[알고리즘] 이분 탐색과 탐욕법

두 기법은 무엇을 버리는가

이분 탐색(Binary Search)은 정렬된 배열이나 단조로운 판정 결과에서 가운데 후보를 검사하고, 정답이 존재할 수 없는 절반을 버리는 탐색 기법입니다. 탐색 공간의 크기가 N → N/2 → N/4 → ...로 줄기 때문에 판정 한 번이 O(1)이라면 전체 탐색은 O(log N)입니다.

탐욕법(Greedy Algorithm)은 현재 상태에서 가장 유리하다고 정한 선택 하나를 확정하고 나머지 문제로 넘어가는 설계 기법입니다. 모든 조합을 비교하지 않으므로 빠르지만, 현재의 선택이 전체 최적해를 해치지 않는다는 근거가 반드시 필요합니다.

구분	이분 탐색	탐욕법
줄이는 것	후보 값 또는 인덱스 구간	남은 선택  문제
핵심 전제	정렬 또는 판정 결과의 단조성	탐욕적 선택 속성과 최적 부분 구조
핵심 질문	정답이 어느 쪽에 있는가?	이 선택을 지금 확정해도 되는가?
대표 위험	경계/반복 조건 오류	증명되지 않은 기준을 직감으로 선택

이분 탐색: 정렬된 값에서 절반을 버린다

정렬된 배열 [1, 3, 5, 7, 9, 11, 13]에서 9를 찾는다고 해보겠습니다. 가운데 값 7보다 목표가 크므로 7을 포함한 왼쪽 구간은 모두 버릴 수 있습니다. 남은 구간의 가운데 값 11보다 목표가 작으므로 오른쪽을 버리면 9만 남습니다.

1. left와 right로 아직 확인할 구간을 표현한다.
2. 가운데 인덱스 mid의 값을 목표와 비교한다.
3. 같으면 반환하고, 목표가 크면 왼쪽 절반을, 작으면 오른쪽 절반을 제외한다.
4. 구간이 빌 때까지 반복하고 찾지 못하면 실패를 반환한다.

#include <cstddef>
#include <vector>

int binarySearch(const std::vector<int>& values, int target)
{
    int left = 0;
    int right = static_cast<int>(values.size()) - 1;

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

        if (values[mid] == target)
            return mid;

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

    return -1;
}

(left + right) / 2도 수학적으로는 같지만 두 인덱스의 합이 정수 범위를 넘을 수 있습니다. left + (right - left) / 2는 같은 가운데 값을 구하면서 덧셈 오버플로 위험을 줄입니다. 빈 배열에서는 right가 -1이 되어 반복문에 들어가지 않습니다.

배열을 먼저 정렬해야 한다면 총비용은 O(N log N) 정렬과 O(log N) 탐색입니다. 한 번만 찾는 상황에서는 O(N) 순차 탐색이 더 단순할 수 있고, 같은 데이터에서 여러 번 찾을 때 정렬 비용이 상쇄됩니다.

코드를 외우기보다 구간 불변식을 정한다

이분 탐색의 오류 대부분은 left, right가 무엇을 포함하는지 모호할 때 발생합니다. 반복 내내 참으로 유지할 문장, 즉 구간 불변식을 먼저 정하면 종료 조건과 갱신식이 자연스럽게 결정됩니다.

표현	초기 구간	반복 조건	오른쪽 제거	왼쪽 제거
폐구간	[0, N-1]	left <= right	right = mid - 1	left = mid + 1
반개구간	[0, N)	left < right	right = mid	left = mid + 1

 

폐구간 구현에서 반복 시작 시 정답 후보가 있다면 [left, right] 안에 있습니다. values[mid] < target이면 mid까지는 정답이 아니므로 left = mid + 1로 갱신합니다. 이처럼 한 번의 반복마다 적어도 한 원소를 확실히 제거해야 종료할 수 있습니다.

