개념 정리
탐색 알고리즘 - 이진 탐색과 DFS/BFS
단원 개요
정렬된 배열에서 O(log N) 만에 값을 찾는 이진 탐색(Binary Search)과 그래프·트리의 모든 정점을 순회하는 깊이 우선 탐색(DFS) 및 너비 우선 탐색(BFS)을 마스터합니다.선수 개념
필수 키워드:필수 전제 조건동작 메커니즘
low = mid + 1high = mid - 1압도적 성능방문 배열(visited)구현 도구재귀 함수(Recursion)스택(Stack)1
선형 탐색 vs 이진 탐색 (Binary Search)
•
선형 탐색 (Linear Search, ): 정렬되지 않은 데이터에서 맨 앞부터 끝까지 하나씩 비교하는 방식입니다.
•
이진 탐색 (Binary Search, ):
•
필수 전제 조건: 탐색 대상 배열이 반드시 오름차순(또는 내림차순)으로 정렬되어 있어야만 사용할 수 있습니다!
•
동작 메커니즘: 시작 인덱스
low와 끝 인덱스 high의 중간 지점 mid = (low + high) // 2의 값과 목표값(target)을 비교합니다.•
arr[mid] == target: 탐색 성공!•
arr[mid] < target: 중간값보다 크므로 왼쪽 절반을 버리고 low = mid + 1로 탐색 범위 축소.•
arr[mid] > target: 중간값보다 작으므로 오른쪽 절반을 버리고 high = mid - 1로 탐색 범위 축소.•
압도적 성능: 매 비교마다 탐색 후보가 로 줄어들어, 약 43억 개()의 데이터에서도 최대 32번의 비교만으로 원하는 값을 찾아냅니다.
핵심 원리
코딩 테스트 고급 기법 '파라메트릭 서치(Parametric Search)': '최소 얼마 이상이어야 조건을 만족하는가?' 같은 최적화 문제를 'X일 때 조건을 만족하는가?(Yes/No)'라는 결정 문제로 바꾸어 이진 탐색으로 정답을 O(log N)에 찾아내는 핵심 패턴입니다.2
그래프 완전 탐색: 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)
그래프의 모든 정점()과 간선()을 빠짐없이 방문할 때(인접 리스트 기준 시간 복잡도 ), 어떤 순서로 탐색을 확장하느냐에 따라 두 가지로 나뉩니다. 무한 루프를 막기 위해 반드시 방문 배열(visited)을 체크해야 합니다.
1
DFS (Depth-First Search, 깊이 우선 탐색):
•
시작 정점에서 한 방향의 갈림길을 선택해 더 이상 갈 곳이 없을 때까지 가장 깊숙이 파고든 뒤, 막히면 직전 갈림길로 되돌아와(Backtracking) 다른 방향을 탐색합니다.
•
구현 도구: 재귀 함수(Recursion) 또는 스택(Stack).
•
특화 문제: 모든 경로 탐색, 조합·순열 생성(백트래킹), 연결 요소(Connected Component) 개수 세기, 사이클 존재 여부 판별, 위상 정렬.
2
BFS (Breadth-First Search, 너비 우선 탐색):
•
시작 정점에서 거리가 1인 인접 정점들을 모두 먼저 방문하고, 이어서 거리가 2인 정점, 거리가 3인 정점 순으로 물결이 퍼져나가듯 레벨별로 넓게 탐색합니다.
•
구현 도구: 큐(Queue /
collections.deque) (절대 재귀로 구현 불가!).•
특화 문제: 가중치가 없는 그래프나 격자 미로에서 시작점으로부터 목적지까지의 최단 거리(최소 이동 횟수) 구하기.
풀이
초기 상태: low = 0, high = 9, target = 23
1) 1단계 비교:
•
mid = (0 + 9) // 2 = 4 ➔ A[4] = 16.
•
목표값 23 > 16이므로 왼쪽 절반(0~4)을 버리고 low = mid + 1 = 5로 갱신합니다 (범위: 5~9).
2) 2단계 비교:
•
mid = (5 + 9) // 2 = 7 ➔ A[7] = 56.
•
목표값 23 < 56이므로 오른쪽 절반(7~9)을 버리고 high = mid - 1 = 6으로 갱신합니다 (범위: 5~6).
3) 3단계 비교:
•
mid = (5 + 6) // 2 = 5 ➔ A[5] = 23.
•
목표값 23 == A[5]가 일치하므로 총 3번의 비교 만에 인덱스 5를 반환하며 탐색을 종료합니다!
3
DFS vs BFS 실전 선택 가이드와 가중치 최단 경로 확장
•
언제 DFS를 쓰고 언제 BFS를 쓸까?
•
"미로에서 탈출하는 최소 칸 수(최단 거리)를 구하라", "특정 상태에 도달하는 최소 연산 횟수를 구하라" ➔ 고민 없이 100% BFS(큐)입니다! DFS는 처음 발견한 경로가 최단 경로라는 보장이 전혀 없기 때문입니다.
•
"경로의 특징(지나온 노드의 조건)을 저장해야 한다", "모든 경우의 수를 다 해보고 조건에 안 맞으면 되돌아가야(가지치기) 한다" ➔ DFS(재귀 + 백트래킹)가 적합합니다.
•
간선에 서로 다른 가중치(비용)가 있다면?:
•
간선의 가중치가 모두 1로 같을 때는 일반 큐를 쓰는 BFS로 최단 거리가 구해지지만, 도로의 길이처럼 간선마다 가중치가 다를 때는 큐 대신 우선순위 큐(최소 힙)를 결합한 다익스트라(Dijkstra) 알고리즘 ()을 사용해야 합니다.
주의할 점
BFS 구현 시 가장 흔한 실수(메모리 초과 원인): 큐에서 노드를 꺼낼 때(popleft) 방문 표시(visited = True)를 하면, 대기 중인 같은 노드가 큐에 중복으로 여러 번 들어가 메모리 초과가 납니다! 반드시 '큐에 넣는 순간(append 직전)'에 visited = True 처리를 해야 합니다.핵심 요약
- ✓이진 탐색은 반드시 정렬된 배열에서만 사용할 수 있으며, 탐색 범위를 절반씩 줄여 O(log N)에 목표값을 찾는다.
- ✓DFS(깊이 우선 탐색)는 스택이나 재귀 함수로 구현하며 백트래킹, 사이클 판별, 모든 경로 탐색에 적합하다.
- ✓BFS(너비 우선 탐색)는 큐(Queue)로 구현하며 시작점으로부터 가까운 순서대로 방문하므로 비가중치 그래프의 최단 경로를 보장한다.
- ✓인접 리스트로 표현된 그래프에서 DFS와 BFS의 전체 탐색 시간 복잡도는 모두 O(V + E)이다.