21-02-26 알고리즘 기초강의

탐욕법과 최소비용신장트리

동전 거스름돈 문제 슈도코드로 해결해보기

while (동전이 남아있고 문제가 미해결):
    가장 가치가 높은 동전을 선택
    if (동전을 더하여 거스름돈의 총액이 거슬러주어야 할 액수를 초과):
        동전을 다시 집어넣는다
    else:
        거스름돈에 동전을 포함시킨다
    if (거스름돈의 총액이 거슬러주어야 할 액수와 같다)
        문제 해결 return

이는 동전의 구성이 [500, 100, 50, 10, 5, 1]일때는 가능하지만 [500, 100, 80, 10, 5, 1]일 때엔 불가능함

탐욕법의 설계전략: 공집합에서 시작
→ 집합에 추가할 다음 최적의 원소를 고른다 (선택 과정)
→ 새로운 집합이 해답으로 적절한지 검사한다 (적절성 검사)
→ 새로운 집합이 문제의 해답인지 판단한다 (해답 점검)
→ 탐욕법은 상대적으로 설계하기 쉽지만 반드시 정확성을 증명해야 함
최소비용 신장트리 (MST:Minimum Spanning Tree) 문제
→ G = (V, E) : 모든 정점이 연결된 가중치가 있는 무방향 그래프
→ G의 부분 그래프 T = (V, F), F ⊆ E
→ 그래프 G의 모든 정점을 연결하는 트리, 간선의 개수는 n-1개
→ 이 때, 모든 신장트리 T 중에 가중치의 합이 최소가 되는 신장트리를 최소비용 신장트리라 함
최소비용 신장트리를 Brute-Force 방식으로 풀기
→ 모든 신장트리를 찾고 가중치의 합이 가장 작은 것을 선택
→ 간선의 개수가 n-1인 연결된 트리가 될때까지 간선을 제거
최소비용 신장트리를 Greedy 방식으로 풀기

해답의 집합을 공집합으로 둔다: 간선 집합 E의 부분 집합 F를 공집합으로 둔다
E에서 최적의 간선 하나를 추출하여 F에 포함시킴
→ 최적을 선택할 때 사용되는 알고리즘에는 프림, 크루스칼 알고리즘이 있다

프림 알고리즘

Y = {V1}: Y는 정점의 집합 V의 부분 집합
Y에 최적의 원소 하나를 포함시킨다 (가중치가 가장 작은 정점 vnear를 선택)
→ F집합에 (nearest(vnear), vnear)를 추가
해답의 집합이 최종이면 종료하고 아니면 2단계를 반복함
→ Y = V가 되면(모든 원소를 포함한다면) 종료

프림 알고리즘 어떻게 구현할까?
→ W[i][j]: 인접행렬 (간선의 가중치)
→ nearest[i] : Y 집합에서 vi에 가장 가까운 정점의 인덱스
→ distance[i] : vi와 nearest[i]의 정점을 연결하는 간선의 가중치

def prim (W):
    n = len(W) - 1
    F = []
    nearest = [-1] * (n + 1)
    distance = [-1] * (n + 1)
    for i in range(2, n+1):
        nearest[i] = 1
        distance[i] = W[1][i]
    for _ in range (n - 1):
        minValue = INF
        for i in range(2, n+1):
            if (0 <= distance[i] and distance[i] < minValue):
                minValue = distance[i]
                vnear = i
        edge = (nearest[vnear], vnear, W[nearest[vnear]][vnear])
        F.append(edge)
        distance[vnear] = -1
        for i in range(2, n+1):
            if (distance[i] > W[i][vnear]):
                distance[i] = W[i][vnear]
                nearest[i] = vnear
    return F

def cost (F):
    total = 0
    for e in F:
        total += e[2]
    return total

21-02-26 알고리즘 기초강의

탐욕법과 최소비용신장트리

Harry Kim