그리디 알고리즘: 빠른 선택 규칙으로 최적화 문제를 푸는 법

지역 선택이 전역 해로 이어지는 조건

그리디 알고리즘은 현재 후보 중 가장 이득이 큰 선택을 계속 쌓아 해를 만드는 최적화 방법이다. 규칙이 단순하고 실행이 빠르다는 장점이 있지만, 모든 문제에 최적해를 보장하지는 않는다.

최적해가 보장되려면 탐욕 선택 속성과 최적 부분 구조가 함께 성립해야 한다. 교환 논증으로 첫 선택을 어떤 최적해의 선택과 바꿔도 결과가 나빠지지 않음을 보일 수 있어야 하며, 남은 부분문제의 최적해 역시 전체 해 구성에 기여해야 한다. 매트로이드 또는 매트로이드와 유사한 구조에서는 독립집합 확장 성질을 바탕으로 이런 최적성을 증명할 수 있다.

일반적인 흐름은 후보 집합에서 우선순위 기준을 정하고, 선택한 후보가 제약을 만족하는지 확인한 뒤, 불가능한 후보를 제외하며 종료 조건까지 반복하는 방식이다. 구현에서는 정렬이나 우선순위 큐가 자주 쓰인다.

선택 기준은 문제 구조에서 나온다

탐욕 기준은 단일 지표나 순위 함수로 표현된다. 간격 스케줄링에서는 종료 시간이 빠른 구간을, 최소 신장 트리에서는 가중치가 작은 간선을, 다른 문제에서는 여유도가 작은 대상을 우선할 수 있다.

좋은 기준은 현재 후보끼리 비교할 수 있어야 하고, 선택 뒤에도 필요한 불변성을 유지해야 하며, 계산 비용도 감당할 수 있어야 한다. 기준이 그럴듯해 보인다는 사실만으로는 충분하지 않다. 최적해의 첫 선택을 탐욕 선택으로 교체할 수 있는지 확인해야 한다.

부분문제의 최적해가 전체 최적해에 연결되지 않거나 교환 논증에 반례가 있으면, 그리디 방식은 근사 해법으로만 다뤄야 한다. 이때는 근사비 보장 알고리즘을 선택하거나, 매트로이드성을 사전에 검토하고, 작은 인스턴스에서는 정확해 탐색과 함께 운용할 수 있다.

정렬·힙·보조 자료구조로 구성하는 구현

정렬 후 한 번 훑는 패턴은 O(n log n) 정렬과 O(n) 스캔으로 해를 만든다. 후보가 동적으로 변하면 우선순위 큐나 힙을 이용해 O(log n) 삽입·삭제로 다음 대상을 고른다.

문제에 따라 보조 자료구조도 달라진다. Kruskal 알고리즘에는 유니온-파인드가, Dijkstra 알고리즘에는 방문 집합이, Huffman 코딩에는 빈도 힙이 사용된다. 대체로 선형로그 또는 준선형 시간과 낮은 메모리 사용량을 기대할 수 있어 대규모 입력에 적합하다. 다만 DP나 정확 해법보다 계산량과 구현 복잡도가 줄어드는 대신, 최적성 보장은 문제 구조에 달려 있다.

⤢✕

입력은 요소 집합, 제약 조건, 목표 함수로 구성된다. 탐욕 기준을 계산한 뒤 선택·검증·갱신을 반복하며, 후보가 소진되면 중단한다. 타당하지 않은 요소는 즉시 제거하고, 결과로 제약을 만족하는 해 또는 근사해를 얻는다.

다른 최적화 접근과의 차이

접근	성능(시간)	확장성	일관성(최적 보장)	안정성(제약 위반 회피)	운영 편의
Greedy	보통 O(n log n)~O(m log n)	대규모 데이터에 강함	문제 구조 충족 시 보장, 일반적으론 미보장	높은 편, 간단한 롤백/검사 용이	구현 간결, 유지보수 용이
Dynamic Programming	O(n·S)~지수 메모이제이션	상태 수 증가에 취약	보장	높음, 상태 전이로 제어	구현 중간, 메모리 비용 큼
정확 해법(ILP/분지한정)	지수~초다항	대규모에 취약	항상 보장	높음	모델링·튜닝 비용 큼

그리디는 문제 구조가 맞을 때 가장 간결한 선택지가 될 수 있다. 반면 상태 조합 자체가 핵심인 문제는 DP가 적합하고, 최적해가 반드시 필요하다면 ILP나 분지한정 같은 정확 해법을 고려해야 한다.

라우팅부터 압축까지 이어지는 활용 범위

Dijkstra 알고리즘은 비음수 가중치 그래프에서 단일 출발 최단경로를 계산한다. 우선순위 큐 기반으로 O((V+E) log V) 시간에 동작한다. 음수 간선이 있으면 부정확해질 수 있으므로, 발견 시 Bellman–Ford로 전환해야 한다.

Kruskal과 Prim 알고리즘은 간선 가중치 합이 최소인 트리를 구성한다. 선택한 간선이 사이클을 만들지 않도록 관리하며, 통신망과 데이터센터 토폴로지 비용 절감에 적용할 수 있다.

간격 스케줄링에서는 종료 시간이 이른 구간부터 선택해 최대 비충돌 작업 수를 구한다. 회의실 배정, 광고 슬롯 배치, CPU 배치에 활용되며, 사전 정렬과 선형 스캔 방식은 대규모 로그나 캘린더 처리에도 맞는다.

