탐색 알고리즘 (Search Algorithms)¶

개요¶

탐색은 데이터에서 원하는 값을 찾는 기본적인 연산입니다. 이 레슨에서는 선형 탐색, 이진 탐색, 파라메트릭 서치, 해시 탐색 등 다양한 탐색 기법을 학습합니다.

목차¶

탐색 알고리즘 비교
선형 탐색
이진 탐색
이진 탐색 변형
파라메트릭 서치
해시 탐색
연습 문제

1. 탐색 알고리즘 비교¶

┌──────────────┬─────────────┬─────────────┬───────────────────┐
│  알고리즘    │ 시간 복잡도 │ 조건        │ 특징              │
├──────────────┼─────────────┼─────────────┼───────────────────┤
│ 선형 탐색    │ O(n)        │ 없음        │ 단순, 범용        │
│ 이진 탐색    │ O(log n)    │ 정렬됨      │ 빠름, 분할정복    │
│ 해시 탐색    │ O(1) 평균   │ 해시 테이블 │ 가장 빠름         │
│ 보간 탐색    │ O(log log n)│ 균등 분포   │ 특수 상황         │
└──────────────┴─────────────┴─────────────┴───────────────────┘

2. 선형 탐색 (Linear Search)¶

원리¶

처음부터 끝까지 순차적으로 검사

배열: [5, 3, 8, 4, 2], 찾는 값: 8

인덱스 0: 5 != 8 → 다음
인덱스 1: 3 != 8 → 다음
인덱스 2: 8 == 8 → 찾음! 인덱스 2 반환

구현¶

// C
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // 못 찾음
}

// C++
int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

// STL
auto it = find(arr.begin(), arr.end(), target);
if (it != arr.end()) {
    int index = distance(arr.begin(), it);
}

# Python
def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

# 내장 함수
# arr.index(target)  # 없으면 ValueError
# target in arr      # 존재 여부만 확인

3. 이진 탐색 (Binary Search)¶

원리¶

정렬된 배열에서 중간값과 비교하여 탐색 범위를 절반씩 줄임

배열: [1, 3, 5, 7, 9, 11, 13], 찾는 값: 9

1단계: left=0, right=6, mid=3
       arr[3]=7 < 9 → left=4

       [1, 3, 5, 7, 9, 11, 13]
                   ↑
                  left

2단계: left=4, right=6, mid=5
       arr[5]=11 > 9 → right=4

       [1, 3, 5, 7, 9, 11, 13]
                   ↑
               left,right

3단계: left=4, right=4, mid=4
       arr[4]=9 == 9 → 찾음! 인덱스 4 반환

구현¶

// C - 반복문
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  // 오버플로우 방지

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

