자료구조 - 탐색

탐색(Search)

데이터를 찾는 방법으로, 대표적으로 정렬 여부에 따라 방식이 나뉜다.

탐색 알고리즘 분류

정렬되지 않은 데이터

순차 탐색 (Linear Search)

앞에서부터 하나씩 비교한다.

시간 복잡도: O(N)

정렬된 데이터

이진 탐색 (Binary Search)

중간 값을 기준으로 탐색 범위를 절반씩 줄인다. 값과 상관없이 항상 중앙에서 시작한다.

시간 복잡도: O(log N)

보간 탐색 (Interpolation Search)

값의 분포를 활용해 탐색 위치를 추정한다. 단순히 중간이 아니라, 타겟 값이 있을 법한 위치를 계산해서 시작한다.

보간 탐색 핵심 아이디어

데이터가 균등하게 분포되어 있다고 가정하며, 값과 인덱스가 비례 관계라고 본다.

탐색 위치 계산식:

$p os = l o w + \frac{( t a r g e t - a rr [ l o w ]) \times ( hi g h - l o w )}{a rr [ hi g h ] - a rr [ l o w ]}$

low: 시작 인덱스
high: 끝 인덱스
target: 찾는 값

타겟이 크면 뒤쪽, 작으면 앞쪽으로 더 가까이 점프한다.

이진 탐색 vs 보간 탐색 비교

항목	이진 탐색	보간 탐색
시작 위치	항상 중앙	값 기반으로 추정
전제 조건	정렬	정렬 + 균등 분포
평균 성능	`O(log N)`	`O(log log N)`
최악 성능	`O(log N)`	`O(N)`

실수 나눗셈이 단점인 이유

보간 탐색의 위치 계산에는 나눗셈 연산이 포함된다. 특히 실수(float/double) 연산은 정수 연산보다 처리 비용이 크다.

이진 탐색의 중간값 계산은 단순한 정수 연산이다.

mid = (low + high) / 2

반면 보간 탐색은 곱셈과 나눗셈이 포함되어 연산 자체가 더 무겁다.

결론: 데이터가 균등 분포라면 보간 탐색이 빠르지만, 분포가 고르지 않거나 연산 비용까지 고려하면 실전에서는 이진 탐색이 더 안정적이다.

이진 트리와 이진 탐색 트리

이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가지는 트리다. 자식은 왼쪽 자식과 오른쪽 자식으로 구분한다.

이진 탐색 트리(Binary Search Tree, BST)

이진 트리에 데이터 저장 규칙을 추가한 형태다.

저장 규칙:

각 노드의 키는 유일하다.
왼쪽 서브트리의 모든 키는 현재 노드의 키보다 작다.
오른쪽 서브트리의 모든 키는 현재 노드의 키보다 크다.
왼쪽·오른쪽 서브트리 역시 각각 이진 탐색 트리여야 한다.

삽입

루트 노드부터 시작한다.
삽입할 값과 현재 노드의 값을 비교한다.
현재 값보다 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 이동한다.
더 이상 비교할 자식 노드가 없는 위치에 새 노드를 삽입한다.

예시: 루트가 10일 때

5 삽입 → 왼쪽
15 삽입 → 오른쪽
7 삽입 → 10보다 작으므로 왼쪽, 5보다 크므로 5의 오른쪽

삭제

삭제는 삽입보다 복잡하다. 중간 노드를 삭제하더라도 이진 탐색 트리의 정렬 규칙을 유지해야 하기 때문이다.

리프 노드 삭제

자식이 없는 노드는 그냥 삭제한다.

자식이 하나인 노드 삭제

삭제할 노드를 없애고, 그 노드의 자식을 부모와 직접 연결한다.

자식이 둘인 노드 삭제

삭제할 노드의 자리를 다른 노드가 대신 채워야 한다.

방법 1: 왼쪽 서브트리에서 가장 큰 값으로 대체 (왼쪽으로 한 번, 이후 계속 오른쪽)
방법 2: 오른쪽 서브트리에서 가장 작은 값으로 대체 (오른쪽으로 한 번, 이후 계속 왼쪽)

루트 노드 삭제

일반 노드 삭제와 동일한 원리로 처리한다. 구현에 따라 루트 위에 가상의 부모 노드를 만들어 루트를 일반 중간 노드처럼 처리하기도 한다.

중위 순회와 정렬

이진 탐색 트리를 중위 순회(Inorder Traversal)하면 노드의 값이 오름차순으로 출력된다.

중위 순회 순서:

왼쪽 서브트리 방문
현재 노드 방문
오른쪽 서브트리 방문

이진 탐색 트리는 왼쪽에 작은 값, 오른쪽에 큰 값이 위치하므로, 이 순서대로 순회하면 자연스럽게 정렬된 순서가 된다.

이진 탐색 심화

lower_bound / upper_bound

lower_bound: target 이상이 처음 나오는 위치
upper_bound: target 초과가 처음 나오는 위치

단순 값 탐색이 아닌 “조건을 만족하는 최소 인덱스 찾기” 패턴이다.

이진 탐색의 두 가지 유형

값 찾기

arr[mid] == target

조건을 만족하는 경계 찾기

조건(mid) == true가 되는 최초 위치

후자가 실전에서 더 자주 쓰인다.

파라메트릭 서치 (Parametric Search)

답을 직접 찾는 게 아니라, 조건을 만족하는 최솟값 또는 최댓값을 찾는 방식이다.

적용 예시: 랜선 자르기, 입국 심사, 최대 최소 거리

핵심 전제: 조건이 단조(monotonic)해야 한다. 아래처럼 false와 true가 한 번만 전환되어야 한다.

false false false true true true

이진 탐색은 배열 탐색뿐 아니라 시간, 거리, 비용, 횟수 같은 값에도 적용할 수 있다.

overflow 방지 mid 계산

int mid = low + (high - low) / 2;

(low + high)는 int 범위를 넘을 수 있으므로 위 방식을 사용한다.

무한 루프 방지

// 잘못된 방식
low = mid;
high = mid;
 
// 올바른 방식
low = mid + 1;
high = mid - 1;

또는 low < high 구조의 lower_bound 스타일을 사용한다.

보간 탐색 심화

빠른 경우

데이터가 균등 분포이고 값이 선형적으로 증가할 때 O(log log N)을 달성한다.

느린 경우

[1, 2, 3, 4, 5, 1000000000]

값 분포가 치우쳐 있으면 pos 계산이 어긋나 거의 순차 탐색처럼 동작한다. 최악의 경우 O(N).

실무/코테에서 잘 쓰지 않는 이유

분포 가정이 필요하다.
구현이 복잡하고 예외 처리가 많다.
이진 탐색으로도 충분히 빠르다.

이진 탐색이 표준이고, 보간 탐색은 특수한 상황에서만 고려한다.

질문

입력된 데이터로 이진 탐색 트리를 구성했을 때 시간 복잡도는?

각 원소를 삽입할 때 걸리는 시간 × 원소 개수로 계산한다.

정부기 DevBlog

탐색기

탐색 1