그리디, 다익스트라

그리디(Greedy)

각 단계에서 최선의 선택을 하는 방식으로 문제를 해결하는 알고리즘. 각 단계에서 최선의 선택(부분 문제의 최적해)를 모두 합쳤을때 전체에서의 최선의 선택과 다르다면 풀이가 성립하지 않는다. 따라서 그리디하게 문제를 풀때는 풀이의 정당성을 증명해야한다. 보통 최적화 문제에서 사용된다.

 

특징

1. 최적 부분 구조 (Optimal Substructure)
   큰 문제를 작은 문제로 쪼개어 해결할 수 있는 문제 구조를 가진다. 그리디 알고리즘은 각 단계에서 부분 문제의 최적해를 찾는 방법으로 전체 문제의 최적해를 찾는다.
2. 탐욕적 선택 속성 (Greedy Choice Property)
   각 단계에서 최적해를 찾기 위해 가장 최선의 선택을 한다. 이 선택이 나중에 문제의 해결에 대한 최적해에 영향을 미치지 않는다.
3. 순간적인 결정
   각 단계에서 한 번 결정된 선택은 후행 단계에서 번복되지 않는다. 즉 한 번 선택된 선택은 고려하지 않는다.

그리디 알고리즘은 다음과 같은 문제에 많이 사용된다:

• 최소 신장 트리 (Minimum Spanning Tree) 구성
• 최단 경로 문제 (Shortest Path Problem)
• 작업 스케줄링 문제 (Job Scheduling Problem)
• 코인 거스름돈 문제 (Coin Change Problem)
• 압축 알고리즘 등

 

다익스트라(Dijikstra)

간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘. 시작 정점을 설정하고 방문 가능하면서 비용이 가장 적게 드는 정점에 방문해 비용을 갱신한다. 이때 각 정점의 비용에 우선순위 큐를 사용하면 시간 복잡도 면에서 효율적일 수 있다. 작동 방식은 다음 단계로 이루어져있다.

1. 시작 정점에서 방문 가능한 정점에 대한 비용을 갱신하고 나머지 정점에 대한 비용은 무한대(INF, infinite)로 설정한다.
2. 방문하지 않는 정점 중 비용이 가장 적게 드는 정점에 방문한다. 해당 정점과 연결된 다른 정점의 비용을 갱신해야하는지 확인한다. 만약 해당 정점을 거쳐 다른 정점에 방문할때보다 기존보다 적은 비용이 든다면 비용을 갱신한다.
3. 모든 정점을 방문할때까지 이와 같은 방식으로 비용을 갱신한다. 모든 정점을 방문했다면 코드 수행을 종료한다.

빠른 다익스트라 알고리즘 구현을 위해서는 최단 거리, 즉 최솟값을 계속 뽑을 수 있는 자료구조가 필요하다. ⇒ Python의 heapq 라이브러리를 이용한다.

from heapq import *

def dijikstra(graph, start):
    """
    [input]
    graph: 인접 리스트 형태의 그래프
    graph[i] = [(j, cost), ...]는 i번 정점에서 j번 정점까지의 거리가 cost라는 의미
    start: 시작 정점의 번호

    [output]
    start 정점에서 각 정점까지의 최단 거리를 반환
    """

    INF = float('inf') # 무한대

    # 시작점을 제외한 모든 정점까지의 거리를 무한대로 설정
    dist = [INF] * len(graph)
    dist[start] = 0

    # 우선순위 큐에 (거리, 정점)을 넣어줌
    # 시작 정점은 거리가 0이므로 (0, start)
    q = [(0, start)]

    # 우선순위 큐가 빌 때까지 계속해서 알고리즘 수행
    while q:
        # 큐에서 가장 거리가 짧은 정점 꺼내기
        cost, idx = heappop(q)
        # 이미 처리된 정점(이미 최단 거리를 구한 정점)이라면 무시
        if dist[idx] < cost:
            continue

        # 현재 정점에서 갈 수 있는 모든 정점을 확인하기
        for adj, d in graph[idx]:
            if dist[adj] > cost + d:
                dist[adj] = cost + d
                heappush(q, (dist[adj], adj))

    return dist