그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)

문제 해결 과정에서 각 단계마다 현재 상황에서 가장 최적이라고 판단되는 선택을 수행하는 알고리즘

선택이 한 번 이루어지면 결정을 되돌릴 수 없는 것이 특징

이러한 방식으로 문제를 단계별로 해결하여 전체 문제에 대한 해답을 도출

 

✨지역 최적해 / 전역 최적해

지역 최적해(Local Optimum)

한 단계에서 당장 선택 가능한 가장 좋은 해결책

전역 최적해(Global Optimum)

문제 전체를 고려했을 때 가장 좋은 해결책

# 그리디 알고리즘은 각 단계마다 지역 최적해를 선택하여 최종적으로 전역 최적해에 도달하려고 하지만, 모든 문제에서 지역 최적해의 연속이 전역 최적해로 이어지는 것은 아님

-🐢

그리디 알고리즘 설계

그리디 알고리즘이 올바르게 동작하려면 두 가지 중요한 성질이 만족되어야 함

 

1️⃣ 그리디 선택 속성(Greedy Choice Property)

· 매 단계에서 그리디 알고리즘이 하는 선택이 전체 문제에 대해 최적해를 도출하는 데 필요한 결정이어야 한다는 성질

· 각 단계의 최선의 선택이 나중에 다른 선택을 하지 않아도 전역 최적해에 기여하는 구조여야 함

2️⃣ 최적 부분 구조(Optimal Substructure)

· 문제의 최적 해가 그 문제의 부분 문제들의 최적 해로 구성될 수 있어야

· 만약 어떤 문제를 작은 문제로 나눴을 때, 각 작은 문제의 최적해를 결합하면 전체 문제의 최적해가 된다는 특성이 있다면 그 문제는 그리디 알고리즘을 적용할 수 있는 후보가 됨

🐢-

대표적인 그리디 알고리즘

1️⃣ 동전 거스름돈 문제(Coin Change Problem)

주어진 거스름돈을 최소 개수의 동전으로 거슬러 주는 문제

그리디 접근: 매 단계마다 가장 큰 동전을 선택하여 거스름돈에서 빼는 방식

주의: 모든 동전 단위가 "특정 조건"(예: 배수 관계)이 있을 때만 그리디 방식이 전역 최적해를 보장

def coin_change(amount, coins):
    """
    amount: 거슬러 줘야 하는 금액
    coins: 동전 단위 (내림차순 정렬되어 있다고 가정)
    """
    result = []
    for coin in coins:
        count = amount // coin
        if count > 0:
            result.append((coin, count))
            amount -= coin * count
    if amount != 0:
        # 그리디 접근은 일부 경우 해결하지 못할 수 있음.
        return None
    return result

# 미국 동전 단위: 25, 10, 5, 1 (센트 단위)
coins = [25, 10, 5, 1]
amount = 87  # 예: 87센트
change = coin_change(amount, coins)
print("거스름돈:", change)
# 출력 예: 거스름돈: [(25, 3), (10, 1), (1, 2)]

 

2️⃣ 활동 선택 문제(Activity Selection Problem)

겹치지 않는 활동(예: 회의)들을 최대한 많이 선택하는 문제

그리디 접근: 끝나는 시간이 가장 빠른 활동을 먼저 선택하고, 그 이후에 시작 시간이 선택된 활동의 끝나는 시간 이후인 활동들을 순서대로 선택

장점: 이 문제는 그리디 선택 속성과 최적 부분 구조를 만족하므로, 그리디 알고리즘이 최적 해를 보장

def activity_selection(activities):
    """
    activities: (시작 시간, 종료 시간) 튜플의 리스트
    종료 시간이 가장 빠른 순서대로 정렬 후, 활동을 선택.
    """
    # 종료 시간 기준으로 정렬
    activities.sort(key=lambda x: x[1])
    selected = []
    last_end_time = 0

    for start, end in activities:
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end

    return selected

# 사용 예시
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
result = activity_selection(activities)
print("선택된 활동들:", result)
# 출력 예: 선택된 활동들: [(1, 4), (5, 7), (8, 11), (12, 14)]

 

3️⃣ 최소 신장 트리(MST, 예: 크루스칼 알고리즘, 프림 알고리즘)

그래프에서 모든 정점을 연결하는 최소 비용의 트리(MST)를 찾는 문제

 

📍크루스칼 알고리즘

그래프의 모든 간선을 가중치가 낮은 순으로 정렬한 후, 가장 낮은 가중치의 간선부터 선택

선택한 간선이 사이클(cycle)을 형성하지 않으면 MST에 포함시키고, 이를 모든 정점이 연결될 때까지 반복

주요 단계:

· 모든 간선을 가중치 기준으로 정렬

· Union-Find(Disjoint Set) 자료구조를 사용하여 간선을 추가할 때 사이클이 생기는지 검사

