Algorithms : Greedy Algorithm

이번 포스트에는 Greedy Algorithm과 Prim, Kruskal, Dijkstra Algorithm에 대해 다룬다.

Greedy Algorithm

Greedy Algorithm 기본 개념

• 매 순간 최선의 선택을 하며 진행함.
• 미래는 고려하지 않음, 되돌아가지 않음.
• 효율은 좋지만 모든 문제에 적용 불가.
• 동적 계획법(DP)과의 차이점:
  • Greedy: 현재 순간의 local optimum 선택
  • DP: 작은 문제들을 해결하여 global optimum 구성

예제 1) 거스름돈 문제 (Coin Change)

• 목표: 적은 수의 동전으로 거스름돈 만들기
• 전략: 가장 큰 동전부터 선택
• 문제: 항상 최적 해가 보장되진 않음
• 한국 동전 시스템: Greedy OK
• 이상한 나라의 동전(8, 6, 2 등): DP 필요

예제 2) Minimum Spanning Tree (MST)

• 정의: 모든 정점을 연결하면서 사이클이 없고, 가중치의 합이 최소인 트리
• 입력: 인접 행렬 W

• 출력: MST T = (V, F),

  F

  =

  V

  - 1

• 대표 알고리즘
  • Prim’s Algorithm
  • Kruskal’s Algorithm
• 서로 다른 locally optimal choice를 사용

---

Prim’s Algorithm

개요

• 시작 정점 v1에서 시작
• 매 단계마다 현재 정점 집합 Y에서 가장 가까운 정점을 선택하여 확장

시간 복잡도

• θ(n²)
• Binary heap 사용시: θ(m log n)
• Fibonacci heap 사용시: θ(m + n log n)

Kruskal’s Algorithm

개요

• edge들을 가중치 오름차순으로 정렬
• 사이클이 생기지 않도록 edge를 하나씩 추가

시간 복잡도

• Sorting: θ(m log m)
• 초기화: θ(n)
• find/merge: θ(m α(m, n))
• 전체: θ(m log m)

Dijkstra’s Algorithm

• Single Source Shortest Path 문제 해결
• 음수 가중치 edge 없음
• Prim과 유사한 구조

시간 복잡도

• θ(n²)
• Binary heap: θ(m log n)
• Fibonacci heap: θ(m + n log n)