// C - 재귀
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, right, target);
    } else {
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

// C++
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

// STL
#include <algorithm>

// binary_search: 존재 여부만 반환
bool found = binary_search(arr.begin(), arr.end(), target);

// lower_bound: target 이상인 첫 위치
auto it = lower_bound(arr.begin(), arr.end(), target);

// upper_bound: target 초과인 첫 위치
auto it = upper_bound(arr.begin(), arr.end(), target);

# Python
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# bisect 모듈
import bisect

# bisect_left: target 이상인 첫 위치
idx = bisect.bisect_left(arr, target)

# bisect_right: target 초과인 첫 위치
idx = bisect.bisect_right(arr, target)

4. 이진 탐색 변형¶

4.1 Lower Bound (이상인 첫 위치)¶

target 이상인 첫 번째 원소의 인덱스

배열: [1, 2, 4, 4, 4, 6, 8], target=4

lower_bound(4) = 2  (첫 번째 4의 인덱스)
lower_bound(5) = 5  (5보다 크거나 같은 6의 인덱스)
lower_bound(0) = 0  (모든 원소가 0보다 큼)
lower_bound(9) = 7  (없음, 배열 끝)

// C
int lowerBound(int arr[], int n, int target) {
    int left = 0;
    int right = n;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

// C++
int lowerBound(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

# Python
def lower_bound(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

4.2 Upper Bound (초과인 첫 위치)¶

target 초과인 첫 번째 원소의 인덱스

배열: [1, 2, 4, 4, 4, 6, 8], target=4

upper_bound(4) = 5  (4보다 큰 첫 원소 6의 인덱스)
upper_bound(5) = 5  (5보다 큰 첫 원소 6의 인덱스)

특정 값의 개수 = upper_bound - lower_bound
4의 개수 = 5 - 2 = 3

// C
int upperBound(int arr[], int n, int target) {
    int left = 0;
    int right = n;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

// C++
int upperBound(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

# Python
def upper_bound(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left

4.3 회전 정렬 배열 탐색¶

회전된 정렬 배열에서 탐색

원본: [0, 1, 2, 4, 5, 6, 7]
회전: [4, 5, 6, 7, 0, 1, 2]

특징: 둘 중 하나는 항상 정렬됨

// C++
int searchRotated(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        // 왼쪽 부분이 정렬됨
        if (arr[left] <= arr[mid]) {
            if (arr[left] <= target && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 오른쪽 부분이 정렬됨
        else {
            if (arr[mid] < target && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

# Python
def search_rotated(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid

        # 왼쪽 부분이 정렬됨
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽 부분이 정렬됨
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

5. 파라메트릭 서치 (Parametric Search)¶

개념¶

최적화 문제를 결정 문제로 변환하여 이진 탐색으로 해결

"최솟값을 구하라" → "x 이하로 가능한가?"
"최댓값을 구하라" → "x 이상으로 가능한가?"

조건: 답이 단조성(monotonic)을 가져야 함
      - 가능 → 가능 → 가능 → 불가능 → 불가능 (경계 찾기)

예제 1: 랜선 자르기¶

문제: N개의 랜선을 K개의 같은 길이 랜선으로 자를 때,
      최대 길이는?

랜선 길이: [802, 743, 457, 539], K=11

길이 100으로 자르면: 8+7+4+5 = 24개 ≥ 11 (가능)
길이 200으로 자르면: 4+3+2+2 = 11개 ≥ 11 (가능)
길이 201으로 자르면: 3+3+2+2 = 10개 < 11 (불가능)

→ 최대 길이는 200

// C++
bool canMake(const vector<int>& cables, int k, long long length) {
    long long count = 0;
    for (int cable : cables) {
        count += cable / length;
    }
    return count >= k;
}

long long maxCableLength(vector<int>& cables, int k) {
    long long left = 1;
    long long right = *max_element(cables.begin(), cables.end());
    long long answer = 0;

    while (left <= right) {
        long long mid = (left + right) / 2;

        if (canMake(cables, k, mid)) {
            answer = mid;
            left = mid + 1;  // 더 긴 길이 시도
        } else {
            right = mid - 1;
        }
    }

    return answer;
}

# Python
def can_make(cables, k, length):
    count = sum(cable // length for cable in cables)
    return count >= k

def max_cable_length(cables, k):
    left, right = 1, max(cables)
    answer = 0

    while left <= right:
        mid = (left + right) // 2

        if can_make(cables, k, mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

예제 2: 나무 자르기¶

문제: N개의 나무를 높이 H로 자를 때,
      M 미터 이상의 나무를 얻을 수 있는 최대 H는?

나무 높이: [20, 15, 10, 17], M=7

H=15로 자르면: 5+0+0+2 = 7m (가능)
H=16으로 자르면: 4+0+0+1 = 5m < 7 (불가능)

→ 최대 H는 15

# Python
def can_get_wood(trees, m, height):
    wood = sum(max(0, tree - height) for tree in trees)
    return wood >= m

def max_cut_height(trees, m):
    left, right = 0, max(trees)
    answer = 0

    while left <= right:
        mid = (left + right) // 2

        if can_get_wood(trees, m, mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

예제 3: 공유기 설치¶

문제: N개의 집에 C개의 공유기를 설치할 때,
      가장 인접한 두 공유기 사이 최대 거리는?

집 위치: [1, 2, 8, 4, 9], C=3 → 정렬: [1, 2, 4, 8, 9]

거리 3으로 설치: 1, 4, 8 또는 1, 4, 9 (가능)
거리 4로 설치: 1, 8 (2개만 가능, 불가)

→ 최대 거리는 3

// C++
bool canInstall(const vector<int>& houses, int c, int dist) {
    int count = 1;
    int lastPos = houses[0];

    for (int i = 1; i < houses.size(); i++) {
        if (houses[i] - lastPos >= dist) {
            count++;
            lastPos = houses[i];
        }
    }

    return count >= c;
}

int maxMinDistance(vector<int>& houses, int c) {
    sort(houses.begin(), houses.end());

    int left = 1;
    int right = houses.back() - houses.front();
    int answer = 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (canInstall(houses, c, mid)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return answer;
}

# Python
def can_install(houses, c, dist):
    count = 1
    last_pos = houses[0]

    for house in houses[1:]:
        if house - last_pos >= dist:
            count += 1
            last_pos = house

    return count >= c

def max_min_distance(houses, c):
    houses.sort()

    left, right = 1, houses[-1] - houses[0]
    answer = 0

    while left <= right:
        mid = (left + right) // 2

        if can_install(houses, c, mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

6. 해시 탐색¶

개념¶

해시 함수를 사용하여 O(1) 시간에 탐색

키 → 해시 함수 → 해시값(인덱스) → 데이터

예: "apple" → hash("apple") = 3 → arr[3] = 데이터

해시 테이블 사용¶

// C++
#include <unordered_map>
#include <unordered_set>

// 해시 맵 (키-값 쌍)
unordered_map<string, int> map;
map["apple"] = 5;
map["banana"] = 3;

// 탐색 O(1)
if (map.count("apple")) {
    cout << map["apple"] << endl;  // 5
}

// 해시 셋 (키만)
unordered_set<int> set;
set.insert(1);
set.insert(2);

// 존재 확인 O(1)
if (set.count(1)) {
    cout << "Found" << endl;
}

# Python
# 딕셔너리 (해시 맵)
d = {"apple": 5, "banana": 3}

# 탐색 O(1)
if "apple" in d:
    print(d["apple"])  # 5

# 세트 (해시 셋)
s = {1, 2, 3}

# 존재 확인 O(1)
if 1 in s:
    print("Found")

Two Sum 문제 (해시 활용)¶

문제: 배열에서 두 수의 합이 target인 인덱스 쌍 찾기

배열: [2, 7, 11, 15], target=9
답: [0, 1] (2 + 7 = 9)

// C++ - O(n) 해시 풀이
vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // 값 → 인덱스

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];

        if (seen.count(complement)) {
            return {seen[complement], i};
        }

        seen[nums[i]] = i;
    }

    return {-1, -1};
}

# Python
def two_sum(nums, target):
    seen = {}  # 값 → 인덱스

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return [-1, -1]

7. 연습 문제¶

문제 1: 제곱근 구하기¶

정수 x의 제곱근을 정수로 반환하세요 (내림).

입력: 8
출력: 2 (2.828...의 내림)

힌트

mid * mid <= x인 최대 mid 찾기 (이진 탐색)

정답 코드

def sqrt(x):
    if x < 2:
        return x

    left, right = 1, x // 2
    answer = 1

    while left <= right:
        mid = (left + right) // 2

        if mid * mid <= x:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

문제 2: 배열에서 피크 원소 찾기¶

피크 원소: 이웃한 원소들보다 큰 원소

입력: [1, 2, 3, 1]
출력: 2 (인덱스 2의 원소 3이 피크)

힌트

이진 탐색으로 O(log n)에 해결 가능 - mid > mid+1이면 왼쪽에 피크 존재 - mid < mid+1이면 오른쪽에 피크 존재