컴퓨터 (71) 썸네일형 리스트형 [코딩테스트][알고리즘] 6. BFS (Breadth First Search) 너비 우선 탐색 BFS 역시 DFS와 마찬가지로 코딩 테스트에 자주 나오는 유형이다. BFS는 아래 그림과 같이 진행되는 탐색 알고리즘이다. 시작점으로부터 같은 이동거리에 있는 점들 순차적으로 탐색하는 방법이고, 동심원을 그리며 탐색을 하는 것으로 생각할 수도 있다. 시작점으로부터 이동거리 순으로 탐색을 하기 때문에 최단경로를 구하는데 유용하게 사용된다. BFS는 자료구조 Queue를 사용해서 구현할 수 있다. 코딩 테스트를 위한 BFS는 미로와 같이 x, y 좌표를 이용하는 문제에 자주 사용되는 것 같다고 생각되어 미로 문제를 통해 BFS를 어떻게 코드로 표현하는지 알아보려고 한다. bfs의 구현을 말로 설명하자면 다음과 같이 진행된다. 1. 탐색할 위치의 좌표를 queue에 넣고 방문처리 한다. 2. queue에서 .. java - 백준 알고리즘 - 1012 유기농 배추 https://www.acmicpc.net/problem/1012 이 문제는 dfs 혹은 bfs를 사용해서 풀 수 있는 문제이다. 이 문제와 매우 비슷한 문제인데 입력값의 형식이 조금 다르다. https://www.acmicpc.net/problem/2667 단지번호붙이기 해설 : https://ckdgus.tistory.com/26 코드를 봐도 이해가 잘 안된다면 단지번호붙이기 문제의 해설을 보고와서 다시 보면 이해하는데 도움이 될 것이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { s.. [코딩테스트][알고리즘] 5. DFS (Depth First Search) 깊이 우선 탐색 DFS는 코딩테스트에서 자주 출제되는 유형이라고 하니 잘 익혀두는 것이 좋을 것 같다. DFS는 그림과 같이 탐색을 진행하는 알고리즘이다. 갈때까지 가다가 더 이상 진행 할 곳이 없으면 돌아가서 다음 방법을 찾는 것이다. 미로를 탐색한다고 생각할때 오른벽에서 손을 떼지 않고 계속 전진하면 출구를 찾을수 있다는 아이디어가 바로 DFS 탐색법이라고 말 할 수 있다. 다시 말해 가장 깊은 곳까지 가는 것을 우선시 하며 탐색하는 것이다. dfs는 stack 혹은 재귀함수로 구현 할 수 있다. 재귀함수로 구현하는게 매우 간단하기 때문에 재귀함수로 구현하는 것을 추천한다. dfs는 다음과 같이 구현 할 수 있다. public static void dfs( int here ) { System.out.print(her.. java - 백준 알고리즘 - 2667 단지번호붙이기 https://www.acmicpc.net/problem/2667 이 문제는 백준 단계별로 풀기 bfs , dfs에 분류되어 있는 문제이다. 나는 재귀 dfs를 사용해서 풀었고 기본적인 아이디어는 이러하다. 1. 모든 좌표마다 dfs 반복을 시도한다. ( 2중 for문 사용 ) 2. 좌표의 값이 1이고 방문하지 않았으면 dfs를 실행한다. ( dfs가 한번 실행되면 단지 번호가 1 늘어남 ) ( dfs경로에 있는 아파트들은 모두 방문처리가 되므로 2번이 단지 번호만큼만 실행됨 ) 자세한 내용은 코드에 주석을 참고하면 좋을것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor.. java - 백준 알고리즘 - 2606 바이러스 알고리즘 분류에는 플로이드 와샬 알고리즘이라고 분류 되어있지만 dfs를 이용해서 풀었다. 자세한 설명은 코드에 주석을 보면 좋을 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M, result; static boolean[][] conn;// 컴퓨터 간의 연결을 나타내기 위한 배열 static boolean[] visited;// 방문을 체크하기 위한 배열 public static void main(String[] agrs) throws IOExceptio.. java - 백준 알고리즘 - 2493 탑 이 문제는 자료구조 Stack을 이용하는 문제이다. 왼쪽부터 차례대로 Stack에 하나씩 넣으면서 스텍의 Top 값과 비교해주면 된다. 인덱스를 출력하기 위해서 높이와 인덱스 2개의 stack을 사용하였다. 스텍에 넣을 값 = now, 스텍의 top 값 = top 1. top > now 일때 Top의 index를 버퍼에 담고 now를 hight, index 스텍에 push 해준다. 2. now = i; ++i) { arr[i] = Integer.parseInt(st.nextToken()); } hight.push(arr[1]); index.push(1); bw.write(""+0); for (int i = 2; N >= i; ++i) { while (true) { if (!hight.isEmpty()) .. JAVA - 백준 알고리즘 - 1520 내리막길 이 문제는 dp를 사용하여 풀 수 있는 문제이다. dp를 사용하는데 완전히 익숙해지지 않았는지 계속 시간초과가 났다. 2시간정도 시도 해보다가 결국 다른 블로그에서 코드를 참고하여 테스트케이스를 디버깅해보고 문제를 해결했다. (왼쪽 오른쪽 위쪽 아래쪽)으로 움직여야 할때 nx와 ny를 사용해 간단하게 표현하는 테크닉에 익숙해지도록 자주 사용해봐야 겠다. 자세한 설명은 주석을 참고하면 좋을 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class P1520 { static int[][] map; stati.. [코딩테스트][알고리즘] 4. DP( Dynamic Programming) 다이나믹 프로그래밍 다이나믹프로그래밍의 기본적인 아이디어는 한 번 풀었던 문제를 다시 풀지 말자! 라는 것이다. 풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다. 이러한 과정을 메모이제이션(Memoization) 이라고한다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다. DP는 분할정복기법( 해결했던 문제도 다시 계산 )을 개선 한 것 인데, 대표적인 예가 피보나치수열을 구하는 것이다. 피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2] 의 공식에 의해 진행되는 수들의 나열이다. 분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.. 이전 1 ··· 4 5 6 7 8 9 다음
