icon

안동민 개발노트

12장: 그리디, 백트래킹, 문자열

그리디 알고리즘과 정당성 증명 방식

그리디는 코드가 짧아서 쉬워 보이지만, 검증이 가장 중요한 알고리즘입니다. 지금 제일 좋아 보이는 선택이 끝까지 맞는지 증명하지 못하면 반례 하나로 바로 무너집니다. 그래서 그리디는 구현보다 정당성 설명이 우선입니다.

여기서는 선택 규칙을 세우는 법과 반례로 검증하는 법을 함께 다룹니다. 교환 논증 같은 증명 틀을 따라갈 수 있게 쉬운 문장으로 정리했습니다. 목표는 감으로 푸는 그리디를 결정 배경 기반 풀이로 바꾸는 것입니다.

규칙 채택/폐기 판단 맵

핵심 개념: 그리디 선택과 정당성

그리디는 구현보다 규칙과 증명을 우선 고정해야 안전합니다. 현재 문제에서 매 단계 무엇을 고를지를 한 문장으로 우선 써 보세요.

그리디 선택 규칙은 매 단계에서 후보를 고르는 기준입니다. 지역 최적 선택을 반복해 전역 최적해를 만들 수 있다는 가정 위에서 동작합니다. 회의실 배정에서 가장 빨리 끝나는 회의부터 선택 규칙이 대표적인 예시입니다.

교환 논증은 현재 선택 규칙이 최적해를 망치지 않음을 증명하는 방법입니다. 임의의 최적해를 선택 규칙을 따르는 형태로 바꿔도 최적성이 유지되는지 확인합니다. 첫 회의를 종료 시간이 가장 빠른 회의로 교체해도 이후 선택 가능한 회의 수가 줄지 않음을 보이는 방식이 전형적입니다.

반례 검증은 규칙이 깨지는 입력을 일부러 만들어 보는 절차입니다. 경계값, 역정렬, 동점 케이스에서 규칙이 실패하지 않는지 확인해 정당성을 보강합니다. 길이가 가장 짧은 회의부터 선택 같은 규칙이 실패하는 입력을 찾으면 잘못된 규칙을 빠르게 배제할 수 있습니다.

그리디 선택이 실무에서 중요한 이유

그리디는 맞으면 빠르고 구현이 간결합니다. 하지만 반례 하나면 알고리즘 전체가 무효가 됩니다. DP처럼 모든 상태를 보지 않기 때문에 증명 없는 그리디는 재사용성이 거의 없습니다.

실무에서도 같은 문제가 제약만 바뀌어 재등장하므로 정당성 구조를 설명할 수 있어야 수정이 가능합니다.

선택 규칙 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

회의실 배정 그리디를 짧은 예제로 따라가 봅니다.

  • 구간: (1,4), (2,3), (3,5), (5,7)
  1. 종료 시간 오름차순으로 정렬합니다.
  2. 가장 먼저 끝나는 구간을 선택합니다.
  3. 이후 시작 시간이 현재 종료 시간 이상인 구간만 채택합니다.
  4. 이 규칙이 반례 없이 유지되는지 교환 논증으로 확인합니다.

교환 논증 기반 그리디 적용 기준

아래 조건이 보이면 그리디 후보로 검토합니다.

  • 지역 선택이 전역 최적해로 이어질 가능성이 높다.
  • 선택 이후 남은 문제가 동일 구조를 유지한다.
  • 교환 논증 또는 cut property를 구성할 수 있다.
  • 반례 탐색에서 규칙이 안정적으로 유지된다.

조건을 만족하지 않으면 DP/그래프 탐색을 우선 비교해야 합니다.

그리디: 회의실 배정(종료 시간 기준)

문제 의도: 종료 시간 기준 그리디가 왜 최적해를 만드는지 확인합니다.
입력 예시: 여러 회의 구간 (start, end)
출력 예시: 선택 가능한 최대 회의 수/목록

main.cpp
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

bool byEndThenStart(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.second != b.second) {
        return a.second < b.second;
    }
    return a.first < b.first;
}

