[백준] 9184 신나는 함수 실행 (python 파이썬)

문제링크:https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

작성코드

 

 

풀이

 

우선 문제의 의사 코드를 재귀함수로 풀어보았다.

 

주어진 의사코드를 바로 python으로 작성하면 위와 같이 나온다.

하지만 이와 같은 방식은 같은 w(a,b,c) 값이 나오더라도 저장을 하지 않고 매번 새로 계산 하므로서 계산 부하가 심하다

 

 

DP(동적 프로그래밍, dynamic programming)

 

최적화 기법으로서 하나의 문제를 작은 여러개의 문제로 분할한 뒤 작은 문제의 결과를 저장하여 큰 문제를 해결할 때 사용하는 방법이다.

메모리를 사용하여 계산 속도를 증가시키는 방법으로 이를 메모이제이션이라고 한다 (캐싱이라고도 함)

 

이를 활용한 코드이다.

 

위의 재귀방식에서 달라진 점은 dp 리스트를 미리 생성해두고 매번 계산마다 dp[a][b][c]에 저장을 한다는 것이다.

예를 들면 DP(20,20,20)에 대하여 연산은 DP(19,20,20) + DP(19,19,20) + DP(19, 20, 19) - DP(19,19,19)가 나온다.

이는 다시

DP(19, 20, 20) = DP(18, 20, 20) + DP(18, 19, 20) - DP(18, 20, 19) - DP(18, 19, 19)

DP(19, 19, 20) = DP(18, 19, 20) + DP(18, 18, 20) - DP(18, 19, 19) - DP(18, 18, 19)

...

벌써부터 DP(18, 19, 20)와 DP(18, 19, 19)가 중복되기 시작한다.

이를 매번 계산하는 것은 비효율적이기 때문에 한번 계산한 값은 dp에 넣어준다.

이렇게 하면 최악의 경우에도 20*20*20 = 8000 번의 계산만 있다면 추가 연산이 필요하지 않게 된다.

 

※ 이때 재귀와 다르게 if dp[a][b][c]: return dp[a][b][c] 가 존재하는데 이는 이미 값이 있다면 해당 값을 쓴다는 의미이다.

만약 이 코드가 없다면 기존 재귀와 동일하게 연산이 진행되며 계산 값을 매번 리스트에 새로 덧씌워줄 뿐이다.

(연산량이 동일하고 메모리만 사용한다)