중요: 폐구간과 반개구간 중 어느 쪽도 더 절대적으로 좋지는 않습니다. 한 구현 안에서 초기값, 반복 조건, 갱신식을 같은 규칙으로 유지하는 것이 중요합니다.

이분 탐색의 진짜 활용: 값이 아니라 경계 찾기

실전에서는 특정 값 하나보다 조건이 바뀌는 첫 위치나 마지막 위치를 찾는 경우가 더 많습니다. 정렬된 배열에서 target 이상인 첫 위치를 찾는 lowerBound가 대표적입니다. 탐색 중 values[mid] >= target이면 mid도 답일 수 있으므로 버리지 않고 right = mid로 좁힙니다.

int lowerBound(const std::vector<int>& values, int target)
{
    int left = 0;
    int right = static_cast<int>(values.size()); // [left, right)

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

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

    return left; // 없다면 values.size()
}

upperBound는 target보다 큰 첫 위치를 찾습니다. 위 코드의 비교를 values[mid] <= target으로 바꾸면 됩니다. 따라서 정렬된 배열에서 특정 값의 개수는 upperBound(target) - lowerBound(target)로 구할 수 있습니다. C++ 표준 라이브러리에는 같은 역할의 std::lower_bound와 std::upper_bound가 있습니다.

값:     1  2  2  2  4  7
인덱스: 0  1  2  3  4  5
            ↑        ↑
       lower(2)=1  upper(2)=4

파라메트릭 서치: 최적화 문제를 결정 문제로 바꾼다

정답 후보 x에 대해 possible(x)를 계산했을 때 결과가 한 번만 바뀐다면 값의 범위에도 이분 탐색을 적용할 수 있습니다. 이런 형태를 흔히 파라메트릭 서치라고 부릅니다. “최댓값을 직접 구하라”는 최적화 문제를 “x가 가능한가?”라는 결정 문제로 바꾸는 것입니다.

x:           1  2  3  4  5  6  7
possible(x): T  T  T  T  F  F  F
                         ↑
                    가능한 최댓값

예를 들어 길이가 긴 랜선일수록 만들 수 있는 조각 수는 같거나 줄어듭니다. 길이 x로 필요한 개수 이상을 만들 수 있는지를 possible(x)로 두면 결과는 true → false로 한 번만 변합니다. 이 단조성이 절반을 안전하게 버릴 수 있는 근거입니다.

long long maxFeasible(long long low, long long high)
{
    long long answer = low - 1;

    while (low <= high)
    {
        const long long mid = low + (high - low) / 2;

        if (possible(mid))
        {
            answer = mid;
            low = mid + 1;      // 더 큰 가능한 값 탐색
        }
        else
        {
            high = mid - 1;
        }
    }

    return answer;
}

반대로 최소 가능한 값을 찾는다면 possible(mid)일 때 답을 저장하고 high = mid - 1로 더 작은 후보를 탐색합니다. 총 시간복잡도는 후보 범위의 크기를 R, 판정 비용을 C라 할 때 O(C log R)입니다. R이 10억이어도 판정은 약 30회, 64비트 양의 범위라도 약 63회면 충분합니다.

문제에서 발견할 수 있는 신호

• 가능한 최대 길이, 최대 거리, 최소 시간처럼 최솟값이나 최댓값을 요구한다.
• “N개 이상 만들 수 있는가?”, “K번 이하로 가능한가?”라는 판정 함수를 만들 수 있다.
• 정답의 값 범위는 매우 크지만 후보 하나를 검사하는 일은 비교적 쉽다.
• 후보를 키우거나 줄일수록 가능 여부가 한 방향으로만 변한다.

신호만 보고 적용해서는 안 됩니다. 예를 들어 가능한 후보가 T, F, T처럼 다시 가능해질 수 있다면 가운데 결과만으로 어느 절반을 버릴지 결정할 수 없습니다. 구현 전에 x가 커질 때 판정 결과가 어느 방향으로 변하는지 문장으로 설명해야 합니다.

