07. Algorithm_Greedy Algorithms and String Matching

그리디 알고리즘이 실패하는 예(이진 트리 경로, 배낭, 동전)와 성공하는 예(MST, 회의실 배정), 그리디의 두 조건과 매트로이드, P와 NP, 문자열 매칭(원시적 매칭, 오토마타, KMP, 라빈-카프). 그리디와 DP, 네 가지 매칭 알고리즘을 실행해 비교

게시 2026/11/05

By younghoonko

24 분읽는 시간

07. Algorithm_Greedy Algorithms and String Matching

학습 목표

그리디 알고리즘의 정의, 장점과 한계
그리디가 최적해를 보장하지 않는 예와 보장하는 예를 코드로 확인
그리디가 성공하기 위한 두 조건과 매트로이드
P, NP, NP-Hard, NP-Complete의 의미
원시적 매칭과 전처리를 쓰는 매칭(오토마타, KMP)
라빈-카프 알고리즘의 수치 비교와 나머지 연산

1. 그리디 알고리즘

현재 시점에서 가장 이득이 되어 보이는 선택을 반복하는 알고리즘.

장점: 단순하고 빠름
단점: 눈앞의 이익만 보다가 큰 그림을 놓쳐 최적해를 보장하지 못할 수 있음
그래서 어떤 기준으로 고르느냐가 성공 여부를 결정함

최적해를 보장하지 않는 예

문제	그리디 기준	실패하는 이유
이진 트리의 최대 합 경로	자식 중 값이 큰 쪽으로 내려감	아래에 어떤 값이 있는지 모르는 채로 결정함
0/1 배낭	가치/무게(가치 밀도)가 큰 물건부터	남은 용량이 낭비될 수 있음 → DP로 풀면 최적
동전 바꾸기	큰 동전부터 최대한	동전 금액이 바로 아래 금액의 배수가 아니면 실패

최적해를 보장하는 예

최소 신장 트리: Prim, Kruskal
최단 경로: Dijkstra (음의 가중치가 없을 때)
회의실 배정: 회의실 하나에 겹치지 않게 가장 많은 회의를 넣을 때

회의실 배정 기준	결과
소요 시간이 짧은 회의 먼저	실패할 수 있음
시작 시간이 이른 회의 먼저	실패할 수 있음
종료 시간이 이른 회의 먼저	항상 최적 (일찍 끝날수록 남은 시간이 많아짐)

실행: 그리디 vs 최적해

  
import itertools, random

# 1) 0/1 배낭: 가치 밀도 그리디 vs DP
def knapsack_greedy(items, cap):
    total, room, chosen = 0, cap, []
    for w, v in sorted(items, key=lambda x: x[1] / x[0], reverse=True):   # 가치/무게 큰 순서
        if w <= room: room -= w; total += v; chosen.append((w, v))
    return total, chosen

def knapsack_dp(items, cap):
    best = [0] * (cap + 1)                       # best[c]: 용량 c로 얻는 최대 가치
    for w, v in items:
        for c in range(cap, w - 1, -1):          # 뒤에서부터 → 각 물건은 한 번만
            best[c] = max(best[c], best[c - w] + v)
    return best[cap]

items = [(10, 60), (20, 100), (30, 120)]         # (무게, 가치), 배낭 용량 50
print("배낭  그리디:", knapsack_greedy(items, 50), "  DP 최적:", knapsack_dp(items, 50))

# 2) 동전 바꾸기: 큰 동전부터 그리디 vs DP
def coin_greedy(coins, W):
    used = {}
    for c in sorted(coins, reverse=True):
        used[c], W = divmod(W, c)
    return sum(used.values()), {c: k for c, k in used.items() if k}

def coin_dp(coins, W):
    INF = float("inf"); dp = [0] + [INF] * W
    for x in range(1, W + 1):
        dp[x] = min((dp[x - c] + 1 for c in coins if c <= x), default=INF)
    return dp[W]

for coins in ([500, 100, 50, 10, 1], [500, 400, 100, 75, 50]):
    print(f"동전 {coins}, 1300원  그리디: {coin_greedy(coins, 1300)}  DP 최소 개수: {coin_dp(coins, 1300)}")

