[알고리즘 코어 파헤치기] 그리디(Greedy) 완벽 해부 - 탐욕이 정답이 되기 위한 두 가지 조건

학습 철학 회고
그리디 알고리즘은 직관적으로 풀기 쉽다는 함정이 있습니다. "그냥 지금 제일 좋아 보이는 걸 고르면 되는 거 아니야?"라는 생각으로 접근하다가 수많은 반례(Edge Case)에 부딪혀 무너지곤 합니다. 이번에는 감각에 의존하는 코딩을 멈추고, '탐욕'이 수학적인 정답으로 귀결되기 위해 반드시 갖춰야 할 이론적 전제 조건을 뼈대로 세웁니다.

📌 개념 요약: 그리디 알고리즘이란?

미래를 내다보지 않고, "오직 현재 상태에서 가장 최선이라고 생각되는 선택"만을 반복하여 최종 해답에 도달하는 방법론입니다.

하지만 모든 문제에 그리디를 적용할 수는 없습니다. 눈앞의 마시멜로를 당장 먹는 것이 최종적으로는 손해일 수 있기 때문입니다. 따라서 그리디가 완벽한 알고리즘으로 작동하려면 다음 두 가지 절대 조건이 모두 성립해야 합니다.

1. 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 전혀 영향을 주지 않아야 합니다. 즉, 지금의 최적의 선택이 '전체 문제의 최적해'를 무조건 보장해야 합니다.
2. 최적 부분 구조 (Optimal Substructure): DP와 마찬가지로, 전체 문제의 최적해가 부분 문제들의 최적해로 이루어져 있어야 합니다.

💡 동작 원리: "정렬(Sort)"이라는 필수 전제

그리디 알고리즘 자체는 DFS나 이분 탐색처럼 정형화된 코드 템플릿(자료구조)이 존재하지 않습니다. 문제마다 '탐욕의 기준'이 다르기 때문입니다.

하지만 거의 모든 그리디 코딩 테스트 문제에는 공통된 뼈대가 있습니다. 바로 가장 좋은 것을 빠르게 뽑아내기 위해, 데이터를 특정한 기준에 맞춰 '정렬(Sort)'하거나 '우선순위 큐(Min-Heap)'에 담아두고 시작한다는 점입니다.

💻 추상화된 템플릿 로직 (설계 뼈대)

정형화된 코드는 없지만, SOP(설계 주도형 사고) 관점에서 그리디 문제를 마주했을 때 전개해야 하는 사고의 흐름과 뼈대 로직은 다음과 같습니다.

def greedy_template(data):
    # 1. [핵심] 탐욕의 기준 설정 및 정렬
    # (예: 회의가 끝나는 시간이 빠른 순, 무게가 가벼운 순 등)
    data.sort(key=lambda x: (x[1], x[0])) 
    # 또는 heapq.heapify(data) 사용
    
    answer = 0
    current_state = 0 # 현재 상태를 추적할 변수
    
    # 2. 정렬된 데이터를 순회하며 탐욕적 선택 진행
    for item in data:
        # 3. [방어 로직] 현재 아이템이 제약 조건을 만족하는가? (가지치기)
        if is_valid(item, current_state):
            # 4. 선택 및 상태 갱신
            answer += item.value
            current_state = item.end_time # 다음 선택을 위한 상태 업데이트
            
    return answer

🚨 설계 및 회고

• 정당성 증명: 그리디 문제를 풀 때는 코드를 짜기 전에 "반례가 정말 없을까?"를 최소 5분 이상 종이에 그려가며 검증해야 합니다. 만약 동전 거스름돈 문제에서 동전 단위가 배수 관계가 아니라면(예: 100원, 70원, 10원), 가장 큰 동전부터 탐욕적으로 고르는 방식은 오답을 냅니다. 이때는 DP나 BFS로 돌아가야 합니다.
• 우선순위 큐의 결합: 매 순간 변화하는 상황 속에서 계속 최솟값/최댓값을 뽑아야 한다면, 매번 .sort()를 호출하는 대신 $O(\log N)$으로 값을 뽑아주는 heapq를 사용하는 것이 완벽한 그리디 구현체입니다. (예: 백준 1715 카드 정렬하기)