ok-lab

깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)은 코딩 테스트에서 단골로 출제되는 문제 유형 중 하나다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 최대한 깊이 먼저 내려간 후, 더 이상 나아갈 곳이 없는 경우에 옆으로 이동하여 다시 탐색하는 방식이다. 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 의 형태로 움직이는 것이다. 미로 찾기 등과 같은 문제를 해결할 때 한 방향으로 끝까지 갈 수 있을 때까지 간 후, 더 이상 갈 수 없으면 가장 가까운 갈림길로 돌아와서 해당 갈림길 방향으로 다시 탐색하는 방식으로 볼 수 있다. 모든 경우의 수를 탐색하고자 할 때 DFS를 사용한다. 그러나, 모든 경우의 수를 ..

해당 문제는 BFS 문제로 완전 탐색을 필요로 하는 문제다. def solution(sizes): h, w = 0,0 for size in sizes: max_s = max(size) min_s = min(size) if max_s >= h: h = max_s if min_s >= w: w = min_s return h * w 다른 사람 풀이를 보면 한 줄로 짧게 작성한 것도 확인할 수 있다. def solution(sizes): return max(max(x) for x in sizes) * max(min(x) for x in sizes)

해당 문제는 bfs를 통해 문제를 해결하는 방식이다. bfs (Breadth-First Search)는 너비 우선 탐색으로 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 예를 들어, 특정 도시에서 다른 도시로 갈 수 있는지 없는지 판단할 때 사용할 수 있다. 시작 정점으로부터 가장 가까운 정점에 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 방식으로, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이를 사용한다. 해당 문제는 두 노드 즉, x, y 간의 최단 경로를 찾는 문제로 해석할 수 있다. def solution(x, y, n): answer = 0 s = set() s.add(x) while s: if y in s: return answe..