# 3) 회의실 배정: 세 가지 그리디 기준 vs 전수 탐색
def schedule(meetings, key):
    chosen = []
    for s, e in sorted(meetings, key=key):                  # 기준 순서대로 보며
        if all(e <= cs or s >= ce for cs, ce in chosen):    # 이미 고른 회의와 겹치지 않으면 배정
            chosen.append((s, e))
    return len(chosen)

def brute(meetings):
    for r in range(len(meetings), 0, -1):
        for sub in itertools.combinations(sorted(meetings), r):
            if all(sub[i][1] <= sub[i + 1][0] for i in range(r - 1)): return r
    return 0

rules = {"짧은 회의 먼저": lambda m: m[1] - m[0], "일찍 시작 먼저": lambda m: m[0], "일찍 끝남 먼저": lambda m: m[1]}
random.seed(3)
wins = {k: 0 for k in rules}
for _ in range(300):
    ms = []
    for _ in range(8):
        s = random.randint(0, 20); ms.append((s, s + random.randint(1, 8)))
    opt = brute(ms)
    for k, f in rules.items(): wins[k] += schedule(ms, f) == opt
print("회의실 배정: 무작위 300개 사례 중 최적해를 낸 횟수", wins)

# 4) 이진 트리 최대 합 경로: 큰 자식 쪽으로만 내려가는 그리디 vs 전체 탐색
tree = {"root": (7, ["a", "b"]), "a": (5, ["c", "d"]), "b": (3, ["e", "f"]),
        "c": (2, []), "d": (1, []), "e": (4, []), "f": (20, [])}
def greedy_path(n):
    v, ch = tree[n]
    return v + (greedy_path(max(ch, key=lambda c: tree[c][0])) if ch else 0)
def best_path(n):
    v, ch = tree[n]
    return v + (max(best_path(c) for c in ch) if ch else 0)
print("이진 트리 경로  그리디:", greedy_path("root"), "  최적:", best_path("root"))

실행 결과

배낭  그리디: (160, [(10, 60), (20, 100)])   DP 최적: 220
동전 [500, 100, 50, 10, 1], 1300원  그리디: (5, {500: 2, 100: 3})  DP 최소 개수: 5
동전 [500, 400, 100, 75, 50], 1300원  그리디: (5, {500: 2, 100: 3})  DP 최소 개수: 3
회의실 배정: 무작위 300개 사례 중 최적해를 낸 횟수 {'짧은 회의 먼저': 290, '일찍 시작 먼저': 207, '일찍 끝남 먼저': 300}
이진 트리 경로  그리디: 14   최적: 30

배낭: 무게 50짜리 배낭에 밀도 순으로 넣으면 (10, 60), (20, 100)을 넣고 남은 20에 (30, 120)이 안 들어가 160. 최적은 (20, 100) + (30, 120) = 220
동전: 500, 100, 50, 10, 1원처럼 금액이 배수 관계면 그리디가 최적(5개). 500, 400, 100, 75, 50원이면 그리디는 500×2 + 100×3 = 5개지만, 최적은 500 + 400×2 = 3개
회의실 배정: 무작위 300개 사례에서 “일찍 끝남 먼저”만 300번 모두 최적. “짧은 회의 먼저”는 290번, “일찍 시작 먼저”는 207번
이진 트리: 루트(7)에서 큰 자식 a(5)로 가면 7 + 5 + 2 = 14지만, 작은 자식 b(3) 아래에 20이 있어 최적은 7 + 3 + 20 = 30

그리디가 성공하기 위한 두 조건

탐욕적 선택 속성 (Greedy Choice Property): 매 순간의 국소 최적 선택이 항상 전체 최적해의 일부가 됨
최적 부분 구조 (Optimal Substructure): 문제를 부분 문제로 나눠도 같은 구조이고, 부분 문제의 최적해를 모으면 전체의 최적해가 됨

DP도 최적 부분 구조가 필요하지만, 그리디는 여기에 한 번 한 선택을 되돌아보지 않아도 된다는 1번 조건까지 필요함.

매트로이드