이분 탐색에서 자주 발생하는 실수

• 범위가 실제로 줄지 않는다
• 폐구간에서 left = mid나 right = mid를 무심코 사용하면 두 원소가 남았을 때 mid가 반복될 수 있습니다. 후보에서 제외한다면 mid ± 1로 이동합니다.
• 가능한 답을 함께 버린다
• 첫 경계를 찾을 때 조건을 만족한 mid는 답일 수 있습니다. 반개구간의 right = mid처럼 후보를 보존하는 갱신이 필요합니다.
• 최적값을 저장하지 않는다
• 가능한 최댓값을 찾다가 더 큰 후보가 실패해도 직전에 성공한 값이 정답입니다. answer에 저장하거나 종료 후 경계가 정답이 되도록 불변식을 설계합니다.
• 검색 범위와 자료형이 잘못됐다
• 거리 합, 시간, 개수가 int를 넘는지 확인하고 long long을 사용합니다. 가능한 최소·최대 후보도 문제 조건에서 정확히 도출해야 합니다.
• 판정 함수의 단조성을 확인하지 않는다
• 빠른 판정 함수가 있어도 결과가 한 번만 바뀌지 않으면 이분 탐색으로 절반을 버릴 수 없습니다.

탐욕법: 현재 선택 하나를 확정한다

탐욕법은 각 단계에서 지금 가장 좋아 보이는 선택을 하고 이를 되돌리지 않습니다. 구현은 보통 정렬한 뒤 앞에서부터 선택하거나, 우선순위 큐에서 최솟값·최댓값을 반복해서 꺼내는 형태입니다. 하지만 “가장 큰 것부터”, “가장 짧은 것부터”는 탐욕법의 정의가 아니라 문제마다 검증해야 할 후보 규칙일 뿐입니다.

500원, 100원, 50원, 10원 동전으로 1,260원을 만들 때 큰 동전부터 사용하면 500×2 + 100×2 + 50×1 + 10×1, 총 6개가 됩니다.

int money = 1260;
const std::vector<int> coins = {500, 100, 50, 10};
int count = 0;

for (const int coin : coins)
{
    count += money / coin;
    money %= coin;
}

이 규칙은 위 동전 체계에서는 맞지만 모든 동전 집합에서 성립하지 않습니다. 동전이 1원, 3원, 4원이고 6원을 만든다면 큰 동전부터 고를 때 4+1+1로 3개가 필요하지만 최적해는 3+3의 2개입니다. 같은 코드가 입력 체계에 따라 맞기도 하고 틀리기도 한다는 점이 탐욕법의 핵심 위험입니다.

탐욕적 선택이 성립하는 조건과 증명

탐욕적 선택 속성

현재 단계의 탐욕적 선택을 포함하는 최적해가 적어도 하나 존재해야 합니다. 즉 지금의 선택 때문에 앞으로 얻을 수 있는 최적 결과를 잃지 않아야 합니다.

최적 부분 구조

탐욕적 선택을 확정하고 남은 부분도 같은 형태의 더 작은 최적화 문제여야 합니다. 이 성질은 DP에도 등장하지만 두 기법의 대응은 다릅니다. DP는 여러 상태의 결과를 저장하고 비교하는 반면, 탐욕법은 하나의 선택이 안전하다는 증명을 바탕으로 다른 후보를 버립니다.

교환 논증

탐욕법을 증명하는 대표 방법은 임의의 최적해를 하나 잡고 그 선택을 탐욕적 선택으로 바꾸어도 결과가 나빠지지 않음을 보이는 것입니다.

1. 최적해 O가 존재한다고 가정한다.
2. O의 첫 선택이 탐욕적 선택 G와 다르면 둘을 교환한다.
3. 교환해도 유효하고 목적값이 나빠지지 않음을 보인다.
4. 그러면 G를 포함한 최적해도 존재하므로 G를 안전하게 확정할 수 있다.

