munjjang9
문짱구의 게임 개발 블로그
Game Programmer

탐욕법 (Greedy)

•

전날 내용 요약 — 완전탐색 (Brute Force)

  • 완전탐색은 모든 경우를 다 시도해 정답을 보장하는 전략 — “무식한 방법”이 아닌 “보장된 정답”
  • next_permutation: 반드시 오름차순 정렬 후 사용해야 모든 순열을 얻을 수 있음
  • 조합 재귀에서 start 파라미터로 중복을 막음 — i+1을 넘겨 항상 앞에서 뒤 방향으로만 선택
  • 비트마스크 부분집합: mask & (1 << i)로 i번째 원소 선택 여부 판단, 경우의 수 2^N
  • 시간복잡도 기준: 순열 N ≤ 8, 부분집합 N ≤ 20, 이중반복문 N ≤ 10,000

탐욕법이란?

완전 탐색은 모든 경우를 다 보는 방법이지만 n이 커지면 시간초과가 발생한다.
반면, 탐욕법은 매 순간 현재 시점에서 가장 최선의 선택을 하는 방법이다.

탐욕법을 사용하면 전체 경우를 다 보지 않더라도 최적해에 도달할 수 있다.

탐욕법의 적용 조건

  1. 탐욕 선택 속성 -> 현재의 최선의 선택이 미래에도 최선을 보장하는 경우

  • 예시 (보트 타기) : 가장 무거운 사람과 가장 가벼운 사람을 보트에 태움 -> 이 선택이 나중의 선택에도 여전히 최선

  • 반례 (최소 동전 개수) : 1원, 4원, 6원 동전이 있고 8원을 만들어야 할 때. -> 큰 숫자를 만들기 위한 최선의 선택은 큰 숫자를 고르는 것. 하지만, 6원을 고르면 1원 2개를 골라야 해서 3개의 동전이 필요하다. 4원을 2개 고르는 것이 최선의 선택.

  1. 최적 부분 구조 -> 부분 문제의 최적해가 모여 전체 최적해를 이루는 경우
  • 예시 (짐 싣기) : n개의 짐을 싣는데 필요한 최소 트럭 수 = (첫 번째 짝 선택) + (나머지 n-2개 짐의 최소 트럭 수). 이처럼 작은 문제(n-2개)의 최적해가 전체 최적해에 기여하는 경우.

위 조건들이 성립하지 않으면 탐욕은 오답을 낼 수 있음.

패턴 1 — 정렬 후 순서대로 선택

가장 흔한 탐욕 패턴이다. 기준에 따라 정렬한 뒤 앞에서부터 차례로 선택한다.

예시) 과자 나눠주기 각각 원하는 최소 과자 크기가 있는 어린이들이 있고, 크기 별로 과자가 존재. 이 때 최대 몇 명을 만족시킬 수 있는지를 해결하는 문제.

int assignCookies(vector<int> children, vector<int> cookies) {
    sort(children.begin(), children.end());
    sort(cookies.begin(), cookies.end());

    int child = 0, cookie = 0;
    while (child < (int)children.size() && cookie < (int)cookies.size()) {
        if (cookies[cookie] >= children[child])
            child++;   // 만족 → 다음 어린이로
        cookie++;      // 과자는 무조건 다음으로
    }
    return child;
}

패턴 2 — 양쪽에서 좁혀오기

정렬을 한 후 양 끝 포인터를 이용해 최적 쌍을 선택하는 방법

예시) 한 번에 짐을 최대 두 개까지 싣는 것이 가능한 수레가 있다. 두 짐의 무게 합은 limit을 넘지 않아야 할 때, 필요한 최소 수레의 수는?

int loadWagon(vector<int> weights, int limit) {
    sort(weights.begin(), weights.end());

    int lo = 0, hi = (int)weights.size() - 1;
    int wagons = 0;

    while (lo <= hi) {
        // 가장 가벼운 짐 + 가장 무거운 짐을 같이 실을 수 있으면 같이 싣는다
        if (weights[lo] + weights[hi] <= limit)
            lo++;
        hi--;      // 가장 무거운 짐은 항상 수레 1대 소모
        wagons++;
    }

    return wagons;
}

탐욕 vs 완전탐색 판단법

기준 완전탐색 탐욕
N 크기 작음 (≤ 20) 큼 (≤ 100,000)
정확성 항상 보장 증명/직관 필요
시간복잡도 O(N!), O(2^N) O(N log N) 수준
적용 조건 제한 없음 탐욕 선택 속성 성립 시

판단하는 순서

  1. n이 크면 완전탐색은 불가능 -> 탐욕 or DP를 고려
  2. 정렬 후 순서대로 선택하면 최적인가를 직관적으로 판단
  3. 반례를 하나라도 찾으면 탐욕 불가능 -> DP

시간복잡도

탐욕법 자체는 O(N)이지만, 정렬이 필요하면 O(N log N) 이 된다.

단계 시간복잡도
정렬 O(N log N)
탐욕 선택 (단일 패스) O(N)
전체 O(N log N)

Table of Contents