21.02.20
백준 알고리즘 문제들을 풀다가 처음 만난 DP(Dynamic Programming)이라는 벽에 부딛혀 몇시간 동안 머리를 싸매다 미친듯한 구글링을 통해 겨우 한문제를 풀어 내었다.
깨달은 점은 DP라는 개념을 모르면 이 문제를 풀 수 없었다는 것이었다. 이 문제를 풀기 위해서 DP라는 개념에 대해서 찾아보고 이해한 것들을 여기 기록 해두려고 한다.
그렇다면 DP라는 게 뭔데?
-> Dynamic Programming
-> 동적 계획법
저 의미만 보면 뭔 멍멍이 소리인지 모르겠다.
나무위키의 설명을 들어보자.
<나무위키>
쉽게 얘기하자면 동적 계획법은 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
아까보다 설명이 길어지긴 했는데 아직 무슨 말인지 모르겠다.
백문이 불여일견이라고 문제를 한번 풀어보자. 그렇다면 위의 설명이 얼마나 친절한 설명인지 알 수 있다.
백준 2748문제
(위의 문제를 간단하게 풀어낸 사람이라면 이 글을 읽을 필요가 없을 거 같다.)
아주 간단한 피보나치 문제이다.
Simple Code
#include <stdio.h>
long long Fibonacci(int num) {
if(num == 1 || num == 2)
return 1;
return Fibonacci(num - 1) + Fibonacci(num - 2);
}
int main(void) {
int N;
scanf("%d", &N);
printf("%lld\n", Fibonacci(N));
return 0;
}위의 코드는 처음에 내가 이 문제를 풀었을 때의 방법이다.
나는 이 문제를 처음 읽었을 때 아주 찌끄레기문제라고 생각했다.
하지만 찌끄레기는 바로 나였음을 N이 90까지 주어진다는 것을 알고 N에다가 90을 집어넣었을 때 깨닫게 되었다.
(정말 오래 걸린다. 미친 듯이 오래 걸린다. 내 컴퓨터가 멈춘 건가 싶었다..)
Top-Down Code
#include <stdio.h>
#include <string.h>
long long memo[100];
long long Fibonacci(int num) {
if(num == 1 || num == 2)
return 1;
if(memo[num] != 0)
return memo[num];
memo[num] = Fibonacci(num - 1) + Fibonacci(num - 2);
return memo[num];
}
int main(void) {
int N;
scanf("%d", &N);
memset(memo, 0, sizeof(memo));
printf("%lld\n", Fibonacci(N));
return 0;
}
위의 코드가 바로 내가 DP에 대해서 어렴풋이 이해를 하고 제출해서 통과된 나의 답이다.
이제부터 두 코드를 비교하면서 설명을 시작하겠다.
나무위키의 설명을 다시보자.
- 쉽게 얘기하자면 동적 계획법은 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.
- 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.
1번의 설명은 쉽게 얘기하면 큰 문제를 풀기위해서 작은 문제로 나눠서 푼다는 말이다.
피보나치 수 구하는 문제가 대표적인 예다.
Fibonacci(N)을 구하기 위해서 Fibonacci(N-1)과 Fibonacci(N-2)로 나눠서 푸는 방법이기 때문이다.
그렇다면 첫번째 코드는 DP인가? 답은 아니다. 왜냐하면 2번의 설명에 부합하지 않기 때문이다.
2번의 설명은 쉽게 말하자면, 문제를 한번이상으로 풀지 않겠다는 것이다.
풀었던 문제를 또 풀지 말라는 말이다.
첫번째 코드의 가장 큰 문제점은 Fibonacci(N)을 구하기 위해서 계속해서 풀었던 문제를 거듭해서 다시 풀게 된다. 그래서 숫자가 커지게 된다면 당연히 시간은 오래 걸릴 수 밖에 없는 것이다.
정리하자면 Dynamic Programming은 큰 문제를 풀기위해서 작은 문제로 나눠서 푸는데 더 큰 문제를 해결하는 방식인데 문제를 해결하는 과정에서 계산의 답들을 저장함으로 반복 계산을 방지할 수 있는 방법이라고 생각하면 된다.
이것을 해결하는 첫번째 방법이 메모이제이션(Memoization) 방식이다.
위에 있는 Top-Down 코드를 보게 된다면 memo라는 배열을 설정해 두고 그곳에 한번 풀었던 답을 저장하게 된다. 그리고 다음에 다시 그 문제를 풀어야하는 상황이 오면 문제를 다시 푸는게 아니라 memo했던 것을 꺼내서 계산하게 된다. 이러한 반복 문제풀이를 없애기 때문에 시간복잡도(Time Complexity)가 획기적으로 줄일 수 있다.
이러한 DP를 구현하는 방식은 크게 두가지가 있다.
Top-down
이렇게 위의 방법을 DP 동적 계산법의 Top-down 방식(하향식)이라고 한다.
주로 문제를 Recusive 함수를 사용해서 해결해야 할 때 함수 호출 또는 반복되는 계산을 줄이기 위해서, 앞서 말했던 메모이제이션을 사용한다.
Bottom-up
Bottom-up(상향식)은 아래쪽에서 작은 문제를 하나씩 해결해 나가면서 먼저 계산했던 문제들의 값을 이용해서 다음 문제들을 차례대로 해결해나가는 방식이다.
추가적으로 내가 해결한 소스코드는 아니지만 Bottom-up방식으로 같은 문제를 해결한 방법을 발견해서 같이 업로드 하겠다.
Bottom-Up Code
#include <stdio.h>
#include <string.h>
long long memo[100];
int main(void) {
int N;
scanf("%d", &N);
memset(memo, 0, sizeof(memo));
memo[0] = 0LL;
memo[1] = 1LL;
for(int i = 2; i <= N; i++)
memo[i] = memo[i-1] + memo[i-2];
printf("%lld\n", memo[N]);
return 0;
}따로 설명하지 않아도 방식만 다르지 똑같은 원리임을 알 수 있을 것이다.