이 밖에도 탐욕 선택이 항상 다른 선택보다 뒤의 선택 공간을 더 넓게 남긴다는 지배 관계를 보이거나, 각 단계 뒤에 유지되는 불변식을 증명할 수 있습니다. 중요한 것은 예제 몇 개에서 맞았다는 관찰이 아니라 모든 유효 입력에 적용되는 논리입니다.

대표 예제: 회의실 배정

한 회의실에서 서로 겹치지 않게 최대한 많은 회의를 진행하려고 합니다. 가장 일찍 시작하는 회의, 가장 짧은 회의, 가장 빨리 끝나는 회의 중 무엇을 골라야 할까요? 정답은 현재 선택 가능한 회의 중 종료 시간이 가장 빠른 회의입니다.

최적 스케줄의 첫 회의를 O, 가장 빨리 끝나는 회의를 G라고 하겠습니다. G는 O보다 늦게 끝나지 않으므로 최적 스케줄에서 O를 G로 바꿔도 이후 회의들은 그대로 배치할 수 있습니다. 회의 수는 줄지 않습니다. 따라서 G를 포함하는 최적해가 존재하며, G 뒤의 회의에도 같은 논리를 반복할 수 있습니다.

#include <algorithm>
#include <utility>
#include <vector>

int maxMeetingCount(std::vector<std::pair<int, int>> meetings)
{
    std::sort(meetings.begin(), meetings.end(),
        [](const auto& a, const auto& b)
        {
            if (a.second != b.second)
                return a.second < b.second; // 종료 시간
            return a.first < b.first;       // 같은 종료 시간
        });

    int count = 0;
    int lastEnd = 0; // 시간이 음수일 수 있다면 조건에 맞게 초기화

    for (const auto& [start, end] : meetings)
    {
        if (start >= lastEnd)
        {
            ++count;
            lastEnd = end;
        }
    }

    return count;
}

정렬에 O(N log N), 한 번의 순회에 O(N)이므로 전체 시간복잡도는 O(N log N)입니다. “가장 짧은 회의”는 시작 시간이 늦어 앞의 공간을 낭비할 수 있고, “가장 일찍 시작하는 회의”는 매우 늦게 끝나 뒤의 선택을 막을 수 있습니다. 목적함수와 직접 연결되는 기준은 종료 후 남는 공간을 최대화하는 가장 빠른 종료입니다.

이분 탐색과 탐욕법 함께 쓰기: 공유기 설치

집의 좌표가 1, 2, 4, 8, 9이고 공유기 3개를 설치한다고 해보겠습니다. 가장 인접한 두 공유기 사이 거리의 최솟값을 최대화해야 합니다. 어떤 집 조합이 최적인지 직접 고르기는 어렵지만, 거리 후보 d가 주어졌을 때 “모든 공유기 간격을 적어도 d로 설치할 수 있는가?”는 쉽게 판정할 수 있습니다.

1. 이분 탐색할 값과 범위

탐색 대상은 집 인덱스가 아니라 최소 거리입니다. 서로 다른 좌표라면 최소 후보는 1, 최대 후보는 마지막 집 - 첫 집입니다. 공유기가 둘 이상이라는 일반적인 문제 조건을 전제로 합니다.

2. 판정 함수는 탐욕적으로 설치한다

가장 왼쪽 집에 첫 공유기를 놓고, 직전 공유기에서 d 이상 떨어진 첫 번째 집에 다음 공유기를 놓습니다. 더 오른쪽 집을 고르는 것보다 이른 집을 고르는 편이 이후 설치 공간을 좁히지 않습니다. 임의의 유효한 배치가 고른 위치보다 탐욕 배치의 각 공유기 위치가 항상 같거나 왼쪽이라는 불변식을 귀납적으로 보일 수 있으므로, 이 방식은 거리 d에서 설치 가능한 공유기 수를 최대화합니다.

