자료구조 & 알고리즘 & cs/알고리즘
[TIL] 동적 계획법 - DP, Dynamic Programming
뽀또롱
2023. 3. 17. 18:00
동적 계획법(DP)
- 작은 문제 해결 후 이를 이용하여 큰 문제를 해결
- 상향식 접근법 (보텀업)
- Memoization 기법(하향식/탑다운)
Memoization? = caching
- 프로그램 실행 시 이전의 값을 저장하여 중복되는 계산 횟수를 줄여 실행 속도를 빠르게 하는 기술
동적 계획법 문제 풀이
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
동적계획법 문제이다.
피보나치 수열을 해결하는 방법과 똑같아서 코드를 작성하였는데
메모리 초과가 떴다.
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)
글 읽기 - 파이썬 메모리 초과는 왜때문일까요;;;
댓글을 작성하려면 로그인해야 합니다.
www.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])728x90