vector<pair<int, int>> intervalScheduling(vector<pair<int, int>> intervals) {
    sort(intervals.begin(), intervals.end(), byEndThenStart);

    vector<pair<int, int>> selected;
    long long end = -(1LL << 60);
    for (const auto& interval : intervals) {
        int s = interval.first;
        int e = interval.second;
        if (s >= end) {
            selected.push_back({s, e});
            end = e;
        }
    }
    return selected;
}

int main() {
    vector<pair<int, int>> meetings = {{1,4}, {2,3}, {3,5}, {0,7}, {5,6}, {8,9}};
    auto ans = intervalScheduling(meetings);
    for (const auto& interval : ans) {
        cout << "(" << interval.first << ", " << interval.second << ") ";
    }
    cout << "\n" << ans.size() << "\n";
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    static List<int[]> intervalScheduling(List<int[]> intervals) {
        intervals.sort((a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        List<int[]> selected = new ArrayList<>();
        long end = Long.MIN_VALUE / 4;
        for (int[] it : intervals) {
            int s = it[0], e = it[1];
            if (s >= end) {
                selected.add(new int[]{s, e});
                end = e;
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        List<int[]> meetings = new ArrayList<>(List.of(
            new int[]{1,4}, new int[]{2,3}, new int[]{3,5},
            new int[]{0,7}, new int[]{5,6}, new int[]{8,9}
        ));
        List<int[]> ans = intervalScheduling(meetings);
        for (int[] p : ans) System.out.print("(" + p[0] + ", " + p[1] + ") ");
        System.out.println();
        System.out.println(ans.size());
    }
}
main.py
def end_then_start(interval):
    return (interval[1], interval[0])

def interval_scheduling(intervals):
    ordered = intervals[:]
    ordered.sort(key=end_then_start)
    selected = []
    end = -10**18

    for s, e in ordered:
        if s >= end:
            selected.append((s, e))
            end = e

    return selected

meetings = [(1, 4), (2, 3), (3, 5), (0, 7), (5, 6), (8, 9)]
ans = interval_scheduling(meetings)
print(ans)
print(len(ans))
# 출력 예시
# [(2, 3), (3, 5), (5, 6), (8, 9)]
# 4
main.rs
fn by_end_then_start(a: &(i32, i32), b: &(i32, i32)) -> std::cmp::Ordering {
    let end_order = a.1.cmp(&b.1);
    if end_order != std::cmp::Ordering::Equal {
        return end_order;
    }
    a.0.cmp(&b.0)
}

fn interval_scheduling(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    intervals.sort_by(by_end_then_start);
    let mut selected = Vec::new();
    let mut end = i64::MIN / 4;
    for (s, e) in intervals {
        if (s as i64) >= end {
            selected.push((s, e));
            end = e as i64;
        }
    }
    selected
}

fn main() {
    let meetings = vec![(1, 4), (2, 3), (3, 5), (0, 7), (5, 6), (8, 9)];
    let ans = interval_scheduling(meetings);
    println!("{:?}", ans);
    println!("{}", ans.len());
}

종료 시각 우선 채택 선정 배경

종료 시간이 가장 빠른 구간을 우선 선택하면 남은 구간에 사용할 수 있는 시간 공간이 최대화됩니다. 교환 논증으로도 증명할 수 있습니다. 최적해의 첫 구간이 더 늦게 끝난다면, 이를 더 빨리 끝나는 구간으로 바꿔도 선택 가능한 개수는 줄지 않습니다.

  • 평균 시간복잡도: O(N log N)
  • 최악 시간복잡도: O(N log N)
  • 공간복잡도: O(N) (선택 결과 저장 포함)

그리디: 활동 선택 실패사례 점검(잘못된 규칙)

문제 의도: 그럴듯하지만 틀린 그리디 규칙을 반례로 빠르게 배제합니다.
입력 예시: 길이 짧은 구간 우선 선택이 실패하는 케이스
출력 예시: 잘못된 규칙 결과 vs 정답 규칙 결과

main.cpp
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

bool byLengthThenEnd(const pair<int, int>& a, const pair<int, int>& b) {
    int la = a.second - a.first;
    int lb = b.second - b.first;
    if (la != lb) {
        return la < lb;
    }
    return a.second < b.second;
}

vector<pair<int, int>> pickByShortestLength(vector<pair<int, int>> intervals) {
    sort(intervals.begin(), intervals.end(), byLengthThenEnd);

    vector<pair<int, int>> chosen;
    for (const auto& interval : intervals) {
        int s = interval.first;
        int e = interval.second;
        bool ok = true;
        for (const auto& selected : chosen) {
            int cs = selected.first;
            int ce = selected.second;
            if (!(e <= cs || ce <= s)) {
                ok = false;
                break;
            }
        }
        if (ok) chosen.push_back({s, e});
    }
    return chosen;
}

int main() {
    vector<pair<int, int>> data = {{1,10}, {1,3}, {3,5}, {5,7}, {7,9}};
    auto ans = pickByShortestLength(data);
    for (const auto& interval : ans) {
        cout << "(" << interval.first << ", " << interval.second << ") ";
    }
    cout << "\n";
    return 0;
}
Main.java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<int[]> pickByShortestLength(List<int[]> intervals) {
        intervals.sort((a, b) -> {
            int la = a[1] - a[0], lb = b[1] - b[0];
            if (la != lb) return Integer.compare(la, lb);
            return Integer.compare(a[1], b[1]);
        });

        List<int[]> chosen = new ArrayList<>();
        for (int[] it : intervals) {
            int s = it[0], e = it[1];
            boolean ok = true;
            for (int[] c : chosen) {
                int cs = c[0], ce = c[1];
                if (!(e <= cs || ce <= s)) {
                    ok = false;
                    break;
                }
            }
            if (ok) chosen.add(new int[]{s, e});
        }
        return chosen;
    }

    public static void main(String[] args) {
        List<int[]> data = new ArrayList<>(List.of(
            new int[]{1,10}, new int[]{1,3}, new int[]{3,5}, new int[]{5,7}, new int[]{7,9}
        ));
        List<int[]> ans = pickByShortestLength(data);
        for (int[] x : ans) System.out.print("(" + x[0] + ", " + x[1] + ") ");
        System.out.println();
    }
}
main.py
def length_then_end(interval):
    return (interval[1] - interval[0], interval[1])

def pick_by_shortest_length(intervals):
    # 잘못된 그리디 후보: 길이가 가장 짧은 구간 우선
    ordered = intervals[:]
    ordered.sort(key=length_then_end)
    chosen = []

    for s, e in ordered:
        ok = True
        for cs, ce in chosen:
            if not (e <= cs or ce <= s):
                ok = False
                break
        if ok:
            chosen.append((s, e))

    return chosen

case = [(1, 10), (1, 3), (3, 5), (5, 7), (7, 9)]
print(pick_by_shortest_length(case))
# 출력 예시: 규칙에 따라 최적보다 적은 개수를 고를 수 있음
main.rs
fn by_length_then_end(a: &(i32, i32), b: &(i32, i32)) -> std::cmp::Ordering {
    let la = a.1 - a.0;
    let lb = b.1 - b.0;
    let len_order = la.cmp(&lb);
    if len_order != std::cmp::Ordering::Equal {
        return len_order;
    }
    a.1.cmp(&b.1)
}

fn pick_by_shortest_length(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    intervals.sort_by(by_length_then_end);

    let mut chosen = Vec::new();
    for (s, e) in intervals {
        let mut ok = true;
        for &(cs, ce) in &chosen {
            if !(e <= cs || ce <= s) {
                ok = false;
                break;
            }
        }
        if ok {
            chosen.push((s, e));
        }
    }
    chosen
}

fn main() {
    let data = vec![(1, 10), (1, 3), (3, 5), (5, 7), (7, 9)];
    println!("{:?}", pick_by_shortest_length(data));
}

실패사례 기반 규칙 폐기 선정 배경

구간 길이가 짧다는 직관은 그럴듯하지만 전역 최적을 보장하지 못합니다. 이 반례 점검은 그리디 규칙을 확정하기 전에 반드시 수행해야 하는 검증 단계입니다.

즉, 그리디는 아이디어보다 증명 가능성이 우선입니다.

  • 평균 시간복잡도: 정렬 O(N log N) + 겹침 검사 O(N^2)
  • 공간복잡도: O(N)

그리디: 최소 동전 개수(그리디 실패 사례)

문제 의도: 동전 체계에 따라 그리디가 실패할 수 있음을 DP와 비교해 확인합니다.
입력 예시: coins=[1,3,4], amount=6
출력 예시: 그리디 3, DP 2

main.cpp
#include <algorithm>
#include <iostream>
#include <optional>
#include <vector>
using namespace std;

optional<int> greedyCoinCount(int amount, vector<int> coins) {
    sort(coins.rbegin(), coins.rend());
    int used = 0, remain = amount;
    for (int c : coins) {
        if (remain >= c) {
            int k = remain / c;
            used += k;
            remain -= c * k;
        }
    }
    if (remain != 0) return nullopt;
    return used;
}

optional<int> dpCoinCount(int amount, const vector<int>& coins) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; ++x) {
        for (int c : coins) {
            if (x >= c) dp[x] = min(dp[x], dp[x - c] + 1);
        }
    }
    if (dp[amount] == INF) return nullopt;
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    cout << *greedyCoinCount(amount, coins) << "\n";
    cout << *dpCoinCount(amount, coins) << "\n";
    return 0;
}
Main.java
import java.util.Arrays;

public class Main {
    static Integer greedyCoinCount(int amount, int[] coins) {
        int[] c = coins.clone();
        Arrays.sort(c);
        int used = 0, remain = amount;
        for (int i = c.length - 1; i >= 0; i--) {
            if (remain >= c[i]) {
                int k = remain / c[i];
                used += k;
                remain -= c[i] * k;
            }
        }
        return remain == 0 ? used : null;
    }

    static Integer dpCoinCount(int amount, int[] coins) {
        int INF = 1_000_000_000;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int x = 1; x <= amount; x++) {
            for (int c : coins) {
                if (x >= c) dp[x] = Math.min(dp[x], dp[x - c] + 1);
            }
        }
        return dp[amount] == INF ? null : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        System.out.println(greedyCoinCount(amount, coins));
        System.out.println(dpCoinCount(amount, coins));
    }
}
main.py
def greedy_coin_count(amount, coins):
    ordered = coins[:]
    ordered.sort(reverse=True)
    used = 0
    remain = amount

    for c in ordered:
        if remain >= c:
            k = remain // c
            used += k
            remain -= c * k

    return used if remain == 0 else None