· 간선을 하나씩 선택하면서, 사이클이 없다면 MST에 추가하고 두 정점을 하나의 집합으로 합침

· 정점 개수 - 1 개의 간선이 선택되면 MST가 완성

# Union-Find 자료구조
class UnionFind: 
    def __init__(self, n):
        # 0부터 n-1까지 각 정점을 자기 자신으로 초기화
        self.parent = list(range(n))

    def find(self, x):
        # 경로 압축(Path Compression) 기법 사용
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # 두 정점의 루트가 다르면 하나로 합침
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX
            return True
        return False

# 크루스칼 알고리즘
def kruskal(n, edges):
    """
    n: 정점의 개수 (정점은 0부터 n-1까지)
    edges: 각 간선을 (가중치, 정점 u, 정점 v) 튜플로 나타낸 리스트
    반환: MST에 포함된 간선 리스트와 전체 비용
    """
    # 간선을 가중치 기준으로 정렬
    edges.sort(key=lambda x: x[0])
    uf = UnionFind(n)
    mst = []
    total_cost = 0

    for weight, u, v in edges:
        # 사이클이 형성되지 않으면(두 정점의 루트가 다르면) 간선을 추가
        if uf.union(u, v):
            mst.append((u, v, weight))
            total_cost += weight

    return mst, total_cost

# 사용 예시
if __name__ == "__main__":
    # 정점: 0, 1, 2, 3
    n = 4
    # 간선 목록: (가중치, u, v)
    edges = [
        (1, 0, 1),
        (4, 0, 2),
        (3, 1, 2),
        (2, 1, 3),
        (5, 2, 3)
    ]
    
    mst, cost = kruskal(n, edges)
    print("Kruskal 알고리즘 MST:")
    for u, v, weight in mst:
        print(f"{u} - {v} : {weight}")
    print("전체 비용:", cost)

 

📍프림 알고리즘(Prim’s Algorithm)

시작 정점에서 출발해, 현재 MST에 포함된 정점과 연결된 간선 중에서 가장 가중치가 낮은 간선을 선택해 MST를 확장

주요 단계:

· 시작 정점을 선택하고 MST에 추가

· MST에 포함된 정점과 인접한 모든 간선을 우선순위 큐(최소 힙)에 넣음

· 우선순위 큐에서 가장 낮은 가중치의 간선을 꺼내, 그 간선의 반대편 정점이 아직 MST에 없다면 해당 정점을 MST에 추가하고, 그 정점과 연결된 간선을 큐에 삽입

· 모든 정점이 MST에 포함될 때까지 반복

import heapq

def prim(n, adj):
    """
    n: 정점의 개수 (정점은 0부터 n-1까지)
    adj: 인접 리스트 형태의 그래프, 각 정점에 대해 (가중치, 인접 정점)의 리스트
         예: {0: [(1, 1), (4, 2)], 1: [(1, 0), (3, 2), (2, 3)], ...}
    반환: MST에 포함된 간선 리스트와 전체 비용
    """
    visited = [False] * n
    mst = []
    total_cost = 0
    # 시작 정점을 0번으로 가정
    visited[0] = True
    # 우선순위 큐 초기화: 시작 정점에서 나가는 간선들 추가
    min_heap = []
    for weight, v in adj[0]:
        heapq.heappush(min_heap, (weight, 0, v))
    
    while min_heap:
        weight, u, v = heapq.heappop(min_heap)
        if not visited[v]:
            visited[v] = True
            mst.append((u, v, weight))
            total_cost += weight
            # v에서 나가는 모든 간선을 큐에 추가 (이미 방문한 정점은 제외)
            for next_weight, next_v in adj[v]:
                if not visited[next_v]:
                    heapq.heappush(min_heap, (next_weight, v, next_v))
    
    return mst, total_cost

# 사용 예시
if __name__ == "__main__":
    n = 4
    # 무방향 그래프를 인접 리스트로 표현 (각 간선은 양쪽에 추가)
    # 예를 들어, 0과 1 사이 간선 가중치 1
    adj = {
        0: [(1, 1), (4, 2)],
        1: [(1, 0), (3, 2), (2, 3)],
        2: [(4, 0), (3, 1), (5, 3)],
        3: [(2, 1), (5, 2)]
    }
    
    mst, cost = prim(n, adj)
    print("Prim 알고리즘 MST:")
    for u, v, weight in mst:
        print(f"{u} - {v} : {weight}")
    print("전체 비용:", cost)

 

4️⃣ 허프만 코딩(Huffman Coding)

주어진 문자(또는 심볼)의 빈도에 따라 가변 길이의 이진 코드를 할당하는 압축 알고리즘

빈도수가 높은 문자는 짧은 코드를, 빈도수가 낮은 문자는 긴 코드를 할당하여 전체 평균 코드 길이를 최소화

최소화를 위해 허프만 트리(Huffman Tree)를 구성하는데, 각 리프 노드는 문자와 그 빈도수를 가지며, 내부 노드는 자식 노드들의 빈도수 합을 가짐

