안녕하세요 Kyun2da 입니다~오랜만에 포스팅을 진행해보네요
이번 포스팅은 다이나믹 프로그래밍(Dynamic Programming)에 대해서 알아보도록 하겠습니다.
1️⃣ 다이나믹 프로그래밍이란?
다이나믹 프로그래밍은 흔히 DP 혹은 동적프로그래밍, 동적계획법으로 불리기도 합니다.
쉽게 말해 답을 재활용하는 기법을 말합니다.
여기서 답을 재활용 한다는 의미는 Memoization을 말하는데, 이는 컴퓨터 용어로 동일한 계산을 할 경우 한번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법입니다.
이 기법은 메모리라는 공간적 비용을 투입해 시간적 비용⏰을 줄이는 방식입니다.
말로는 무슨말인지 잘 모르겠나요? 그러면 간단한 예제를 보며 DP에 대한 감을 익혀보도록 하겠습니다.
2️⃣ 간단한 예제- 피보나치 수
DP를 시작할 때 항상 하는 기초적인 DP 문제입니다.
☝️백준에도 피보나치 문제가 수록되어 있으니 한번 풀어보는 것도 도움이 될 것 같네요!
🚏그럼 예제문제를 통해 DP를 이해해 볼까요?
피보나치는 기본적으로 0번째는 0, 1번째는 1, 그 다음부터는 Fn=Fn-1+Fn-2를 만족하는 성질을 갖고 있습니다.
1
2
3
4
5
6
7
8
9
int fibonacci(int n)
{
if(n==0)
return 0;
else if(n==1)
return 1;
else
return fibonacci(n-1)+fibonacci(n-2);
}
우리는 보통 이런 재귀를 활용한 피보나치를 많이 사용하곤 했을 것입니다.
이 코드가 바로 Top-down 방식의 다이나믹 프로그래밍 인데요~😃
하지만 위의 코드는 n이 커지면 시간이 엄청나게 걸린다는 단점이 있습니다.
메모이제이션 기법을 활용한다면 이런 단점을 극복할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int main()
{
int arr[100];
arr[0] = 0, arr[1] = 1;
int num;
scanf("%d", &num);
for (int i = 2; i <= num; i++)
{
arr[i] = arr[i - 1] + arr[i - 2];
}
printf("%d",arr[num]);
return 0;
}
위와 같이 공간적 비용을 쓴다면 시간을 많이 단축시킬 수 있습니다.
이전의 결과들을 arr라는 배열에 저장해서 이전의 값들을 또 다시 계산해도 되지 않기 때문입니다.
이러한 유형의 문제를 dp라고 합니다.
3️⃣ DP 유형
다이나믹 프로그래밍을 푸는 방식에는 두가지 방법이 있습니다.
Top-DownBottom-Up
Top down 방식으로 문제를 푸는 방법은 다음과 같습니다.
- 문제를 작은 문제로 나눈다.
- 작은 문제들을 푼다.
- 작은 문제들의 답으로 전체 문제를 푼다.
Top down 방식은 보통 재귀로 구현이 됩니다.
1
2
3
4
5
6
7
8
9
10
int fibonacci(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (dp[n] != -1) return dp[n];
dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
return dp[n];
}
Bottom-Up 방식으로 문제를 푸는 방법은 다음과 같습니다.
- 가장 작은 문제부터 푼다.
- 문제의 크기를 점점 크게 만들어서 전체문제를 푼다.
1
2
3
4
5
6
int fibonacci(int n)
{
dp[0] = 0, dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
}
두 코드의 차이라고 장단점을 말하자면, Top-down 방식은 코드의 가독성이 증가되는 장점이 있습니다.
하지만 작성하기 어렵고 보통 재귀를 이용해 메모이제이션을 쓰지 않으므로 시간이 오래걸립니다.
반면, Bottom-Up방식은 시간이 적게걸리지만, 코드의 가독성이 조금 떨어진다는 단점이 있다고 합니다.
4️⃣ 분할정복과의 차이?
흔히들 DP와 분할정복의 차이에 대해서 헷갈려 하시는 분들이 많습니다.
분할 정복은 분할했을 경우 반복적인 문제가 발생하지 않습니다.
하지만 DP는 반복적인 문제가 발생하기 때문에 메모이제이션(Memoization)기법들이 필요하게 됩니다.
또한 이 과정에서 DP는 별도의 메모리를 소비하기 때문에 그리디 알고리즘에 비해 시간 복잡도는 크지만 문제를 풀 수 있는 스펙트럼이 넓고 근삿값이 아닌 최적의 값을 얻을 수 있습니다.
5️⃣ DP 연습하기
☝️dp 문제 유형이 정리된 백준의 단계별로 풀어보기 입니다. 위의 링크의 16문제를 풀어보면 dp의 기초가 충분히 잡힐 것이라고 생각합니다.
☝️위의 문제모음에대한 풀이 모음입니다. 보잘 것 없는 제 코드지만 참고용으로 따로 모아두었습니다.
마치며..
이상 Dynamic Programming 사용법과 접근법, 분할정복과의 차이에 대해 알아보았습니다.😊
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
