함께 배우는 수업 · 컴퓨터/정보

탐색 알고리즘 - 이진 탐색과 DFS/BFS

정렬된 배열에서 O(log N) 만에 값을 찾는 이진 탐색(Binary Search)과 그래프·트리의 모든 정점을 순회하는 깊이 우선 탐색(DFS) 및 너비 우선 탐색(BFS)을 마스터합니다.

이 수업에서 해 볼 일

탐색 조건과 방문 순서에 맞는 알고리즘을 고른다

먼저 알면 좋은 것: 스택(LIFO)과 큐(FIFO) 및 재귀 호출 원리 · 그래프의 인접 리스트 표현과 방문 체크(visited 배열) · 정렬 알고리즘과 로그 시간 복잡도 $O(\log N)$

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

이진 탐색은 정렬된 범위의 중간 값을 비교해 답이 있을 수 없는 절반을 버린다. 정렬 조건이 없으면 그 절반을 버릴 논리적 근거가 없다.BFS는 시작점에서 가까운 간선 수의 층부터 방문한다. DFS는 한 갈래를 깊게 따라가므로 경로의 존재는 찾을 수 있어도 처음 찾은 경로가 항상 최단은 아니다.그래프 탐색에서는 방문 표시로 순환을 막자. BFS의 최단 경로 보장은 동일 간선 비용을 전제로 하므로 가중치가 다르면 비용을 반영하는 알고리즘을 선택해야 한다.

1. 선형 탐색 vs 이진 탐색 (Binary Search)

- 선형 탐색 (Linear Search, $O(N)$ ): 정렬되지 않은 데이터에서 맨 앞부터 끝까지 하나씩 비교하는 방식입니다. - 이진 탐색 (Binary Search, $O(\log N)$ ): - 필수 전제 조건: 탐색 대상 배열이 반드시 오름차순(또는 내림차순)으로 정렬되어 있어야만 사용할 수 있습니다! - 동작 메커니즘: 시작 인덱스 low와 끝 인덱스 high의 중간 지점 mid = (low + high) // 2의 값과 목표값(target)을 비교합니다. - arr[mid] == target: 탐색 성공! - arr[mid] < target: 중간값보다 크므로 왼쪽 절반을 버리고 low = mid + 1로 탐색 범위 축소. - arr[mid] > target: 중간값보다 작으므로 오른쪽 절반을 버리고 high = mid - 1로 탐색 범위 축소. - 압도적 성능: 매 비교마다 탐색 후보가

\frac{1}{2}

로 줄어들어, 약 43억 개( $2^{32}$ )의 데이터에서도 최대 32번의 비교만으로 원하는 값을 찾아냅니다.코딩 테스트 고급 기법 '파라메트릭 서치(Parametric Search)': '최소 얼마 이상이어야 조건을 만족하는가?' 같은 최적화 문제를 'X일 때 조건을 만족하는가?(Yes/No)'라는 결정 문제로 바꾸어 이진 탐색으로 정답을 O(log N)에 찾아내는 핵심 패턴입니다.

2. 그래프 완전 탐색: 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)

그래프의 모든 정점(

V

)과 간선(

E

)을 빠짐없이 방문할 때(인접 리스트 기준 시간 복잡도 $O(V + E)$ ), 어떤 순서로 탐색을 확장하느냐에 따라 두 가지로 나뉩니다. 무한 루프를 막기 위해 반드시 방문 배열(visited)을 체크해야 합니다. 1. DFS (Depth-First Search, 깊이 우선 탐색): - 시작 정점에서 한 방향의 갈림길을 선택해 더 이상 갈 곳이 없을 때까지 가장 깊숙이 파고든 뒤, 막히면 직전 갈림길로 되돌아와(Backtracking) 다른 방향을 탐색합니다. - 구현 도구: 재귀 함수(Recursion) 또는 스택(Stack). - 특화 문제: 모든 경로 탐색, 조합·순열 생성(백트래킹), 연결 요소(Connected Component) 개수 세기, 사이클 존재 여부 판별, 위상 정렬. 2. BFS (Breadth-First Search, 너비 우선 탐색): - 시작 정점에서 거리가 1인 인접 정점들을 모두 먼저 방문하고, 이어서 거리가 2인 정점, 거리가 3인 정점 순으로 물결이 퍼져나가듯 레벨별로 넓게 탐색합니다. - 구현 도구: 큐(Queue / collections.deque) (절대 재귀로 구현 불가!). - 특화 문제: 가중치가 없는 그래프나 격자 미로에서 시작점으로부터 목적지까지의 최단 거리(최소 이동 횟수) 구하기.

예제로 살펴보기

오름차순 정렬된 배열 A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91](인덱스 0~9)에서 이진 탐색으로 목표값 23을 찾을 때, 매 단계 확인하는 중간 인덱스 mid와 값 A[mid]의 변화 과정을 순서대로 서술하시오.

초기 상태: 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를 반환하며 탐색을 종료합니다!

확인: 이진 탐색은 반드시 정렬된 배열에서만 사용할 수 있으며, 탐색 범위를 절반씩 줄여 O(log N)에 목표값을 찾는다.

3. DFS vs BFS 실전 선택 가이드와 가중치 최단 경로 확장

- 언제 DFS를 쓰고 언제 BFS를 쓸까? - "미로에서 탈출하는 최소 칸 수(최단 거리)를 구하라", "특정 상태에 도달하는 최소 연산 횟수를 구하라" ➔ 고민 없이 100% BFS(큐)입니다! DFS는 처음 발견한 경로가 최단 경로라는 보장이 전혀 없기 때문입니다. - "경로의 특징(지나온 노드의 조건)을 저장해야 한다", "모든 경우의 수를 다 해보고 조건에 안 맞으면 되돌아가야(가지치기) 한다" ➔ DFS(재귀 + 백트래킹)가 적합합니다. - 간선에 서로 다른 가중치(비용)가 있다면?: - 간선의 가중치가 모두 1로 같을 때는 일반 큐를 쓰는 BFS로 최단 거리가 구해지지만, 도로의 길이처럼 간선마다 가중치가 다를 때는 큐 대신 우선순위 큐(최소 힙)를 결합한 다익스트라(Dijkstra) 알고리즘 ( $O(E \log V)$ )을 사용해야 합니다.BFS 구현 시 가장 흔한 실수(메모리 초과 원인): 큐에서 노드를 꺼낼 때(popleft) 방문 표시(visited = True)를 하면, 대기 중인 같은 노드가 큐에 중복으로 여러 번 들어가 메모리 초과가 납니다! 반드시 '큐에 넣는 순간(append 직전)'에 visited = True 처리를 해야 합니다.

참고 근거와 확인 범위

Harvard CS50 · Lecture 3: Algorithms ↗
선형·이진 탐색과 정렬 여부의 관계

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →