[Algorithm]동적계획법(다이나믹 프로그래밍)

다이나믹 프로그래밍.

다이나믹이라는 단어가 들어가서 그런지 이름만 들으면 엄청 화려?하고 신날거같지만 실상은 그렇지않다.

프로그래밍에 다이나믹은 전혀 어울리지 않을거같은데 어떻게 다이나믹 프로그래밍이라는 이름을쓰지?

그래서 이름에대한 유래를 알아봤다.

---

동적 계획법의 고안자인 벨만(Richard E. Bellman)은 dynamic이라는 단어가 멋있어서(...) 선택했다고 한다.

Programming이란 단어는 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다.

• 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저) 1권 p.207

---

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그냥 멋있어보여서 사용함 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

다이나믹프로그래밍(DP) 에 대해 조금 알아보겠따.

다이나믹프로그래밍은 큰문제를 풀기위해 작은문제를 풀어 큰문제를 풀어가는 방법이다.

말로만 들으면 이해가 가지않는다 그래서 그림설명을 해보겠다.

대표적인 DP문제로 피보나치함수를 들 수 있다.

1003번: 피보나치 함수

 

www.acmicpc.net

(피보나치함수를 푸는 문제.)

사실 위 문제는 문제속에 피보나치함수를 구할수있는 식이 있다. 

하지만 옛날엔 그대로 답을 제출하면 통과였지만 채점기준이 바껴 모두 시간초과.. (재귀로 짜서그럼 그래서 DP로 풀어야한다.)

피보나치함수를 푸는방법으로 재귀함수를 이용한 방법이있지만 느리다. 수가 커질수록 엄청난 스택이쌓인다.

간단하게 4를 피보나치함수에 넣어보면 위처럼 호출되어진다.

하지만 이 그림을 보고있으면 필요없는 부분이있다. F(4) 밑의 F(2) 는 F(3)을 호출하면서 이미 F(2)의 답을 알고있다.

때문에 F(2)는 한번 더 호출할 필요가 없다.

이것을 해결한다면 엄청난 시간 단축 효과를 볼수있음. (메모이제이션)

(재귀피보나치 예)

재귀로풀면 시간초과가 나버림..

그래서 이 문제는 DP로 바꿔야한다.

사실 이 문제를 DP로 해결하는데도 여러방법이있다. 

이미 알고있는 부분을 메모이제이션 을 이용해 문제를 해결하는 방법이 있고(파이썬막코드),

이처럼 미리 알고있는 부분( if(listA[n] <= 0): )은 스킵하는 메모이제이션을 이용한 방법과

미리 앞의 값을 이용해 뒤에올 값을 계산해버리는 방법이있다.

처럼 규칙성? 을 이용해 뒤의값을 알아버리는것이다.

dp[i] = dp[i-1]+dp[i-2] 이처럼 인접한 수의 관계를 이용해 문제를 푸는것을 점화식 을 이용한 풀이 라고도 하는데 사실 많은 DP문제가 점화식만 구하면 답을 구할수있다.

이문제의경우 dp[i] = dp[i-1]+dp[i-2]가 점화식이된다.