[알고리즘] 동적계획법
피보나치 수열
: 첫째, 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
동적계획법이란?
: 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법
이 때, 하위 문제의 답을 저장하여 중복 연산을 하지 않음.
동적계획법 문제의 특성
중복되는 부분문제 : 작은 하위 문제들이 중복되어 나타난다.
최적 부분 구조 : 최적해는 부분 문제의 최적해로부터 구할 수 있다.
시간 복잡도
간단한 재귀호출 : 계산하는 양이 대략 2배씩 늘어남. 계산양이 많아지면 느려짐
동적계획법: 각 항들은 딱 1번씩만 계산이 됨. n번째 항을 구하기 위해선 n만큼만 시간을 들이면 됨.
공간 복잡도
: 하위 문제들의 답을 저장해놓기 때문에 하위 문제의 수만큼 저장공간 필요
동적계획법을 구현하는 테크닉
점화식
: 복잡한 문제를 작은 하위문제로 표현한 식
예) f(n) = f(n-1)+f(n-2)
1. 구하고자 하는 값이 무엇인지 정의한다.
f(n): n번째 피보나치 수열
2. 구하고자 하는 값을 부분문제들로 표현한다.f(n) = f(n-1)+f(n-2)
피보나치 수열의 n번째 항은 n-1항과 n-2항의 합이다.
방법
1. top-down (재귀호출식 방법)
= 작은문제를 풀어 return해준다.
= 큰 문제를 작은 문제로 나눈다.
2. bottom-up (반복문식 방법)
= 크기를 조금씩 늘려서 문제를 푼다.
= 작은 문제부터 차례로 풀어 적는다.
동적계획법 문제풀이 방법 요약
- 구하고자 하는 값이 무엇인지 정의하기
- 구하고자 하는 값을 부분문제로 구성된 식으로 표현하기
- 점화식을 재귀호출, 반복문 식으로 코드로 작성하기