def dp_coin_count(amount, coins):
    INF = 10**9
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for c in coins:
            if x >= c:
                dp[x] = min(dp[x], dp[x - c] + 1)

    return dp[amount] if dp[amount] != INF else None

coins = [1, 3, 4]
amount = 6
print(greedy_coin_count(amount, coins))
print(dp_coin_count(amount, coins))
# 출력
# 3   (4+1+1)
# 2   (3+3)
main.rs
fn greedy_coin_count(amount: usize, mut coins: Vec<usize>) -> Option<usize> {
    coins.sort();
    coins.reverse();
    let mut used = 0usize;
    let mut remain = amount;
    for c in coins {
        if remain >= c {
            let k = remain / c;
            used += k;
            remain -= c * k;
        }
    }
    if remain == 0 { Some(used) } else { None }
}

fn dp_coin_count(amount: usize, coins: &[usize]) -> Option<usize> {
    let inf = usize::MAX / 4;
    let mut dp = vec![inf; amount + 1];
    dp[0] = 0;
    for x in 1..=amount {
        for &c in coins {
            if x >= c {
                dp[x] = dp[x].min(dp[x - c].saturating_add(1));
            }
        }
    }
    if dp[amount] == inf { None } else { Some(dp[amount]) }
}

fn main() {
    let coins = vec![1, 3, 4];
    let amount = 6;
    println!("{:?}", greedy_coin_count(amount, coins.clone()));
    println!("{:?}", dp_coin_count(amount, &coins));
}

