[알고리즘] Dynamic Programming (DB)

코딩테스트에서 DP 알고리즘은 단골 문제로 나온다. 그런데도 많은 사람들이 어려워하고, 나 또한 매우 어려워한다.
이번 기회에 개념을 확실히 다지고 DP 를 정복하고자 한다!!

 

피보나치 수열

DP 알고리즘의 대표적인 예시이다. 예시를 보면서 DP를 이해해보자.
피보나치 수열은 점화식으로 표현할 수 있다.

피보나치 수열의 점화식

이 점화식을 따라서 알고리즘을 짜기 위해서는 재귀 함수를 이용해야한다.

int fib(int n){
	if (n==1 or n==2){
		return 1;
	}
	return fib(n-1) + fib(n-2);
}

그런데 이런식으로만 작성하면 구하고자 하는 값이 커질때는 시간이 너무 오래 걸릴 수도 있다는 한계점이 있다.

하.. 그리는데 애먹었다..

왜냐하면 이미 구한 값을 계속 구해야하기 때문이다.
n이 1이거나 2일때가 나올때까지 계속 들어가야한다.

 

메모이제이션

중복으로 계산되는 것을 막기 위해 한번 계산된 것은 배열에 저장하도록 하는 기법이 메모이제이션이다. 

int mem[100];
mem[0] = 1;
mem[1] = 1;

int fib(int n) {	
	if (mem[n] != 0) return mem[n];
	return fib(n - 1) + fib(n - 2);
}

위 처럼 저장하는 배열을 미리 만들어서 값이 구해질때마다 값을 넣어주고, 찾고 싶을때 꺼내어 쓰면 된다.

이미 저장된 값을 가지고 값을 구하기 때문에 속도가 훨씬 빠르다.

 

재귀함수 대신 반복문

지금까지 재귀함수를 이용하여 DP를 구현해보았다.
이렇게 재귀함수를 이용하면 큰 문제를 먼저 맞딱뜨리고, 그 큰 문제를 해결하기 위해 더 작은 문제를 호출하고 저장하면서 큰 문제를 해결할 수 있다. 이런 방식은 탑다운 방식 혹은 하향식이라고 한다.

재귀 함수 대신에 반복문을 사용하면 재귀함수의 오버헤드 발생 문제에서 해방될 수 있다.

int dp[100];

int main() {
	dp[0] = 1;
	dp[1] = 1;
	int n = 6; //내가 찾고자 하는 피보나치 수
	for (int i = 3; i <= n; i++) {
		dp[n] = dp[n - 1] + dp[n - 2];
	}

	return 0;
}

반복문을 잘 보면, 작은 문제부터 차근차근 최종 문제까지 도달하여 정답을 도출해낸다. 이런 방식을 바틈업 방식 혹은 상향식이라고 한다.

보통 반복문을 사용하여 dp 알고리즘을 짤 때, 차근차근 결과값을 저장하는 배열의 이름을 dp라고 통상 짓는다.

 

 

여기까지가 가장 간단한 dp 알고리즘의 설명이다.
지금까지 배운 내용을 가지고 이 백준 문제를 풀어보면 이해하는데 더 도움이 될 것이다.

https://www.acmicpc.net/problem/9095 

9095번: 1, 2, 3 더하기

dp의 아주 기본적인 문제이지만 dp를 모르면 풀 수 없는 문제이기 때문에 처음에 dp를 학습할 때 좋은 문제라는 생각이 든다.