[TIL] 동적 계획법 - DP, Dynamic Programming

동적 계획법(DP)

• 작은 문제 해결 후 이를 이용하여 큰 문제를 해결
• 상향식 접근법 (보텀업)
• Memoization 기법(하향식/탑다운)

Memoization? = caching
- 프로그램 실행 시 이전의 값을 저장하여 중복되는 계산 횟수를 줄여 실행 속도를 빠르게 하는 기술

 

 

동적 계획법 문제 풀이

1904번: 01타일 (acmicpc.net)

1904번: 01타일

 

동적계획법 문제이다.

피보나치 수열을 해결하는 방법과 똑같아서 코드를 작성하였는데

메모리 초과가 떴다.

 

import sys
n = int(sys.stdin.readline())
dp=[0]*1000001
dp[1]=1
dp[2]=2

for i in range(3,n+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%15746)

 

dp리스트의 크기를 미리 할당하면 메모리 초과가 해결되는 문제가 있었기에 이번에도 그렇게 하였는데

해결되지 않았다.

 

글 읽기 - 파이썬 메모리 초과는 왜때문일까요;;; (acmicpc.net)

글 읽기 - 파이썬 메모리 초과는 왜때문일까요;;;

이 답변을 보고 해결하였는데,

파이썬의 int형은 고정된 크기가 아니므로 변수의 크기에 따라 사용하는 메모리가 변한다는 것을 참고하여 

코드를 수정하였다.

 

import sys
n = int(sys.stdin.readline())
dp=[0]*1000001
dp[1]=1
dp[2]=2


for i in range(3,n+1):
    dp[i] = (dp[i-1]+dp[i-2])%15746
print(dp[n])