다이나믹 프로그래밍(파이썬3)

한국어로는 동적 프로그래밍입니다.

알고리즘의 효율을 개선해주는 방법이라고 할 수 있습니다.

 

다이내믹 프로그래밍 사용 조건...

1. 최적 부분 구조: 큰 문제를 여러 작은 문제들로 나눌 수 있는지

2. 중복되는 부분 문제 : 동일한 작은 문제들을 반복적으로 해결할 수 있는지

 

메모이제이션...

-한 번 구한 문제의 답을 메모리 공간에 메모해놓는 기법

-다이내믹 프로그래밍 구현 방법 중 하나

피보나치 수열(메모이제이션 응용)(파이썬)

 

다이나믹 프로그래밍 문제 접근 방법...

1. 그리디, 구현, 완전 탐색 등의 아이디어를 접목시켜보고, 그래도 해결이 안 되면

다이내믹 프로그래밍을 접목시켜보자

 

2. 재귀 함수로 먼저 코딩해본 후, 다이내믹 프로그래밍으로 효율성을 개선시켜보자

 

---

예제 1) 효율적인 화폐 구성

 

-화폐 단위로 한 칸씩 이동하는 느낌?으로 접근해본다.

ex) 화폐단위 2를 기준으로 생각하고 있다면

d [2] = 1일 때, d [4] = 2 임을 유추할 수 있다. (2원에 2원 1개만 더하면 4원이 됨으로)

 

-화폐단위별로 한 번씩 유추하는 과정을 반복해준다.(과정이 반복되면 반복될수록 값이 더 정확해진다.)

ex) 화폐단위 2를 기준으로 반복이 한번 끝난 상태에서, 화폐단위 3을 기준으로 생각하고 있다고 가정해보자.

2 기준 반복에서는 d [6] = 3이었다. 

하지만

3 기준 반복에서는

d [3]=1을 바탕으로 d [6] = 2 임을 유추할 수 있다.(좀 더 정확한 값이 도출됨)

 

전 처음에 코드 이해에 정말 오랜 시간이 걸렸습니다 ㅠㅠㅠ

조금 더 직관적인 접근을 위해 표를 살짝 추가해볼게요~

 

N=3 / money_list = [2,3,5] / M=7 일 때

(i=0 loop)

d index	0	1	2	3	4	5	6	7
d value	0	1001	1	1001	1	1001	1	1001

(i=1 loop)

d index	0	1	2	3	4	5	6	7
d value	0	1001	1	1	2	2	2	3

(i=2 loop)

d index	0	1	2	3	4	5	6	7
d value	0	1001	1	1	2	1	2	2

---

정리) 

-막상 짜고 보면 간단하다.

-근본적인 사고의 틀인 점화식을 구하는 것이 가장 중요하다.

-메모이제이션을 통해 효율을 높인다.