Dynamic Programming

[DP] 문제 풀이 팁

다이나믹 프로그래밍 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하려는 알고리즘 기법 다이나믹 프로그래밍을 사용할 수 있는 경우 1. 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다) 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결 (최적화)) 두가지 조건을 만족하면 다이나믹 프로그래밍 방식을 사용할 수 있다 하향식 (탑다운) 메모이제이션 기법사용 : 한번 계산한 결과를 메모리 공간에 메모하는 기법 재귀 사용 탑다운 방식 시간복잡도 O(N) # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수를 재귀함수로 구현 (탑다운 DP) def fibo(x): # 종료 조건 (1 또는 2일때 1반환) if x == 1..