동전 체계별 방식 선정 배경

동전 체계에 따라 그리디는 최소 개수를 보장하지 않습니다. canonical coin system(예: 일반 화폐 체계)에서는 동작할 수 있지만 임의 동전 집합에서는 반례가 쉽게 나옵니다. 그래서 동전 문제는 그리디를 기본값으로 두기 전에 체계 조건을 우선 확인해야 합니다.

  • 시간복잡도: 그리디 O(K log K), DP O(K * amount)
  • 공간복잡도: 그리디 O(1), DP O(amount)

성능/정확성 비용 상쇄 지점

그리디 설계의 균형점은 아래와 같습니다.

  • 장점: 구현이 짧고 빠름
  • 단점: 증명 실패 시 전체 무효
  • 장점: 실시간 의사결정 문제에 적합
  • 단점: 제약 변경에 민감

문제마다 빠른 근사인지 정확 최적인지 목표를 분리해야 합니다.

선택 과정 로그 실수 포인트

그리디 구현에서 자주 발생하는 실수입니다.

  • 정렬 키를 목적 함수와 무관하게 선택
  • 동점 처리 규칙 미정의
  • 증명 없이 샘플 통과만으로 규칙 확정
  • 반례 탐색을 하지 않고 제출

반례 테스트에는 작은 입력, 경계 입력, 동점 다량 케이스를 포함하세요.

