동적 계획법(Dynamic Programming) 과 탐욕법(Greedy Algorithm)

최적화 문제를 푸는 방법은 두 가지가 있다

1. 모든 상황을 고려해 최적의 방법을 찾는 것 -> 동적계획법

2. 그때 그때 가장 최선의 방법을 선택해 답을 구하는 방법 -> 탐욕법

 

---

동적계획법 (Dynamic Programming)

- 전체 문제를 여러 개의 하위 문제로 나누고, 하위 문제들의 해결 방법을 결합해 최종 문제를 해결하는 방식

 

예제 

1. 배낭문제

2. 막대기 자르기

.

.

 

탐욕법 (탐욕 알고리즘, Greedy Algorithm)

- 문제를 해결하는 과정에서 순간순간마다 최적이라고 생각하는 결정을 내려 진행해 최종 문제를 해결하는 방식

- 전체 문제해결의 최적의 답을 보장하진 않지만, 계산 속도가 빠르다는 장점이 있다.

 

위의 문제 (가장 큰 수 찾기)에서도 실제로 가장 큰 수는 99이지만, 그리디 알고리즘으로 찾게 된다면 12가 나온다

 

 

예제

1. 거스름돈 동전 계산 문제

2. 허프만 코딩

.

.

 

 

각각 예제들은 추후 더 자세히 포스팅 하는 걸로..