탐욕 알고리즘의 선택 기준과 최적성 검증

매 순간의 선택이 전체 해로 이어지는 조건

탐욕법(Greedy Algorithm)은 해 공간 전체를 탐색하지 않고, 현재 상태에서 가장 이득이 큰 선택을 이어 붙이는 알고리즘 패러다임이다. 빠르게 해를 구성할 수 있다는 장점만으로 적용할 수는 없다. 국소 선택이 전역 최적해로 이어지는지부터 확인해야 한다.

이 판단에는 Greedy-choice property(탐욕 선택 성질)와 Optimal substructure(최적 부분 구조)가 필요하다. 교환 논증(exchange argument)으로 선택의 정당성을 보이거나, 매트로이드(matroid) 구조를 통해 일반적인 정당성을 확인할 수 있다. 조건이 성립하지 않으면 탐욕법은 근사 또는 휴리스틱으로 다뤄야 한다.

⤢✕

후보를 정의한 뒤 정렬 또는 우선순위 평가를 수행하고, 제약을 만족하는 후보만 반복적으로 선택한다. 이 과정에서는 제약이 명확히 정의됐는지, 같은 우선순위의 후보를 어떻게 처리할지, 음수 가중치처럼 특정 알고리즘의 전제를 깨는 입력이 없는지를 함께 점검해야 한다. 선택된 해가 계속 제약을 만족하고 상태 갱신이 일관되게 이뤄지는 것이 불변식이다.

선택 기준과 자료구조를 함께 설계한다

탐욕 기준은 목적함수와 제약에서 출발한다. 간격 스케줄링에서는 종료 시간이 이른 작업을, 최소 신장 트리에서는 가중치가 낮은 간선을 우선할 수 있다. 우선순위가 같은 경우의 처리 규칙도 명시해야 한다. 예를 들어 종료 시간이 같다면 더 짧은 작업을 우대하는 식이다.

정당성은 구현 뒤가 아니라 설계 단계에서 검증한다. 탐욕 선택 성질과 최적 부분 구조를 확인하고, 교환 논증으로 현재 선택을 포함하는 최적해로 바꿀 수 있는지 살핀다. 매트로이드 구조라면 더 일반적인 정당성 근거가 된다.

계산 구조는 보통 정렬 O(n log n)과 우선순위 큐·힙 O(log n) 연산에 기반한다. Kruskal에는 Union-Find, 다익스트라에는 min-heap, 허프만 코딩에는 빈도 힙처럼 문제에 맞는 자료구조를 붙인다. 각 후보 선택에서 제약 위배 여부를 상수~로그 시간에 판단할 수 있도록 상태를 구성하는 편이 낫다. MST에서는 선택한 간선이 사이클을 만들지 않아야 하고, 분할 배낭에서는 용량 제약이 유지돼야 한다.

네트워크와 데이터 처리에서의 적용 방식

최소 신장 트리(MST)는 네트워크 비용을 줄이는 대표적인 사례다. Kruskal은 간선을 가중치 순으로 정렬한 뒤 사이클을 만들지 않는 간선을 고르고, Prim은 프런티어에서 가장 낮은 가중치의 간선을 확장한다. 데이터센터 L2/L3 백본, 전력망·광망 구축, 클러스터 토폴로지 비용 절감에 적용할 수 있다.

다익스트라 알고리즘은 거리 배열을 초기화하고 최소 거리 노드를 확정한 다음 인접 간선을 반복 이완한다. 음수 가중치가 없다는 전제가 필요하다. 네트워크 QoS 경로, 맵·물류 최단 경로, 선행 제약이 있는 작업 스케줄의 경로 비용 평가가 적용 대상이다.

허프만 코딩은 빈도 기반 min-heap에서 항목을 병합해 이진 트리를 만들고, 가변 길이 코드를 부여한다. 로그 압축, 메시지 큐 페이로드 축소, CDN 전송 비용 절감에 활용된다.