Huffman 코딩은 빈도를 기준으로 항목을 병합해 최소 평균 코드 길이 트리를 만든다. 로그 전송이나 메시지 큐 페이로드 최적화에 사용할 수 있다.

집합 커버, K-센터, 최대 절단 같은 조합 최적화 문제에서는 근사보장 그리디 알고리즘이 활용된다. 서비스 커버리지, 캐시 프리페칭, A/B 실험 리소스 배분도 이런 접근이 실용적인 영역이다.

종료 시간이 빠른 구간을 고르는 코드

Python 3.10+와 표준 라이브러리만 사용하는 예시다.

from typing import List, Tuple

def select_max_non_overlapping(intervals: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    # 입력 검증
    for s, e in intervals:
        if e < s:
            raise ValueError(f"잘못된 구간: start={s}, end={e}")
    # 종료 시간 기준 정렬
    intervals = sorted(intervals, key=lambda x: x[1])
    result = []
    current_end = float('-inf')

    for s, e in intervals:
        if s >= current_end:
            result.append((s, e))
            current_end = e
    return result

if __name__ == "__main__":
    data = [(1, 3), (2, 4), (3, 5), (0, 2), (5, 7), (6, 8)]
    print(select_max_non_overlapping(data))

구간을 종료 시간 오름차순으로 정렬한 뒤, 이전에 선택한 구간과 겹치지 않으면 결과에 추가한다. 시간 복잡도는 O(n log n)이고 추가 공간은 O(1)이다.

사이클을 막으며 최소 신장 트리를 만드는 코드

이 예시는 Python 3.10+ 환경에서 무향 연결 그래프를 가정한다.

class DSU:
    def __init__(self, n: int):
        self.p = list(range(n))
        self.r = [0]*n
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.r[pa] < self.r[pb]:
            pa, pb = pb, pa
        self.p[pb] = pa
        if self.r[pa] == self.r[pb]:
            self.r[pa] += 1
        return True

def kruskal(n: int, edges):
    # edges: (w, u, v)
    edges = sorted(edges)  # 가중치 기준
    dsu = DSU(n)
    mst, total = [], 0
    for w, u, v in edges:
        if dsu.union(u, v):
            mst.append((u, v, w))
            total += w
    if len(mst) != n - 1:
        raise ValueError("그래프가 연결되지 않음")
    return mst, total

if __name__ == "__main__":
    n = 4
    edges = [(1,0,1),(4,0,2),(3,0,3),(2,1,2),(5,2,3)]
    print(kruskal(n, edges))

간선을 가중치 오름차순으로 정렬하고, 사이클을 만들지 않는 간선만 선택한다. 선택된 간선이 n-1개가 되면 최소 신장 트리가 완성되며 시간 복잡도는 O(E log E)이다.

빈도 힙으로 만드는 Huffman 코드

Python 3.10+와 heapq를 사용한다.

import heapq
from collections import Counter

def huffman_codes(s: str):
    freq = Counter(s)
    if len(freq) == 1:
        # 단일 문자 특수처리
        ch = next(iter(freq))
        return {ch: "0"}

    heap = [[w, i, ch] for i, (ch, w) in enumerate(freq.items())]
    heapq.heapify(heap)
    idx = len(heap)

    while len(heap) > 1:
        w1, _, left = heapq.heappop(heap)
        w2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, [w1 + w2, idx, (left, right)])
        idx += 1

    def build_codes(node, prefix, table):
        if isinstance(node, str):
            table[node] = prefix
        else:
            left, right = node
            build_codes(left, prefix + "0", table)
            build_codes(right, prefix + "1", table)
        return table

    _, _, root = heap[0]
    return build_codes(root, "", {})

if __name__ == "__main__":
    s = "aaabbcdddde"
    print(huffman_codes(s))

빈도를 기준으로 최소 힙에서 항목을 병합하고, 만들어진 이진트리를 따라 좌측에는 0, 우측에는 1을 부여한다. 시간 복잡도는 O(k log k)이며, k는 상이한 문자 수다.

속도와 최적성 사이에서 확인할 점

정렬·힙 기반 구현은 DP나 정확해 방식과 비교해 10~100배 수준의 속도 향상을 기대할 수 있고, 데이터 규모가 커질수록 성능 격차도 확대된다. 추가 메모리는 O(1)~O(n) 수준이므로 대규모 스트리밍과 온라인 처리에 적합하다.

문제 구조가 맞으면 최적해를 보장한다. 구조가 맞지 않더라도 집합 커버의 ln n, 0-1 배낭의 1/2 단순 그리디처럼 로그급 또는 상수 근사비를 달성할 수 있다.

운영 전에는 탐욕 선택 속성, 최적 부분 구조, 매트로이드성을 검토하는 편이 좋다. 작은 인스턴스에서는 정확해와 비교하고 반례 유닛테스트를 포함해야 한다. 정렬·힙·유니온-파인드 구현을 표준화하고 입력 검증과 예외 처리를 일관되게 유지하면 검증 비용을 줄일 수 있다.

근사를 허용하면 속도를 높일 수 있지만, 최적성이 필수인 경우에는 다른 기법이 필요하다. 단순한 기준은 해석하기 쉽지만 복합 기준은 정당성 증명이 어려워진다. 온라인 선택은 실시간 의사결정에 유리한 대신 미래 정보를 포함하지 못해 품질이 낮아질 수 있다.