그리디 알고리즘으로 최적해가 보장되는 수학적 구조. 문제가 매트로이드 구조면 그리디로 최적해를 얻음
유한 집합 S와 그 부분집합들의 모임 I가 다음을 만족하면 매트로이드
1. 공집합은 I에 속함
2. 유전성: A가 I에 속하면 A의 부분집합도 I에 속함
3. 교환성: A, B가 I에 속하고 A가 B보다 작으면, B에 있고 A에 없는 원소 x 중 \(A \cup \lbrace x \rbrace\)가 I에 속하는 것이 있음
확장: A에 x를 더해도 I에 속하면 x가 A를 확장한다고 함. 더 이상 확장되지 않는 A가 포화 집합
매트로이드의 모든 포화 집합은 크기가 같음
그래픽 매트로이드: 그래프 G의 간선 집합에서 사이클이 없는 간선 집합(숲) 들의 모임은 매트로이드. 포화 집합은 신장 트리이고, Kruskal이 이 구조 위의 그리디라서 MST가 최적으로 구해짐

2. P와 NP

분류	뜻
P	다항식 시간 안에 답을 구할 수 있는 (예/아니오) 문제
NP	답이 “예”인 해가 주어지면, 그것이 맞는지 다항식 시간 안에 확인할 수 있는 문제
NP-Hard	모든 NP 문제를 다항식 시간 안에 이 문제로 변환할 수 있음 (증명할 때는 이미 알려진 NP-Hard 문제 하나를 이 문제로 다항식 시간에 변환하면 됨)
NP-Complete	NP이면서 NP-Hard

P는 NP에 포함됨. P = NP인지는 아직 아무도 증명하지 못함
배낭 문제(의사결정 버전)는 NP-Complete. 앞의 DP는 \(O(nW)\)로 용량 W의 값에 비례하므로(입력 길이에 대해서는 지수) 다항식 시간 알고리즘이 아님
NP-Complete나 NP-Hard 문제는 정확한 최적해 대신 “최대한 좋은” 해를 빠르게 찾는 방향(근사, 휴리스틱)으로 접근함

3. 문자열 매칭

본문 A(길이 n)에서 패턴 P(길이 m)가 나타나는 위치를 모두 찾는 문제.

원시적 매칭

A의 모든 시작 위치에서 P와 한 글자씩 비교
\(O(mn)\). 앞에서 비교하며 알게 된 부분 일치 정보를 버려서 비효율적

전처리를 쓰는 매칭

전처리: 본 알고리즘이 데이터를 쉽게 다루도록 정보를 미리 계산해 두는 과정. 패턴만 보고 미리 계산해 두면, 매칭에 실패했을 때 이미 일치한 부분을 이용해 불필요한 비교를 건너뜀.

오토마타: 상태를 가지고 입력을 받을 때마다 상태를 바꾸는 계산 기계. 구성 요소 다섯 가지 (외우기)

기호	뜻
Q	상태 집합 (패턴에서 지금까지 일치한 길이 0 ~ m)
\(q_0\)	시작 상태 (0)
A	목표 상태 집합 (m, 패턴 전체가 일치)
\(\Sigma\)	입력 알파벳
\(\delta\)	상태 전이 함수 (현재 상태와 읽은 문자로 다음 상태 결정)

전이 함수를 만들어 두면 본문의 문자 하나당 전이 한 번 → 매칭은 \(\Theta(n)\)
KMP는 전이 함수 전체 대신 실패 함수 \(\pi\)(패턴의 각 접두사에서 “접두사이면서 접미사”인 가장 긴 길이)만 계산해 같은 효과를 냄. 전처리 \(O(m)\), 매칭 \(O(n)\)

라빈-카프

문자열을 \(d\)진수 수치로 바꿔서 문자열 비교를 수치 비교로 대신함
창을 한 칸 밀 때 맨 앞 문자의 몫을 빼고 새 문자를 더해서 다음 수치를 \(O(1)\)에 계산
수가 너무 커지지 않게 큰 소수 \(q\)로 나머지 연산을 함. 나머지가 같아도 실제 문자열은 다를 수 있으므로(가짜 일치) 수치가 같을 때만 문자열을 직접 비교
평균 \(O(n + m)\), 가짜 일치가 매우 많으면 최악 \(O(mn)\)

