탐색 알고리즘 (Search Algorithms)

📝 개념 정의

데이터 집합에서 원하는 값을 찾는 알고리즘입니다.

주요 탐색 방법:

순차 탐색 (Linear Search)
이진 탐색 (Binary Search)

🔍 순차 탐색 (Linear Search)

개념

리스트의 앞에서부터 하나씩 확인하는 방법입니다.

특징

시간복잡도: O(n)

장점: ✅ 구현 간단 ✅ 정렬 불필요

단점: ❌ 느린 속도 (데이터가 많을 때)

⭐ 이진 탐색 (Binary Search)

개념

정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 방법입니다.

전제 조건

리스트가 정렬되어 있어야 함

동작 과정

중간값 선택
찾는 값과 중간값 비교
찾는 값이 작으면 왼쪽 절반 탐색
찾는 값이 크면 오른쪽 절반 탐색
값을 찾을 때까지 반복

예시

배열: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 찾는 값: 4

Step 1

시작: 0, 끝: 9, 중간: 4 (index)
중간값: 8
4 \u003c 8 → 왼쪽 탐색

Step 2

시작: 0, 끝: 3, 중간: 1
중간값: 2
4 \u003e 2 → 오른쪽 탐색

Step 3

시작: 2, 끝: 3, 중간: 2
중간값: 4
찾음!

📊 시간복잡도 분석

이진 탐색의 시간복잡도

O(log n)

이유:

매 단계마다 탐색 범위가 절반으로 감소
n → n/2 → n/4 → ... → 1
k번 반복 시: n/2^k = 1
k = log₂n

비교

| 탐색 방법 | 시간복잡도 | 정렬 필요 | |-----------|------------|-----------| | 순차 탐색 | O(n) | X | | 이진 탐색 | O(log n) | O |

💻 구현 방법

1. 재귀 구현

int binarySearch(int key, int low, int high) {
    if (low <= high) {
        int mid = (low + high) / 2;
        
        if (key == arr[mid]) {
            return mid;  // 탐색 성공
        } else if (key < arr[mid]) {
            return binarySearch(key, low, mid - 1);  // 왼쪽 탐색
        } else {
            return binarySearch(key, mid + 1, high);  // 오른쪽 탐색
        }
    }
    return -1;  // 탐색 실패
}

2. 반복 구현

int binarySearch(int key, int low, int high) {
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (key == arr[mid]) {
            return mid;
        } else if (key < arr[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;  // 탐색 실패
}

🎯 파라메트릭 서치 (Parametric Search)

개념

최적화 문제를 결정 문제로 변환하여 이진 탐색으로 해결하는 기법입니다.

특징:

"예" 또는 "아니오"로 답할 수 있는 문제
특정 조건을 만족하는 최적값 찾기

예시: 떡볶이 떡 만들기

문제

떡의 높이: [19, 15, 10, 17]
요청 길이: 6cm
절단기 높이 H를 설정하면 H보다 긴 떡은 잘림
최소 6cm를 얻을 수 있는 최대 H는?

해결 과정

Step 1: 시작: 0, 끝: 19, 중간: 9

잘린 떡: (19-9) + (15-9) + (10-9) + (17-9) = 24
24 \u003e 6 → 더 높게 자를 수 있음 → 오른쪽 탐색

Step 2: 시작: 10, 끝: 19, 중간: 14

잘린 떡: (19-14) + (15-14) + (17-14) = 8
8 \u003e 6 → 오른쪽 탐색

Step 3: 시작: 15, 끝: 19, 중간: 17

잘린 떡: (19-17) = 2
2 \u003c 6 → 왼쪽 탐색

Step 4: 시작: 15, 끝: 16, 중간: 15

잘린 떡: (19-15) + (17-15) = 6
정답: 15

구현

int start = 0;
int end = (int) 1e9;
int result = 0;

while (start <= end) {
    long total = 0;
    int mid = (start + end) / 2;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] > mid) {
            total += arr[i] - mid;
        }
    }
    
    if (total < m) {
        end = mid - 1;  // 더 많이 자르기
    } else {
        result = mid;
        start = mid + 1;  // 덜 자르기
    }
}

💡 이진 탐색 활용

언제 사용?

✅ 정렬된 데이터에서 검색 ✅ 탐색 범위가 매우 클 때 (예: 10억) ✅ 파라메트릭 서치 문제

주의사항

❌ 정렬되지 않은 데이터에는 사용 불가 ❌ 정렬 비용 고려 필요 (O(n log n))

❓ 면접 질문 예시

Q1. 이진 탐색이란 무엇인가요?

답변: 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 알고리즘입니다. 중간값과 찾는 값을 비교하여 작으면 왼쪽, 크면 오른쪽을 탐색합니다. 시간복잡도는 O(log n)으로 매우 효율적입니다.

Q2. 이진 탐색의 시간복잡도가 O(log n)인 이유는?

답변: 매 단계마다 탐색 범위가 절반으로 줄어들기 때문입니다. n개의 데이터를 k번 반복하면 n/2^k = 1이 되고, 이를 정리하면 k = log₂n이 됩니다. 따라서 시간복잡도는 O(log n)입니다.

Q3. 이진 탐색을 사용할 수 없는 경우는?

답변: 데이터가 정렬되어 있지 않은 경우입니다. 이진 탐색은 정렬된 데이터를 전제로 하므로, 정렬되지 않은 데이터에는 순차 탐색을 사용하거나 먼저 정렬해야 합니다. 단, 정렬 비용(O(n log n))을 고려해야 합니다.

Q4. 파라메트릭 서치란 무엇인가요?

답변: 최적화 문제를 결정 문제("예" 또는 "아니오")로 변환하여 이진 탐색으로 해결하는 기법입니다. 특정 조건을 만족하는 최적값을 찾을 때 사용하며, 탐색 범위가 매우 클 때 효과적입니다. 예를 들어, "이 높이로 자르면 조건을 만족하는가?"를 반복적으로 확인하여 최적 높이를 찾습니다.

Q5. 재귀와 반복 구현의 차이는?

답변: 재귀 구현은 코드가 간결하지만 함수 호출 오버헤드와 스택 메모리를 사용합니다. 반복 구현은 코드가 조금 더 길지만 메모리 효율적이고 스택 오버플로우 위험이 없습니다. 일반적으로 반복 구현이 성능 면에서 유리합니다.

📚 원본 참고 자료

출처: 2023-CS-Study

링크: algorithm_binary_search.md
내용: 이진 탐색, 파라메트릭 서치, 예시 문제

CS Wiki

탐색 알고리즘