🔍 탐색(Search)
- 데이터를 찾는 방법
- 대표적으로 정렬 여부에 따라 방식이 나뉨
📌 탐색 알고리즘 분류
1. 정렬되지 않은 데이터
- 순차 탐색 (Linear Search)
- 앞에서부터 하나씩 비교
- 시간 복잡도:
O(N)
2. 정렬된 데이터
✔️ 이진 탐색 (Binary Search)
- 중간 값을 기준으로 탐색 범위를 절반씩 줄임
- 값과 상관없이 항상 중앙에서 시작
- 시간 복잡도:
O(log N)
✔️ 보간 탐색 (Interpolation Search)
- 값의 분포를 활용해서 탐색 위치를 추정
- 단순히 중간이 아니라, 타겟 값이 있을 법한 위치를 계산해서 시작
📌 보간 탐색 핵심 아이디어
- 데이터가 균등하게 분포되어 있다고 가정
- 값과 인덱스가 비례 관계라고 본다
👉 따라서 탐색 위치를 이렇게 계산:
low: 시작 인덱스high: 끝 인덱스target: 찾는 값
➡️ 타겟이 크면 뒤쪽, 작으면 앞쪽으로 더 가까이 점프
📊 특징 비교
| 항목 | 이진 탐색 | 보간 탐색 |
|---|---|---|
| 시작 위치 | 항상 중앙 | 값 기반으로 추정 |
| 전제 조건 | 정렬 | 정렬 + 균등 분포 |
| 평균 성능 | O(log N) | O(log log N) |
| 최악 성능 | O(log N) | O(N) |
⚠️ 실수 나눗셈이 단점인 이유
보간 탐색에서 위치 계산 시:
- 나눗셈 연산이 포함됨
- 특히
실수(float/double)연산은:- 정수 연산보다 비용이 더 큼
- CPU에서 처리 시간이 더 오래 걸림
👉 왜 문제가 될까?
- 이진 탐색은 단순:
mid = (low + high) / 2- → 빠른 정수 연산
- 보간 탐색은:
- 곱셈 + 나눗셈 포함
- → 연산 자체가 더 무거움
👉 결론
- 데이터가 균등 분포라면 → 보간 탐색이 훨씬 빠름
- 하지만:
- 분포가 고르지 않거나
- 연산 비용까지 고려하면
➡️ 실전에서는 이진 탐색이 더 안정적
💡 한 줄 정리
보간 탐색은 “값을 이용해 점프하는 이진 탐색”이지만,
분포 가정 + 연산 비용 때문에 항상 좋은 선택은 아니다.
이진 트리와 이진 탐색 트리
이진 트리(Binary Tree)
- 각 노드가 최대 두 개의 자식 노드를 가지는 트리
- 자식은 보통 왼쪽 자식, 오른쪽 자식으로 구분한다
이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리는 이진 트리에 데이터 저장 규칙을 추가한 형태이다.
저장 규칙
- 각 노드의 키는 유일하다
- 어떤 노드를 기준으로 했을 때:
- 왼쪽 서브트리의 모든 키는 현재 노드의 키보다 작다
- 오른쪽 서브트리의 모든 키는 현재 노드의 키보다 크다
- 왼쪽 서브트리와 오른쪽 서브트리 역시 각각 이진 탐색 트리여야 한다
삽입
이진 탐색 트리에 데이터를 삽입하는 과정은 다음과 같다.
- 루트 노드부터 시작
- 삽입할 값과 현재 노드의 값을 비교
- 현재 값보다:
- 작으면 → 왼쪽 자식으로 이동
- 크면 → 오른쪽 자식으로 이동
- 더 이상 비교할 자식 노드가 없는 위치에 도달하면, 그 자리에 새 노드를 삽입
예시
10이 루트이고5를 넣으면 → 왼쪽15를 넣으면 → 오른쪽7을 넣으면 →10보다 작으므로 왼쪽,5보다 크므로5의 오른쪽에 삽입
삭제
삭제는 삽입보다 복잡하다.
이유는 중간에 있는 노드를 삭제할 경우에도 이진 탐색 트리의 정렬 규칙을 유지해야 하기 때문이다.
1. 리프 노드 삭제
- 자식이 없는 노드라면 그냥 삭제하면 된다
2. 자식이 하나인 노드 삭제
- 삭제할 노드를 없애고
- 그 노드의 자식을 부모와 바로 연결하면 된다
3. 자식이 둘인 노드 삭제
이 경우는 삭제할 노드의 자리를 다른 노드가 대신 채워야 한다.
대표적으로 두 가지 방법이 있다.
방법 1. 왼쪽 서브트리의 가장 큰 값으로 대체
- 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드를 찾는다
- 즉, 왼쪽으로 한 번 간 뒤 계속 오른쪽으로 내려간 노드
- 이 값을 삭제할 노드 자리에 올린다
방법 2. 오른쪽 서브트리의 가장 작은 값으로 대체
- 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드를 찾는다
- 즉, 오른쪽으로 한 번 간 뒤 계속 왼쪽으로 내려간 노드
- 이 값을 삭제할 노드 자리에 올린다
루트 노드 삭제
루트 노드도 결국 삭제 대상 노드 중 하나일 뿐이다.
처리는 일반 노드 삭제와 같은 원리로 할 수 있다.
구현에 따라서는:
- 루트 위에 가상의 부모 노드를 하나 만든 뒤
- 루트를 일반 중간 노드처럼 처리하기도 한다
이렇게 하면 삭제 로직을 더 일관성 있게 구현할 수 있다.
중위 순회와 정렬
이진 탐색 트리를 중위 순회(Inorder Traversal) 하면
노드의 값이 오름차순으로 출력된다.
중위 순회 순서
- 왼쪽 서브트리 방문
- 현재 노드 방문
- 오른쪽 서브트리 방문
이유
이진 탐색 트리는
- 왼쪽에는 작은 값
- 가운데는 현재 값
- 오른쪽에는 큰 값
이 구조를 가지기 때문에 중위 순회를 하면 자연스럽게 정렬된 순서가 된다.
정리
- 이진 탐색 트리는 정렬 규칙이 있는 이진 트리이다
- 삽입은 비교하면서 내려가 빈 자리에 넣으면 된다
- 삭제는 경우를 나누어 처리해야 한다
- 리프 노드: 바로 삭제
- 자식 1개: 자식을 부모와 연결
- 자식 2개: 대체 노드로 교체
🔍 1. 이진 탐색에서 꼭 알아야 하는 포인트
✔️ (1) lower_bound / upper_bound 개념
- lower_bound: target 이상이 처음 나오는 위치
- upper_bound: target 초과가 처음 나오는 위치
👉 이건 단순 탐색이 아니라
“조건을 만족하는 최소 인덱스 찾기” 패턴이다.
✔️ (2) “정답을 찾는 탐색” vs “조건을 만족하는 경계 찾기”
이진 탐색은 사실 두 종류다:
① 값 찾기
arr[mid] == target
② 조건 만족하는 최소/최대 찾기 (이게 더 중요)
조건(mid) == true가 되는 최초 위치
✔️ (3) 파라메트릭 서치 (Parametric Search)
이건 거의 이진 탐색의 확장 개념이다.
👉 “답을 직접 찾는 게 아니라, 조건을 만족하는 최소값/최대값을 찾는다”
- 랜선 자르기
- 입국 심사
- 최대 최소 거리
👉 여기서 핵심은:
- 조건이 단조(monotonic)해야 한다
✔️ (4) overflow 방지 mid 계산
int mid = low + (high - low) / 2;
👉 이유:
(low + high)는 int 범위 넘을 수 있음
✔️ (5) 무한 루프 나는 대표 실수
low = mid; // ❌ 위험
high = mid; // ❌ 위험
👉 반드시:
low = mid + 1;
high = mid - 1;
혹은 lower_bound 스타일로:
low < high 구조 사용
🔍 2. 보간 탐색에서 추가로 알아두면 좋은 것
✔️ (1) 언제 진짜 빠르냐
👉 전제:
- 데이터가 균등 분포
- 값이 선형적으로 증가
이럴 때만:
O(log log N)
✔️ (2) 언제 망하냐
👉 대표 케이스:
[1, 2, 3, 4, 5, 1000000000]
- 값 분포가 깨짐
- pos 계산이 틀어짐
➡️ 거의 순차 탐색처럼 변함
👉 최악: O(N)
✔️ (3) 실무/코테에서 거의 안 쓰는 이유
- 분포 가정이 필요함
- 구현 복잡
- 예외 처리 많음
- 이진 탐색이 충분히 빠름
👉 그래서 현실에서는:
“이진 탐색이 표준, 보간 탐색은 특수 케이스”
🔍 3. 둘 다 공통으로 중요한 개념
✔️ (1) 단조성 (Monotonicity)
이진 탐색이 가능한 이유: false false false true true true
이 구조 때문임 👉 이게 깨지면 이진 탐색 못 씀
✔️ (2) 탐색 범위 정의가 더 중요함
실수 많이 나는 부분:
[low, high][low, high)- 종료 조건
✔️ (3) 탐색 대상이 “값”이 아닐 수도 있음
이진 탐색은 배열 탐색이 아니라:
- 시간
- 거리
- 비용
- 횟수
같은 것에도 적용된다
이게 파라메트릭 서치
질문 사항
입력된 데이터로 이진 탐색 트리를 구성했을 때 시간 복잡도는? 각 원소를 삽입할 때 걸리는 시간 × 원소 개수