그리디 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 적용 관점을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

예제평균 시간최악 시간공간
회의실 배정O(N log N)O(N log N)O(N)
길이 기준 선택(반례용)O(N^2)O(N^2)O(N)
동전 그리디O(K log K)O(K log K)O(1)

복잡도가 낮아도 증명에 실패하면 채택할 수 없다는 점이 그리디의 핵심입니다.

교환 논증 누락 방지 포인트

  • 그리디 규칙은 코드보다 우선 자연어로 명확히 적어야 합니다.
  • 증명 문단과 반례 문단을 함께 관리하면 회귀 실수를 줄일 수 있습니다.
  • 온라인 저지에서는 정답 보장 여부를 문제에서 직접 확인해야 합니다.
  • 프로덕션 코드에서는 규칙 변경 가능성을 고려해 정렬 키를 상수화하는 편이 좋습니다.

그리디 구현 전후 점검 목록

  • 선택 규칙의 정당성(교환 논증 등)을 설명할 수 있는가
  • 반례 입력으로 규칙의 안전성을 검증했는가
  • 동점/경계 구간 처리 기준을 명확히 고정했는가
  • 그리디 실패 가능 문제는 DP/탐색 대안을 비교했는가

그리디 정당성 정리

그리디는 빠른 알고리즘이 아니라 증명 가능한 선택 규칙입니다. 선택, 증명, 반례 점검까지 한 세트로 다루면 짧은 코드로도 높은 신뢰도를 확보할 수 있습니다.

공간 최적화, 경로 복원, DP 디버깅 절차

이전 페이지

백트래킹과 가지치기 전략 설계

다음 페이지

목차

규칙 채택/폐기 판단 맵
핵심 개념: 그리디 선택과 정당성
그리디 선택이 실무에서 중요한 이유
선택 규칙 오답 재현으로 검증하기
교환 논증 기반 그리디 적용 기준
그리디: 회의실 배정(종료 시간 기준)
종료 시각 우선 채택 선정 배경
그리디: 활동 선택 실패사례 점검(잘못된 규칙)
실패사례 기반 규칙 폐기 선정 배경
그리디: 최소 동전 개수(그리디 실패 사례)
동전 체계별 방식 선정 배경
성능/정확성 비용 상쇄 지점
선택 과정 로그 실수 포인트
그리디 비용 모델 정리
교환 논증 누락 방지 포인트
그리디 구현 전후 점검 목록
그리디 정당성 정리