👋 다이나믹 프로그래밍에 대해 알아보고 PS 도전해보자!
✏️ 다이나믹 프로그래밍?
✔️ 다이나믹 프로그래밍의 등장
컴퓨터의 등장으로 현실 세계의 다양한 문제들이 쉽게 해결되고 있지만 여전히 컴퓨터를 활용해도 해결하기 어려운 문제들이 존재한다. 최적의 답을 구하기 위해 막대한 시간과 메모리 공간이 필요한 문제들이 이에 해당한다. 만약 문제를 해결하기 위해 100년의 연산 시간이 걸린다면 이것을 두고 문제를 해결했다! 라고 말하기 어려울 것이다.
피보나치(ㅁㅊ단골) 문제는 대표적인 시간 복잡도가 높은 문제 중 하나이다. 재귀를 이용한 구현으로는 O(2^n)의 지수시간이 소요되며, 만약 n이 100이라면 1,000,000,000,000,000, ... 번 가량의 연산을 수행해야 한다. 숫자만 봐도 알 수 있듯 우리가 죽기 전까지 연산이 끝나지 않을 것이라는 의미이다.
//재귀를 이용한 피보나치의 구현
int fibo(int n) {
if (n==1 || n==2) return 1;
return fibo(n-1) + fibo(n-2);
}✔️ 다이나믹 프로그래밍의 정의
이러한 골칫덩어리 친구들을 위해 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법 중 가장 대표적인 것을 다이나믹 프로그래밍이라 부른다. 한 마디로 1) 큰 문제를 작게 나누고 2) 이미 해결했던 문제라면 이전의 결과값을 가지고 문제를 효율적으로 해결하는 것이다!
다이나믹 프로그래밍을 사용하기 위해서는 두 가지의 조건이 필요하다.
- 큰 문제를 작은 문제로 나눌 수 있다
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치를 예를 들어 설명해보자!
피보나치의 n번째 항을 fibo(n)이라고 표현해보겠다. 그럼 fibo(4)를 구하기 위해 위의 코드를 실행시켜 보면 아래의 그림과 같이 함수가 호출된다.
이 때, 그래프에서 fibo(2) 는 중복되어 호출되는 것을 확인할 수 있다. 그럼 연산 과정에서 굳이 다시 fibo(2)를 연산하지 말고, 처음 fibo(2)를 계산하고 그 값을 저장해놓은 뒤에 그 이후의 연산에서는 그냥 값을 꺼내다 쓰면 어떨까?
이러한 방법을 Memoization 이라고 부른다! Memoization은 값을 저장하는 방법이므로 Caching 캐싱 이라고도 할 수 있다.
✔️ 다이나믹 프로그래밍의 두 가지 기법
그럼 위에서 알아본 다이나믹 프로그래밍의 기본 원리들은 어떻게 구현할 수 있을까? 다이나믹 프로그래밍에는 1️⃣ 탑다운 top down, 2️⃣ 바텀업 bottom up 2가지의 기법이 있다. 이름에서도 유추해볼 수 있듯 탑다운은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이고, 바텀업은 작은 문제부터 차근차근 답을 도출하는 방식이다.
탑다운은 하향식, 바텀업은 상향식이라고도 하며 다이나믹 프로그래밍의 전형적인 형태는 Bottom Up 방식이다. Bottom Up 방식에서 사용되는 결과 저장용 테이블을 dpTable이라고 하고 memoization은 탑다운 방식에 국한되어 사용하는 표현이다.
이해를 돕기 위해 피보나치 수열을 두 가지 방식으로 구현을 해보았다!
탑다운 Top Down
▶️ fibo(n) (큰문제)를 구하기 위해 fibo(n-1), fibo(n-2) (작은 문제) 호출
unsigned long long fiboTopDown(int n, std::vector<unsigned long long> &dpTable) {
if (n==1 || n==2) return 1;
if (dpTable[n] != 0) {
std::cout << dpTable[n] << "\n";
return dpTable[n];
}
dpTable[n] = fiboTopDown(n-1, dpTable) + fiboTopDown(n-2, dpTable);
return dpTable[n];
}바텀업 Bottom Up
▶️ fibo(n) (큰문제)를 구하기 위해 fibo(m++)부터 차근차근 계산
unsigned long long fiboBottomUp(int n, std::vector<unsigned long long> &dpTable) {
dpTable[1] = 1;
dpTable[2] = 1;
int m = 3;
while (m != n + 1) {
dpTable[m] = dpTable[m-1] + dpTable[m-2];
m++;
}
return dpTable[n];
}추가) unsigned long long 타입을 써도 90번째 항까지 밖에 표현이 안된다는데 그 이후의 값들은 어떻게 처리해야 되는지 공부해봐야겠다 🤔
참고자료
