사전 캠프 9일차

오늘은 먼저 웹 개발 종합반 3주차 강의 먼저 듣고 백준 코딩테스트 문제를 풀었다

 

웹개발 종합반 3주차 강의

 

Jquery에 대해 먼저 배웠는데

function checkResult() {
        let fruits = ['사과','배','감','귤','수박']
        $('#q1').empty();
        
        fruits.forEach(a =>{
            let temp_html = `<p>${a}</p>`;
            $('#q1').append(temp_html);
        })
        let people = [
            {'name':'서영','age':24},
            {'name':'현아','age':30},
            {'name':'영환','age':12},
            {'name':'서연','age':15},
            {'name':'지용','age':18},
            {'name':'예지','age':36}
        ]
        $('#q2').empty();
        people.forEach(a =>{
            let temp_html = `<p>${a['name']}는 ${a['age']}살 입니다.</p>`;
            $('#q2').append(temp_html);
        })

    }

 

이런식으로 $('#목표 id')로 변경을 원하는 지점을 지정하고 뒤에 .empty나 .append로 변경해주면 된다.

또한 html 태그를 사용 하려면 ` 백틱이라는 기호를 사용해서 더욱 쉽게 사용가능하다.

 

 

$('#타겟').toggle();

타겟인 부분을 없앴다가 만들었다가 할 수 있다. 아예 없애는 것이 아닌 display='none' 상태를 만들어준다.

 

id 가  image인 곳의 value 값을 가져온다

 let image = $('#image').val();

 

fetch 부분은 아쉽게 실습이 안되서 이론적으로 이해만 했다

fetch("URL")
// 해당 URL로 웹 통신을 요청 기본은 GET
	.then(res => res.json()) 
// 데이터를 res라는 이름으로 JSON화
	.then(data => { 
		console.log(data) 
   }) // JSON 형태로 바뀐 데이터를 개발자도구로 확인

 

다음에 실습이 정상화되면 다시 해보려고한다!

 

• then은 통신 요청 받은 후 할 행동에 대해 지정하는 것

 

알고리즘 문제풀기! 

 

백준 1697번 숨바꼭질

한번 풀었던 문제로 기억을 되살려 쉽게 풀었던거 같다. 사실 처음 풀었을 때는 전형적인 DP 문제라고 생각하고 DP로 풀었었는데 BFS로 간단하게 풀려서 상당히 놀랐던 문제로 BFS/DFS가 이런식으로도 활용될 수 있구나 라는 것을 배운 문제이다.

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static boolean visited[];
	public static int [] arr;
	public static int dp[][];
	public static LinkedList <String> list = new LinkedList<>();
	public static Queue <Integer> q = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		arr = new int[100001];
		visited = new boolean[100001];
		bfs(n,k);
	
	}
	public static void bfs(int n, int k) {
		q.add(n);
		while(!q.isEmpty()) {
			n = q.poll();
			if(n==k) {
				System.out.println(arr[k]);
				return;
			}
			if(n  - 1 >= 0 && arr[n-1] == 0 ) {
				arr[n-1] = arr[n] + 1;
				q.add(n-1);
			}
			if(n + 1 < 100001 && arr[n+1] == 0) {
				arr[n+1] = arr[n] + 1;
				q.add(n+1);
			}
			if(n * 2 < 100001 && arr[n * 2] == 0) {
				arr[n * 2] = arr[n] + 1;
				q.add(n*2);
			}
		}
	}
}

 

 

 

 

백준 11724번 연결 요소의 개수

 

전형적인 DFS 문제로 그냥 들어갈때 마다 count 값을 올려주는 식으로 해결했다.

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int[][] arr;
	public static boolean visited[];
	public static Stack <Integer> stack = new Stack<>();
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		arr = new int[n+1][n+1];
		visited = new boolean[n+1];
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a][b] = arr[b][a] = 1;
		}
		int count = 0;
		for(int i=1;i<=n;i++) {
			if(!visited[i]) {
				dfs(n,i);
				count++;
			}
				
			
		}
		System.out.println(count);
	}
	public static void dfs(int n, int v) {
		visited[v] = true;
		for(int i=1;i<=n;i++) {
			if(arr[v][i]==1 && !visited[i]) {
				dfs(n,i);
			}
		}
	}
}

 

 

백준 14502번 연구소

벽 세우는걸 브루트포스로 전체를 돌려가며 모든 경우의 수를 찾고 DFS로 바이러스가 퍼져가는 것을 구현하고 원래의 상태를 미리 복제해두고 다시 원상복구 시키는 식으로 구현했는데 구글에 검색하니 벽세우는 것을 DFS로 구현하는게 더욱 성능적으로 우월하고 BFS로 바이러스가 퍼져가는걸 구현하는게 더 좋다고 해서 다시 풀어봤다. 또한 Clone 메서드를 쓰면 깊은 복제로 분명 배열이 따로따로 존재해야 되는데 어느 순간 문제가 생겼다 이 부분은 저녁에 조금 더 공부해보려고 한다!

 

추가 ) 이차원 배열은 Clone 메서드를 써도 앝은 복사가 된다! 일차원 배열 단위로 clone 하자!

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int arr[][];
	public static int test[][];
	public static boolean visited[][];
	public static int n;
	public static int m;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n][m];
		test = new int[n][m];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0;j<m;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				test[i][j] = arr[i][j];
			}
		}
		int max = -1;
		for(int i=0;i<n*m-2;i++) {
			if(arr[i/m][i%m] == 0) {
				for(int j=i+1;j<n*m-1;j++) {
					if(arr[j/m][j%m] == 0) {
						for(int k=j+1;k<n*m;k++) {
							if(arr[k/m][k%m] == 0) {
								visited = new boolean[n][m];
								makeWall(i,j,k);
								for(int a=0;a<n;a++) {
									for(int b =0;b<m;b++) {
										if(test[a][b]==2 && !visited[a][b]) {			
											dfs(a,b);
										}
									}
								}		
								int a = countSafeZone();
								if(a > max) {
									max = a;
								}
								reset();
							}
						}
					}
				}
			}
		}
		System.out.println(max);
	}
	public static void dfs(int a, int b) {
		int xFlag [] = {-1,0,0,1};
		int yFlag [] = {0,-1,1,0};
		visited[a][b] = true;
		for(int i=0;i<4;i++) {
			int newA = a + xFlag[i];
			int newB = b + yFlag[i];
			if(newA >=0 && newB >=0 && newA < n && newB < m) {
				if(test[newA][newB]==0) {
					test[newA][newB]=2;
					dfs(newA,newB);
				}
			}
		}
	}
	public static int countSafeZone() {
		int count = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(test[i][j]==0) {
					count++;
				}
			}
		}
		return count;
	}

	public static void makeWall(int i, int j,int  k) {
		test[i/m][i%m] = 1;
		test[j/m][j%m] = 1;
		test[k/m][k%m] = 1;
	}
	public static void reset() {
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				test[i][j] = arr[i][j];
			}
		}
	}
}

 

 

검색을 통해 다른부분과 복제 부분을 고친 코드

알긴 하지만 제대로 정리하진 않는 백트래킹 기법이 사용되어서 조금 당황했지만 그래도 이해가 안되는 부분은 없었던거 같다

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static int arr[][];
	public static int copy[][];
	public static int n;
	public static int m;
	public static int max = -1;
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		arr = new int[n][m];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(bf.readLine());
			for(int j=0;j<m;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(0);
		System.out.println(max);
	}
	public static void dfs(int count) {
		if(count == 3) {
			bfs();
			return;
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(arr[i][j]==0) {
					arr[i][j] = 1;
					dfs(count+1);
					arr[i][j] = 0;
				}
			}
		}
	}
	public static void bfs() {
		int xFlag [] = {-1,0,0,1};
		int yFlag [] = {0,-1,1,0};
		Queue <String> q = new LinkedList<>();
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr[i][j] == 2) {
					q.offer(i+" "+j);
	            }
	        }
	    }
		copy = new int[n][m];
		for(int i=0;i<n;i++) {
			copy[i]=arr[i].clone();
		}
		while(!q.isEmpty()) {
			StringTokenizer st2 = new StringTokenizer(q.poll());
			int x = Integer.parseInt(st2.nextToken());
			int y = Integer.parseInt(st2.nextToken());
			for(int i=0;i<4;i++) {
				int newx = x + xFlag[i];
				int newy = y + yFlag[i];
				if(newx >= 0 && newx < n && newy >=0 && newy < m) {
					if(copy[newx][newy]==0) {
						copy[newx][newy]=2;
						q.add(newx+" "+newy);
					}
				}
			}
		}
		countSafeZone();
	}
	public static void countSafeZone() {
		int count = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(copy[i][j]==0) {
					count++;
				}
			}
		}
		max = Math.max(max, count);
	}

}

 

 

위에가 내가 원래 풀었던 방식 아래가 구글을 통해 수정한 방식인데 성능 차이가...? 어째서 내가 풀었던 방식이 더 뛰어난지 모르겠다. 코드 자체는 검색한 방법이 깔끔하다고 생각한다. 내가 짜면서도 5중 포문은 이게 맞나 싶었기 때문이다. 어느 부분에서 성능 차이가 많이 나는지 확인해 봐야할거같다!

 

주말 동안 풀었는데 문제 조금 더 풀고 월요일에는 DFS / BFS 관련 문제는 전부 끝내려고 한다!