최종적으로 트리의 각 리프 노드까지 도달하는 경로가 해당 문자의 허프만 코드

import heapq

# 1. 허프만 노드 클래스 정의
class HuffmanNode:
    def __init__(self, frequency, symbol=None, left=None, right=None):
        self.frequency = frequency  # 문자 빈도수
        self.symbol = symbol        # 리프 노드일 경우 해당 문자, 내부 노드는 None
        self.left = left            # 왼쪽 자식
        self.right = right          # 오른쪽 자식

    # heapq 모듈이 노드들을 비교할 때, 빈도수를 기준으로 비교하도록 __lt__ (less than) 메서드를 정의
    def __lt__(self, other):
        return self.frequency < other.frequency

    def __repr__(self):
        return f"HuffmanNode(symbol={self.symbol}, frequency={self.frequency})"


# 2. 허프만 트리 생성 함수
def build_huffman_tree(frequency):
    """
    frequency: 각 문자의 빈도수를 담은 딕셔너리 (예: {'a': 45, 'b': 13, ...})
    반환: 허프만 트리의 루트 노드
    """
    heap = []
    # 각 문자에 대해 허프만 노드를 생성하고 최소 힙에 삽입
    for symbol, freq in frequency.items():
        node = HuffmanNode(freq, symbol)
        heapq.heappush(heap, node)

    # 최소 힙의 크기가 1이 될 때까지 두 개의 최소 빈도 노드를 추출하여 병합
    while len(heap) > 1:
        node1 = heapq.heappop(heap)  # 빈도수 가장 낮은 노드
        node2 = heapq.heappop(heap)  # 두 번째로 낮은 노드

        # 두 노드를 병합하여 새로운 부모 노드를 생성
        merged = HuffmanNode(node1.frequency + node2.frequency, None, node1, node2)
        heapq.heappush(heap, merged)

    # 남은 하나의 노드가 허프만 트리의 루트가 됨
    return heap[0]


# 3. 허프만 코드 생성 함수
def generate_huffman_codes(root, prefix="", code_map=None):
    """
    root: 허프만 트리의 루트 노드
    prefix: 현재까지 생성된 코드 (재귀적으로 갱신)
    code_map: 각 문자에 할당된 허프만 코드를 저장할 딕셔너리
    반환: 문자별 허프만 코드가 담긴 딕셔너리
    """
    if code_map is None:
        code_map = {}

    # 리프 노드라면 해당 심볼에 현재 prefix를 할당
    if root.symbol is not None:
        code_map[root.symbol] = prefix
    else:
        # 내부 노드인 경우 왼쪽은 '0', 오른쪽은 '1'을 추가하며 재귀 호출
        if root.left:
            generate_huffman_codes(root.left, prefix + "0", code_map)
        if root.right:
            generate_huffman_codes(root.right, prefix + "1", code_map)
    return code_map


# 4. 허프만 코딩 전체 예제 실행
if __name__ == "__main__":
    # 예시 빈도: 각 문자의 발생 빈도 (문자열 압축 등에서 많이 사용됨)
    frequency = {
        'a': 45,
        'b': 13,
        'c': 12,
        'd': 16,
        'e': 9,
        'f': 5
    }

    # 허프만 트리 생성
    root = build_huffman_tree(frequency)
    # 허프만 코드 생성
    huffman_codes = generate_huffman_codes(root)

    print("허프만 코딩 결과:")
    for symbol in sorted(huffman_codes):
        print(f"{symbol}: {huffman_codes[symbol]}")

    # 출력 예시 (코드는 구현 방식 및 힙의 특성에 따라 달라질 수 있음):
    # a: 0
    # b: 101
    # c: 100
    # d: 111
    # e: 1101
    # f: 1100

· HuffmanNode 클래스(허프만 노드 클래스 정의)

각 노드는 빈도수, 문자(심볼), 왼쪽/오른쪽 자식을 가짐

__lt__ 메서드를 구현하여, 힙에서 빈도수 기준 비교가 가능하도록 함

· build_huffman_tree 함수(허프만 트리 생성)

주어진 빈도 딕셔너리로부터 각 문자에 대해 노드를 만들고, 최소 힙에 넣음

힙에서 두 개의 노드를 꺼내어 빈도수의 합으로 병합한 새로운 노드를 생성하고, 다시 힙에 넣는 과정을 반복

최종적으로 힙에 남은 한 개의 노드가 전체 허프만 트리의 루트가 됨

· generate_huffman_codes 함수(허프만 코드 생성)

허프만 트리를 재귀적으로 순회하면서, 왼쪽으로 이동할 때마다 코드에 "0"을, 오른쪽으로 이동할 때마다 "1"을 추가

리프 노드에 도달하면 해당 문자에 대한 코드(prefix)를 코드 맵에 저장