다이나믹 프로그래밍 (Dynamic Programming)과 그리디 알고리즘 (Greedy Algorithm)의 공통점과 차이점

1. 개요

**다이나믹 프로그래밍 (DP)**과 그리디 알고리즘은 모두 최적화 문제를 해결하는 알고리즘 설계 기법입니다. 두 기법 모두 문제를 더 작은 하위 문제로 나누어 해결한다는 공통점이 있습니다. 그러나 문제를 해결하는 접근 방식과 적용 가능한 문제 유형이 서로 다릅니다.

 

2. 공통점

1. 최적화 문제 해결
   • 두 알고리즘 모두 최적의 해결책을 찾는 최적화 문제에 사용됩니다.
2. 문제의 분할
   • 두 기법 모두 문제를 더 작은 하위 문제로 나누어 해결합니다.
3. 부분 문제
   • 두 기법 모두 하위 문제를 해결한 결과를 기반으로 전체 문제의 해결책을 도출합니다.
4. 재귀적 사고
   • 두 알고리즘 모두 재귀적으로 문제를 해결할 수 있습니다.

 

3. 차이점

3.1. 문제 해결 접근 방식

 

다이나믹 프로그래밍 (DP)	그리디 알고리즘
하위 문제를 모두 해결하고, 그 결과를 기반으로 최적의 해를 찾습니다.	현재 상태에서 가장 최적의 선택을 하여 문제를 해결합니다.
전체 문제를 해결하기 위해 모든 가능한 선택지를 고려합니다.	항상 지역적으로 가장 좋은 선택을 하며, 전체 문제의 최적 해를 찾기 위해 나아갑니다.

3.2. 최적 부분 구조 (Optimal Substructure)

 

다이나믹 프로그래밍 (DP)	그리디 알고리즘
모든 하위 문제를 해결한 후, 그 결과를 결합하여 최적의 해를 구합니다.	단계별로 최적의 선택을 하며 최종적으로 최적의 해에 도달합니다.
예: 경로 문제에서 모든 하위 경로를 고려한 후 최적 경로를 찾습니다.	예: 항상 가장 짧은 간선을 선택하여 최적의 경로를 만듭니다.

3.3. 중복되는 하위 문제 (Overlapping Subproblems)

 

다이나믹 프로그래밍 (DP)	그리디 알고리즘
중복되는 하위 문제가 존재합니다. 같은 하위 문제를 여러 번 계산하므로 메모이제이션이나 테이블화를 사용합니다.	중복되는 하위 문제가 없습니다. 각 단계에서의 결정은 다음 단계에 영향을 미치지 않습니다.

3.4. 적용 가능성

 

다이나믹 프로그래밍 (DP)	그리디 알고리즘
최적의 해를 보장하기 위해 모든 선택지를 고려해야 할 때 사용합니다.	**문제가 그리디 선택 속성 (Greedy Choice Property)**을 만족할 때 사용합니다.
예: 최장 증가 부분 수열 (LIS), 배낭 문제 (Knapsack Problem)	예: 최소 스패닝 트리 (MST), 다익스트라 알고리즘

 

4. 핵심 개념 비교

4.1. 최적 부분 구조 (Optimal Substructure)

• 다이나믹 프로그래밍과 그리디 알고리즘 모두 최적 부분 구조를 가집니다.
  • 최적 부분 구조란 문제의 최적 해결책이 그 하위 문제들의 최적 해결책으로 구성되는 성질입니다.

4.2. 중복되는 하위 문제 (Overlapping Subproblems)

• 다이나믹 프로그래밍: 같은 하위 문제가 여러 번 반복됩니다.
  • 예: 피보나치 수열 계산에서 **F(5)**는 **F(4)**와 **F(3)**를 두 번 이상 계산합니다.
• 그리디 알고리즘: 중복되는 하위 문제가 없습니다. 각 단계의 선택이 다른 단계와 독립적입니다.

4.3. 그리디 선택 속성 (Greedy Choice Property)

• 그리디 알고리즘은 그리디 선택 속성을 만족해야 합니다.
  • 현재 단계에서 최적의 선택이 나중에도 전체 문제에 대해 최적의 해를 보장합니다.
• 다이나믹 프로그래밍은 그리디 선택 속성을 만족하지 않더라도 적용할 수 있습니다.

 

 

5. 예제 비교

예제 1: 배낭 문제 (Knapsack Problem)

1. 다이나믹 프로그래밍 (0-1 Knapsack)
   • 각 물건을 선택하거나 선택하지 않는 모든 경우를 고려하여 최적의 조합을 찾습니다.
   • 시간 복잡도: O(nW)O(nW)O(nW) (여기서 nnn은 물건의 수, WWW는 배낭의 용량)
2. 그리디 알고리즘 (Fractional Knapsack)
   • 물건의 무게당 가치가 높은 것부터 선택합니다 (그리디 선택).
   • 이 방법은 물건을 쪼갤 수 있는 경우에만 최적해를 보장합니다.
   • 시간 복잡도: O(nlog⁡n)O(n \log n)O(nlogn)

 

예제 2: 최단 경로 문제

1. 다익스트라 알고리즘 (그리디)
   • 양수 가중치를 가지는 그래프에서 최단 경로를 찾습니다.
   • 매 단계에서 가장 가까운 정점을 선택합니다.
2. 플로이드-워셜 알고리즘 (다이나믹 프로그래밍)
   • 모든 정점 쌍에 대해 최단 경로를 구합니다.
   • 시간 복잡도: O(V3)O(V^3)O(V3)

 

6. 시간 복잡도 및 공간 복잡도 비교

 

알고리즘	시간 복잡도	공간 복잡도
다이나믹 프로그래밍	보통 O(n×m)	보통 O(n×m)
그리디 알고리즘	보통 O(nlog⁡n) 또는 O(n)	보통 O(1) 또는 O(n)

 

7. 결론

특징	다이나믹 프로그래밍 (DP)	그리디 알고리즘
접근 방식	모든 하위 문제를 해결하고 결과를 조합	현재 단계에서 가장 최적의 선택을 함
최적해 보장	항상 보장 (적절한 조건 만족 시)	그리디 선택 속성을 만족할 때만 보장
중복 하위 문제	중복된 하위 문제가 있음. 메모이제이션 필요	중복 하위 문제가 없음
적용 예제	배낭 문제, 피보나치 수열, 최장 증가 부분 수열	다익스트라 알고리즘, 최소 스패닝 트리, 프림 알고리즘
복잡도	보통 O(n×m)	보통 O(nlog⁡n) 또는 O(n)

 

 

두 기법을 적절히 사용하기 위해서는 문제가 최적 부분 구조와 그리디 선택 속성을 만족하는지를 확인하는 것이 중요합니다.