DP (Dynamic Programming) vs 그리디 알고리즘

동적 계획법의 두가지 방법론

메모이제이션(하향식 방법)

메인 문제를 분할하면서 해결하는 방법이다.
태뷸레이션(상향식 방법)

가장 작은 문제를 먼저 해결하고 최종적으로 메인 문제를 해결하는 방법이다.


그리디 알고리즘의 이해
그리디 알고리즘은 동적 계획법을 보완하는 개념이다

브루트 포스, 동적 계획법 그리고 그리디 알고리즘을 비교한다


위 그림을 참고해 서울 → 부산을 가는 최소 경로를 구해보자

브루트 포스, 동적 계획법, 그리고 그리드 알고리즘을 토대로 구해볼 것이다



브루트 포스

서울에서 부산으로 갈 수 있는 모든 해를 구한다(왼쪽부터)

250km + 100km / 80km / 120km

200km + 100km / 80km / 120km

300km + 100km / 80km / 120km

위 9개의 값 중 최소값인 280km를 결과로 반환한다



동적 계획법

1항: 서울 → 대구 경로에서 최소값을 기록한다

= 250km, 200km, 300km 중 최소값을 기록

→ dp[1] = 200km



2항: 서울 → 부산 경로까지 최소값을 기록한다

= 200km+100km, 200km+80km, 200km+120km 중 최소값을 기록

→ dp[2] = 280km



그리디 알고리즘
250km / 200km / 300km 중 최소값을 구한다

100km / 80km / 120km 중 최소값을 구한다

최소값을 모두 더한다 = 280km

→ 이 문제의 경우 세가지 방법 중 가장 효율적인 방식이라 할 수 있다

그리디 알고리즘의 적용
그리디 알고리즘은 현재의 선택이 미래에 영향을 주지 않을 때 사용할 수 있다

위 문제의 경우 서울 → 대전의 1번 경로를 선택해도 대전 → 부산의 길 선택에 영향을 주는 것은 아니다매 순간의 선택이 제한조건에 영향을 주지 않을 때 순간마다 최적의 해를 구하는 경우를 알아본다

출처:

https://devyoseph.tistory.com/m/132