왜 탐색 방법이 여러 가지인가

“배열에서 특정 값을 찾는다”는 목표는 하나지만, 데이터가 어떤 상태로 준비되어 있는가에 따라 쓸 수 있는 방법과 그 대가가 완전히 달라진다. 정렬되지 않은 데이터에는 순차 탐색밖에 쓸 수 없고, 정렬된 데이터라면 훨씬 빠른 이진 탐색을 쓸 수 있다. 정렬을 유지하는 비용 자체를 아예 피하고 싶다면 해시 테이블을 쓸 수도 있다. 독학사 4단계 시험은 이 세 방법의 절차 자체보다 “이 상황에서는 어떤 방법을 선택해야 하는가”, “그 복잡도는 왜 그 값인가”를 근거와 함께 설명할 수 있는가를 더 깊이 묻는다. 이 편에서는 절차 추적은 짧게 다루고, 복잡도를 수식으로 유도하는 과정과 선택 기준에 집중한다.

쉽게 말하면: 탐색은 “데이터를 미리 얼마나 손질해 두었는가”와 “그 손질에 어떤 대가를 치렀는가”를 맞바꾸는 문제다.

순차 탐색 — 손질 없이 바로 찾기

순차 탐색(sequential search, 선형 탐색)은 배열의 맨 앞부터 하나씩 확인해 목표값을 찾는 가장 단순한 방법이다. 정렬 여부와 무관하게 항상 쓸 수 있다는 것이 유일한 장점이다.

원소가 $n$개인 배열에서 목표값이 배열에 있을 확률이 균등하다고 가정하면, 평균적으로 배열의 중간쯤(약 $n/2$번째)에서 찾게 되므로 평균 비교 횟수는 $\frac{n+1}{2}$번이다. 하지만 점근적 표기에서는 계수를 버리므로 평균과 최악 모두 $O(n)$으로 같은 계열에 속한다. 정렬이 되어 있지 않을 때 순차 탐색은 선택의 여지가 없는 유일한 방법이라는 점에서, “느리지만 항상 쓸 수 있다”는 것 자체가 이 알고리즘의 존재 이유다.

이진 탐색 — 정렬을 대가로 절반씩 버린다

이진 탐색(binary search)은 배열이 정렬되어 있을 때만 쓸 수 있는 방법으로, 탐색 범위의 중간값과 목표값을 비교해 절반을 통째로 버리는 과정을 반복한다. 이 편에서는 절차 추적보다 왜 시간 복잡도가 $O(\log n)$인지를 점화식으로 유도하는 데 집중한다.

점화식 세우기

크기 $n$짜리 범위를 탐색하는 데 걸리는 비교 횟수를 $T(n)$이라 하자. 이진 탐색은 중간값과 한 번 비교한 뒤, 그 결과에 따라 크기가 정확히 절반(약 $n/2$)인 범위 하나만 남기고 나머지는 완전히 버린다. 그러므로 다음과 같은 점화식이 성립한다.

• $T(n)$: 크기 $n$인 범위를 탐색하는 데 필요한 비교 횟수
• $T(n/2)$: 절반으로 줄어든 범위를 탐색하는 데 필요한 비교 횟수(재귀적으로 같은 문제)
• $+1$: 지금 범위에서 중간값과 한 번 비교하는 비용
• 기저 조건: $T(1) = 1$(범위에 원소가 하나 남으면 비교 한 번으로 종료)

반복 대입으로 점화식 풀기

이 점화식을 $n$이 $2^k$ 꼴이라고 가정하고 반복해서 대입하며 풀어본다.

이 패턴을 계속 반복하면, $j$번 대입했을 때 다음과 같은 형태가 된다.

범위 크기가 1이 되는 순간이 재귀가 끝나는 지점이므로, $\frac{n}{2^j} = 1$이 되는 $j$를 구하면 된다.

이 $j$를 대입하면 다음과 같은 결과를 얻는다.

상수항 1을 점근적 표기에서 버리면 최종적으로 다음과 같다.

이 유도 과정이 말해주는 것은 단순하다. 매번 절반을 버리는 전략이므로, 범위가 1이 될 때까지 절반을 나누는 횟수가 곧 비교 횟수이고, 그 횟수는 $n$을 몇 번 2로 나눠야 1이 되는지, 즉 $\log_2 n$이다.

이진 탐색도 결정 트리 하한을 만족한다