간격 스케줄링과 광고 슬롯 할당에서는 종료 시간이 빠른 활동부터 선택해 겹치지 않는 일정을 구성한다. 회의실·서버 슬롯 배정, 스토리지 I/O 윈도 스케줄, 광고 인벤토리 효율화가 이 패턴에 해당한다.

다른 최적화 방식과의 경계

방법	최적성 보장	시간 복잡도 경향	확장성(대규모)	구현 난이도	메모리 요구
탐욕법	문제에 따라 보장/비보장, 증명 필요	O(n log n) 또는 O((V+E) log V)	높음	낮음~중간	낮음
동적 계획법	보장(정의가능 시)	상태 수×전이 비용	중간(상태 폭발 위험)	중간~높음	중~높음
백트래킹/완전탐색	보장	지수 시간	낮음	중간	중간
근사/휴리스틱	비보장(성능 경계 존재 가능)	다양	높음	낮음	낮음

최적성을 증명할 수 있고 정렬이나 힙으로 구현할 수 있다면 탐욕법을 우선 검토할 수 있다. 반대로 음수 가중치나 비표준 동전 시스템처럼 탐욕 선택이 최적해를 놓칠 수 있는 문제라면 DP 또는 근사 방식을 검토해야 한다.

간격 스케줄링으로 보는 구현

환경과 전제는 Python 3.10+ 및 표준 라이브러리다. 아래 코드는 최대 비겹침 활동 수를 구한다.

from typing import List, Tuple

def interval_scheduling(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    # 입력 검증
    for s, f in intervals:
        if f < s:
            raise ValueError(f"잘못된 구간: 시작({s}) > 종료({f})")
    # 종료 시간 기준 오름차순 정렬
    intervals_sorted = sorted(intervals, key=lambda x: x[1])
    result: List[Tuple[int, int]] = []
    last_finish = float("-inf")
    for s, f in intervals_sorted:
        if s >= last_finish:
            result.append((s, f))
            last_finish = f
    return result

if __name__ == "__main__":
    # 예시 입력: (시작, 종료)
    jobs = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
    selected = interval_scheduling(jobs)
    print("선택된 활동:", selected)
    # 출력 예: 선택된 활동: [(1, 4), (5, 7), (8, 11)]

정렬에 O(n log n), 선택 과정에 O(n)이 든다. 종료 시간이 같을 때는 임의로 선택해도 최적이며, 이는 교환 논증으로 설명할 수 있다.

빠른 해법을 운영에 올리기 전 확인할 점

정렬·힙 기반 탐욕 설계는 대규모 입력에서 DP 대비 평균 320배 속도 개선을 제공할 수 있으며, 문제 특성에 따라 달라진다. 메모리는 상수저차수 수준으로 유지돼 캐시 친화적으로 실행할 수 있다. 구현과 검증 비용을 줄이고, 장애 또는 디그레이드 상황에서 휴리스틱으로 전환하기도 쉽다.

적용 전에는 목적함수와 제약, 후보 집합을 먼저 모델링한다. 이어 우선순위 함수, 동률 규칙, 제약 판별 함수를 정하고 탐욕 선택 성질·최적 부분 구조·교환 논증을 검토한다. 정당성이 성립하지 않으면 근사 또는 DP로 전환한다.

테스트에서는 비표준 동전 거스름돈인 동전 {1,3,4}, 금액 6처럼 탐욕법이 실패하는 반례를 확인할 수 있다. 빈 입력, 같은 가중치가 많은 입력, 음수·0 가중치도 경계 조건으로 점검한다. 운영 시에는 선택 횟수, 제약 위배율, 목적값 수렴을 기록한다.

최적성 보장이 필요한 업무라면 증명 없이 배포해서는 안 된다. 규칙 변경이 잦은 환경에서는 우선순위 함수를 구성 가능하게 설계해야 하며, 데이터 노이즈나 드리프트가 있을 때 근사 품질이 낮아질 수 있으므로 재평가 주기도 정해야 한다.