bool canInstall(const std::vector<long long>& houses,
                int requiredRouters,
                long long minimumDistance)
{
    int installed = 1;
    long long lastPosition = houses.front();

    for (std::size_t i = 1; i < houses.size(); ++i)
    {
        if (houses[i] - lastPosition >= minimumDistance)
        {
            ++installed;
            lastPosition = houses[i];

            if (installed >= requiredRouters)
                return true;
        }
    }

    return false;
}

3. 판정 결과는 단조롭다

거리 d로 설치할 수 있다면 그보다 작은 거리로도 같은 배치를 사용할 수 있습니다. 반대로 d로 설치할 수 없다면 더 큰 거리에서도 설치할 수 없습니다. 따라서 판정 결과는 거리가 커질수록 true → false로 한 번만 바뀝니다.

4. 가능한 거리의 최댓값을 찾는다

long long maxMinimumDistance(std::vector<long long> houses,
                             int requiredRouters)
{
    std::sort(houses.begin(), houses.end());

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

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

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

    return answer;
}

집이 N개이고 좌표 범위를 D라 하면 정렬은 O(N log N), 한 번의 판정은 O(N), 판정 횟수는 O(log D)입니다. 전체 시간복잡도는 O(N log N + N log D), 정렬을 제외한 추가 공간은 O(1)입니다.

역할을 분리해 보면 명확합니다. 이분 탐색은 최소 거리 후보를 빠르게 찾고, 탐욕법은 주어진 거리에서 공유기를 최대한 많이 설치해 가능 여부를 정확히 판정합니다.

어떤 기법을 선택할지 판단하는 체크리스트

질문	그렇다면 검토할 기법
정렬된 데이터에서 값이나 첫/마지막 위치를 찾는가?	인덱스 이분 탐색
최적값 후보 x의 가능 여부가 단조로운가?	값 이분 탐색/ 파라메트릭 서치
국소  선택을 포함하는 최적해가 항상 존재함을 증명할 수 있는가?	탐욕법
여러 선택을 비교해야 하고 부분 문제가 반복되는가?	동적 계획법
후보 판정 자체를 가장 이른 위치부터 선택해 최대로 구성할 수 있는가?	이분 탐색 + 탐욕 판정

 

• 무엇을 탐색하는지 한 문장으로 정의한다
• 배열 인덱스인지, 답의 값인지, 첫 가능한 경계인지 명확히 합니다.
• 단조성을 방향까지 적는다
• false → true인지 true → false인지 적으면 어느 경계를 찾아야 할지 드러납니다.
• 구간 표기 하나를 끝까지 지킨다
• 폐구간과 반개구간의 초기값·종료 조건·갱신식을 섞지 않습니다.
• 탐욕 기준에 반례를 시도한다
• 가장 큰 것, 가장 짧은 것 같은 직관이 작은 반례에서도 깨지지 않는지 먼저 확인합니다.
• 교환해도 나빠지지 않음을 증명한다
• 임의의 최적해를 탐욕 선택을 포함하는 해로 바꿀 수 있어야 선택을 확정할 수 있습니다.
• 복잡도를 판정 함수까지 포함해 계산한다
• 파라메트릭 서치는 O(log R)만이 아니라 O(C log R)입니다.

이분 탐색과 탐욕법은 모두 많은 후보를 보지 않고 버린다는 점에서 강력합니다. 그만큼 “왜 버려도 되는가”가 알고리즘의 본체입니다. 이분 탐색에서는 단조성과 구간 불변식이, 탐욕법에서는 교환 논증과 최적 부분 구조가 그 근거가 됩니다. 템플릿을 암기하기 전에 이 근거를 먼저 세우면 경계 조건이 달라져도 안정적으로 구현할 수 있습니다.