09편에서 다룬 결정 트리 논증은 정렬뿐 아니라 비교 기반 탐색에도 그대로 적용된다. 정렬된 배열 $n$개 원소 중 목표값이 있을 수 있는 위치는 $n$가지, 없을 수도 있다는 경우까지 포함하면 총 $n+1$가지의 결과가 나올 수 있다. 비교 한 번마다 결과가 둘로 갈리는 이진 결정 트리이므로, 리프가 $n+1$개 이상이려면 트리 높이 $h$가 다음을 만족해야 한다.

이진 탐색은 이 하한을 정확히 달성하는 최적의 비교 기반 탐색 방법이다. 즉 “정렬된 배열에서 값의 존재 여부를 비교로만 확인하는” 어떤 알고리즘도 이진 탐색보다 적은 비교로 항상 성공할 수는 없다.

자주 틀리는 점: 이진 탐색이 $O(\log n)$인 이유를 “그냥 절반씩 줄어드니까 로그”라고 뭉뚱그려 외우면, “왜 로그의 밑이 2인가”, “왜 상수 1이 사라지는가” 같은 서술형 문항에 답하지 못한다. 점화식 $T(n) = T(n/2) + 1$을 직접 세우고 반복 대입으로 $\log_2 n$을 유도하는 과정 자체를 설명할 수 있어야 한다.

해시 탐색 — 정렬 대신 계산으로 위치를 찾는다

해싱(hashing)은 정렬을 유지하는 비용 자체를 피하고, 값을 해시 함수 $h(k)$로 계산해 바로 그 위치에 저장·탐색하는 방법이다. 해시 함수 자체와 체이닝·개방 주소법의 동작 절차는 자료구조 과목에서 이미 다뤘으므로(연결리스트·개방 주소 탐사의 구체적인 삽입 과정은 자료구조 2단계 16편 참고), 이 편에서는 평균 성능이 왜 그렇게 되는지를 수식으로 유도하는 데 집중한다.

적재율이라는 하나의 숫자로 성능을 예측한다

해시 테이블의 성능을 결정하는 가장 중요한 값은 적재율(load factor) $\alpha$다.

• $n$: 테이블에 실제로 저장된 키의 개수
• $m$: 테이블의 전체 칸(슬롯) 수
• $\alpha$: 칸 하나당 평균적으로 몇 개의 키가 몰려 있는지를 나타내는 비율

체이닝(chaining) 방식에서는 키들이 균등하게 분산되어 있다고 가정하면, 각 칸의 연결리스트 길이는 평균적으로 $\alpha$개가 된다. 어떤 키를 탐색할 때는 해시값을 계산하는 데 $O(1)$, 그 칸의 리스트를 훑는 데 평균 $O(\alpha)$가 걸리므로, 체이닝의 평균 탐색 시간은 다음과 같다.

$\alpha$가 항상 어떤 상수 이하로 유지되도록 관리하면(예: 저장된 키가 칸 수의 1.5배를 넘으면 테이블 크기를 늘리는 방식), 이 값은 사실상 $O(1)$에 가까워진다. 이것이 “해시 테이블은 평균 $O(1)$에 동작한다”는 말의 정확한 근거다.

개방 주소법(open addressing)에서는 테이블 안에서만 빈칸을 찾아야 하므로 $\alpha$가 1을 넘을 수 없다($n \leq m$). 선형 조사법을 균등 해싱으로 가정했을 때, 삽입에 실패할 확률 없이 성공하기까지 평균 탐사 횟수는 대략 다음 식으로 근사된다.

이 식이 말해주는 함정은 명확하다. $\alpha = 0.5$(테이블이 절반 찼을 때)면 평균 탐사 횟수는 $\frac{1}{0.5} = 2$번이지만, $\alpha = 0.9$(90퍼센트 참)면 $\frac{1}{0.1} = 10$번으로 급격히 늘어난다. 적재율이 1에 가까워질수록 평균 탐사 횟수가 폭발적으로 증가한다는 것이 개방 주소법의 핵심 약점이다.

최악의 경우는 여전히 O(n)이다

평균 성능이 아무리 좋아도, 모든 키가 해시 함수 계산 결과 같은 칸으로 몰리는 최악의 경우(해시 함수 설계가 나쁘거나, 공격자가 의도적으로 충돌을 유발하는 경우)라면 체이닝은 하나의 긴 연결리스트를 순차 탐색하는 것과 같아져 $O(n)$이 되고, 개방 주소법도 테이블 전체를 훑어야 할 수 있어 $O(n)$이 된다.

