중복되는 연산을 줄이자
1. 다이내믹 프로그래밍(=동적 계획법)이 필요한 이유
- 컴퓨터의 메모리 공간은 제한적
- 시간이 매우 많이 걸리는 알고리즘을 효율적으로 만들 수 있음
2. 다이내믹 프로그래밍 예시
피보니치 수열: 다이내믹 프로그래밍을 사용하면 연산 횟수와 수행 시간을 비약적으로 줄일 수 있다.
내가 처음 다이내믹 프로그래밍을 알게된 계기도 피보나치 수열이었다.- 기본적인 피보나치 수열 함수
int fibo(int x){
if(x==1 || x==2) return 1;
return fibo(x-1) + fibo(x-2);
}- 기본적인 피보나치 수열은 구하려는 숫자가 커질수록 중복된 연산이 굉장히 많아진다.
- 중복된 연산을 줄이면 연산 횟수가 줄고 수행시간이 빨라질 것이다.
- 중복 연산을 줄인 피보나치 수열 함수
int d[100] ={0,};
int fibo(int x){
if(x==1 || x==2) return 1;
if(d[x]!0) return d[x];
return d[x] = fibo(x-1) + fibo(x-2);
}시간복잡도: O(N)
3. 다이내믹 프로그래밍 사용 조건
모든 경우에 다이내믹 프로그래밍을 사용할 수 있는 것은 아니다.
다이내믹 프로그래밍을 사용할 수 있는 경우 (ex. 피보나치 수열)
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
4. 메모이제이션
- 메모이제이션은 다이내믹 프로그래밍을 구현하는 방법 중 한 종류 (캐싱이라고도 함)
- 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
- 피보나치 수열을 수정한 방법이 메모리제이션
- 한 번 구한 정보를 리스트에 저장하는 방식으로 구현
5. 다이내믹 프로그래밍의 종류
1. 탑다운
- 큰 문제를 해결하기 위해 작은 문제를 호출
- 재귀 함수 이용
- 위에서 사용한 피보나치 수열 수정이 탑다운 방식
2. 바텀업
- 작은 문제부터 차근차근 답을 도출
- 반복문 이용
- 반복문을 이용한 피보나치 수열 함수 수정
int d[100]={0,};
d[1]=1;
d[2]=1;
n=99;
for(int i=3; i<=n; i++){
d[i] = d[i-1]+d[i-2];
}
cout<<d[n]<<endl;6. 정리
- 다이내믹 프로그래밍 기법을 사용하면 연산 횟수와 수행 시간을 비약적으로 줄일 수 있다.
- 다이내믹 프로그래밍 기법은 항상 사용할 수 있는 것은 아니다.
- 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리거나
- 해결하고자 하는 부분 문제들의 중복 여부를 확인해보고 다이내믹 프로그래밍 기법을 사용하자.
- 재귀 함수는 무한히 호출할 수 없기 때문에 (메모리 스택 때문) 탑 다운 방식보다 바텀 업 방식으로 구현하는 것을 권장
7. 예제
8-1. 1로 만들기