실행: 네 가지 매칭 비교

  
import random

def naive(A, P):
    n, m, hits, cmp = len(A), len(P), [], 0
    for i in range(n - m + 1):                    # 모든 시작 위치에서
        j = 0
        while j < m:
            cmp += 1
            if A[i + j] != P[j]: break
            j += 1
        if j == m: hits.append(i)
    return hits, cmp

def build_automaton(P, sigma):
    """δ(q, a): 상태 q(일치한 길이)에서 문자 a를 읽은 뒤의 상태. P[:k]가 (P[:q] + a)의 접미사인 가장 큰 k"""
    m, delta = len(P), []
    for q in range(m + 1):
        row = {}
        for a in sigma:
            k = min(m, q + 1)
            while k > 0 and not (P[:q] + a).endswith(P[:k]): k -= 1
            row[a] = k
        delta.append(row)
    return delta

def automaton_match(A, P, delta):
    q, hits = 0, []
    for i, a in enumerate(A):                     # 문자 하나당 상태 전이 한 번
        q = delta[q].get(a, 0)
        if q == len(P): hits.append(i - len(P) + 1)
    return hits, len(A)

def kmp(A, P):
    m = len(P); pi = [0] * m; k = 0               # pi[i]: P[:i+1]의 가장 긴 (접두사 = 접미사) 길이
    for i in range(1, m):
        while k and P[i] != P[k]: k = pi[k - 1]
        if P[i] == P[k]: k += 1
        pi[i] = k
    hits, q, cmp = [], 0, 0
    for i, c in enumerate(A):
        while True:
            cmp += 1
            if c == P[q]: q += 1; break
            if q == 0: break
            q = pi[q - 1]                         # 실패하면 이미 일치한 부분을 이용해 건너뜀
        if q == m: hits.append(i - m + 1); q = pi[q - 1]
    return hits, cmp, pi

def rabin_karp(A, P, d=256, q=1_000_003):
    n, m = len(A), len(P)
    h = pow(d, m - 1, q)                          # 맨 앞 자리의 가중치
    p = t = 0
    for i in range(m):                            # 패턴과 첫 창의 수치 계산
        p = (d * p + ord(P[i])) % q; t = (d * t + ord(A[i])) % q
    hits, spurious = [], 0
    for s in range(n - m + 1):
        if p == t:                                # 수치가 같을 때만 실제 문자열 비교
            if A[s:s + m] == P: hits.append(s)
            else: spurious += 1
        if s < n - m:                             # 창을 한 칸 밀며 O(1)에 다음 수치 계산
            t = (d * (t - ord(A[s]) * h) + ord(A[s + m])) % q
    return hits, spurious

A, P = "ababcabcabababd", "ababd"
print("본문:", A, " 패턴:", P)
print("naive    :", naive(A, P))
print("automaton:", automaton_match(A, P, build_automaton(P, set(A))))
h, c, pi = kmp(A, P); print("KMP      :", (h, c), " 실패 함수 pi =", pi)
print("Rabin-Karp:", rabin_karp(A, P))

print("\n패턴 'ababd'의 상태 전이 함수 δ (행: 상태, 열: 문자)")
delta = build_automaton(P, "abd")
for q, row in enumerate(delta):
    print(f"  상태 {q}: " + "  ".join(f"{a}→{row[a]}" for a in "abd"))

# 큰 입력: 결과가 str.find로 찾은 위치와 같은지, 비교 횟수는 얼마인지
random.seed(0)
A = "".join(random.choice("ab") for _ in range(200_000))
P = "abababab" + "b"
truth = [i for i in range(len(A)) if A.startswith(P, i)]
n1, c1 = naive(A, P); a1, c2 = automaton_match(A, P, build_automaton(P, "ab"))
k1, c3, _ = kmp(A, P); r1, sp = rabin_karp(A, P)
print(f"\nn = {len(A):,}, m = {len(P)}, 일치 {len(truth)}곳")
print("네 방법 모두 정답과 일치:", n1 == a1 == k1 == r1 == truth)
print(f"문자 비교(또는 전이) 횟수  naive {c1:,} / automaton {c2:,} / KMP {c3:,}, Rabin-Karp 가짜 일치 {sp}번")