728x90
다이나믹 프로그래밍 (Dynamic Programming)
큰 문제를 작은 문제로 나누어 해결하는 방법
다음의 조건을 만족할 때 사용할 수 있다
- 큰 문제를 작은 문제로 나눌 수 있다
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다
메모이제이션(Memoizations)
- 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
- 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
- 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다
Code with Python
> 피보나치 함수 : 탑다운 다이나믹 프로그래밍
탑다운(Top-Down) : 큰 문제를 해결하기 위해 작은 문제를 호출, 재귀함수 이용
d = [0] * 100 # Memoization 하기 위한 리스트
def fibo(x):
if x == 1 or x == 2:
return 1
if d[x] != 0: # 계산한 적 있는 문제라면
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
> 피보나치 함수 : 보텀업 다이나믹 프로그래밍
보텀업(Bottom-Up) : 작은 문제부터 차근차근 답을 도출, 반복문 이용
- 전형적인 형태
- 보텀업 방식에서 사용하는 결과 저장 리스트를 'DP 테이블'이라고 부른다
- 재귀 함수 스택 크기가 한정되어 있을 수 있기 때문에 보텀업 방식으로 구현하기를 권장한다
d = [0] * 100 # DP 테이블
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
문제 접근
- 완전 탐색 알고리즘으로 접근했을 때 시간이 오래걸린다면, 다이나믹 프로그래밍을 적용할 수 있는지 고려해보자
- 재귀 함수로 비효율적인 프로그램일 작성한 뒤, 메모이제이션을 적용할 수 있다면 코드를 개선하자
- sys 라이브러리의 setrecursionlimit() 함수로 재귀 제한을 완화할 수 있다
import sys
sys.setrecursionlimit(2500)
📚 참고서적 : 이것이 코딩테스트다 with 파이썬
728x90