설모의 기록

탐색 알고리즘에는 여러가지가 있습니다. 가장 기본적인 알고리즘이 BFS 와 DFS 인데요. 각각 아래에서 살펴보겠습니다. BFS(Breath First Search) BFS 는 너비우선탐색 알고리즘입니다. 위의 트리는 깊이(depth)가 2인 이진트리입니다. BFS는 루트부터 시작해서 깊이별로 가로방향을 먼저 탐색해나가는 방식입니다. 따라서 1단계에 있는 a를 먼저 탐색하고, 2단계에 있는 b,c 를 탐색하고, 마지막으로 3단계에 있는 d,e,f,g 를 탐색하는 방식입니다. 장점너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장합니다.최단경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.노드의 수가 적고 깊이가 얕은 해가 존재..

최단 경로 탐색 알고리즘 최단 경로를 탐색하는 알고리즘의 종류는 여러가지가 존재합니다. 그 종류 중 하나인 a* 알고리즘에 대해 알아보겠습니다. a* 알고리즘은 bfs 알고리즘의 한 예로, 휴리스틱(h) 값을 이용해 최단 경로를 추정해나가는 방식입니다. 아래의 설명을 보시면 아시겠지만 휴리스틱 값이 0이라고 생각하면 결국 최단 경로가 되는데요. 휴리스틱 값이 0 이라면 bfs 와 똑같은 알고리즘이 됩니다. 따라서, 이 알고리즘은 결국 bfs 알고리즘이 최단 경로를 발견한다는 것을 다시 입증해주는 예시입니다. 개념과 예시는 아래에서 설명하도록 하겠습니다. A* 알고리즘? 한 지점에서 목표 지점으로 가는 방법 중 가장 짧은 길을 찾는 것을 최단 경로 탐색이라 하며, 지점을 노드라고 표현합니다. a* 알고리즘..

이 문제는 간단한 동적계획법 문제입니다. 이전 값들을 배열에 저장해놓고 다음 배열 값에는 이전 값들을 읽어와 저장을 하는 방식입니다. 소스코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int[][] dp = new int[41][2]; public static void main(String[] args) throws IOException { BufferedR..

이 문제는 입력된 수만큼 사람이 원으로 앉고, 입력된 값만큼 원을 돌며 사람을 제거하는 문제입니다. 푸는 방식- 큐에 N 까지의 숫자를 모두 넣습니다.- (M - 1) 만큼 큐에서 숫자를 빼 마지막에 넣습니다.- 큐에서 한개를 pop 해 출력합니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class..

이 문제는 dfs 와 bfs 두 방식을 이용해 그래프 탐색 결과를 출력하는 문제입니다. 단 방문할 때 낮은 정점 순으로 방문을 해야 합니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N, M, V; static int[][] graph; static int[] dx = { 0, -1, 0, 1 }, dy = { 1, 0, -1, 0 }; static int[] visit; ..

이 문제는 큐를 이용하는 문제입니다. 우선순위가 높은 문서를 먼저 뽑고 그 다음 들어온 순서대로 문서를 프린트해 입력된 인덱스값의 문서가 몇 번째로 프린트되게 되는지를 구하는 문제입니다. 푸는 방식- linkedlist 에 우선순위 값을 전부 저장합니다. - 큐에 입력된 순서대로 우선순위를 저장합니다.- 큐를 돌면서 getMax() 함수를 이용해 가장 높은 우선순위를 구하고, 그 값과 현재 가장 앞에 있는 문서의 우선순위 값과 같으면 pop, 아니면 다시 push 합니다. 이 때, 우선순위 값도 같고 구하려는 인덱스가 현재의 문서의 인덱스와 일치하면 인덱스를 출력하고 다음 테스트케이스로 넘어갑니다. import java.io.BufferedReader; import java.io.BufferedWrite..

이 문제는 다익스트라 알고리즘의 대표 문제입니다. 다익스트라 알고리즘 개념에 대해서 잊어버려서 개념부터 다시 보고 온,,다익스트라 알고리즘은 가중치가 존재하는 그래프에서 정점과 정점사이의 최단거리를 구할 때 사용 되는 알고리즘 입니다. 처음엔 다익스트라 알고리즘 개념만 보고 온 상태로 문제를 풀었습니다. weight 를 int[nV + 1][nV + 1] 배열로 만들어 사용했더니 런타임 에러가 났습니다.왜그러나 했는데 이차원 배열일 경우에는 사용하지 않는 인덱스도 너무 많았습니다. 게다가 정점의 개수 nV 가 20,000 개라면, weight 배열에만 20,000 * 20,000 * 4 byte 가 필요하기 때문에 메모리 낭비입니다.알고리즘 문제를 풀 때 다익스트라 알고리즘은 우선순위 큐와 함께 사용하는..

저는 dfs 를 이용해 풀었습니다. 테스트 케이스를 포함해 모든 케이스가 맞는데도 불구하고 계속 틀려서 왜 그러나 했는데, 한 반복문 안에서 뿌요뿌요가 두번 터지면 count 변수는 한번만 증가시켜야 제대로 된 정답이 나옵니다. (예) 아래의 케이스의 경우, count 변수는 1 이 나와야 합니다.............................................................RRRYYYRRRYYY 푸는 방식- 뿌요뿌요 배열에서 내가 검사해야 할 가장 위쪽 X 인덱스가 몇인지 구한다. (minX)- while 문을 돌면서 '.' 이 아닌 char 를 찾는다.- 그 char 를 포함해 주변에 같은 문자들의 개수가 4를 넘으면 뿌요뿌요를 터뜨리고 flag 변수를 바꿔준다.- fla..

저는 dfs, bfs 를 이용하여 문제를 풀었습니다. 푸는 방식- dfs 를 이용해 이중루프를 돌려 섬마다 번호를 체크해줍니다.- bfs 를 이용해 큐에 들어있는 인덱스 주변으로 섬을 확장 시킵니다.- 가장 짧은 길이를 출력합니다. import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Point { int x, y; Point (int x, int y) { this.x = x; this.y = y; } } public class Main { static int N, COUNT = 0, NUMBER = 0; static int[][] a, visit, bridge..