자주 틀리는 점: “해시 탐색은 항상 $O(1)$이다”라고 단정하면 안 된다. 이는 적재율이 상수로 관리되고 해시 함수가 키를 고르게 분산시킨다는 조건 아래에서의 평균 시간이며, 최악의 경우는 여전히 $O(n)$이다. “해시 테이블은 최악의 경우에도 O(1)을 보장한다”는 보기는 항상 틀린 진술이다.

무엇을 선택해야 하는가 — 상황별 판단 기준

세 방법의 복잡도만 외우는 것으로는 시험에서 “이런 상황에는 어떤 자료 구조·탐색을 써야 하는가”를 묻는 응용 문항에 대응하기 어렵다. 판단은 보통 다음 순서로 이루어진다.

• 정렬을 유지할 필요가 없고 순서·범위 검색이 필요 없다면 해시 테이블이 평균적으로 가장 빠르다. 다만 최악의 경우($O(n)$)에 대비해 해시 함수 품질과 적재율 관리가 필요하다.
• “5보다 크고 20보다 작은 값을 모두 찾아라”처럼 범위·순서 질의가 필요하다면 해시 테이블은 적합하지 않다(해시 함수는 순서를 보존하지 않는다). 정렬된 배열이나 균형 탐색 트리(자료구조 2단계 14편 참고)를 이진 탐색과 함께 써야 한다.
• 데이터가 정렬되어 있지 않고, 정렬을 유지하는 비용(삽입할 때마다 재정렬)이 검색 이득보다 크다면 순차 탐색이 오히려 합리적인 선택일 수 있다. 예를 들어 탐색을 딱 한 번만 할 데이터라면, 정렬($O(n \log n)$) 후 이진 탐색($O(\log n)$)을 하는 것보다 그냥 순차 탐색 한 번($O(n)$)이 총 비용이 더 적다.

자주 틀리는 점: “정렬만 되어 있으면 무조건 이진 탐색이 최선이다”라고 단정하면 안 된다. 탐색을 딱 한 번만 수행할 것이라면, 정렬 비용 $O(n \log n)$까지 합산했을 때 총 비용은 순차 탐색 한 번의 $O(n)$보다 오히려 크다. 이진 탐색이 유리해지는 것은 같은 정렬된 데이터에 대해 탐색을 여러 번 반복할 때다.

자주 틀리는 점

• 이진 탐색의 O(log n)을 점화식 없이 직관으로만 설명하는 실수: 서술형 문항에서는 $T(n) = T(n/2) + 1$을 세우고 $\log_2 n$을 유도하는 과정 자체를 요구할 수 있다.
• 적재율 $\alpha$를 저장된 키 개수로 착각하는 실수: $\alpha$는 키 개수 자체가 아니라 키 개수를 테이블 크기로 나눈 비율이다.
• 해시 탐색이 항상 최악에도 O(1)이라고 착각하는 실수: 평균은 O(1)에 가까울 수 있지만, 최악은 여전히 O(n)이다.
• 정렬되어 있으면 무조건 이진 탐색이 이득이라고 착각하는 실수: 탐색을 한 번만 한다면 정렬 비용까지 합쳐 순차 탐색보다 총 비용이 클 수 있다.

핵심 정리

• 순차 탐색은 정렬 여부와 무관하게 $O(n)$이며, 데이터가 정렬되어 있지 않을 때의 유일한 대안이다.
• 이진 탐색은 점화식 $T(n)=T(n/2)+1$을 반복 대입해 $O(\log n)$을 유도할 수 있고, 이는 비교 기반 탐색의 결정 트리 하한 $\log_2(n+1)$에 정확히 도달한 최적값이다.
• 해시 탐색의 평균 성능은 적재율 $\alpha=n/m$으로 결정되며, 체이닝은 $O(1+\alpha)$, 개방 주소법은 대략 $O(1/(1-\alpha))$이지만, 두 방식 모두 최악의 경우 $O(n)$을 피할 수 없다.
• 어떤 방법을 선택할지는 “정렬 유지가 가능한가”, “순서·범위 질의가 필요한가”, “탐색을 몇 번 반복할 것인가”를 기준으로 판단한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 알고리즘 과목 출제기준·평가영역 확인용 공식 안내.
• GeeksforGeeks — Binary Search  — 이진 탐색의 복잡도 유도와 결정 트리 하한 관련 개념 참고 자료.