코딩 테스트 문제 중에서 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 엄청나게 증가시킬 수 있는 방법이 있다. 대표적인 방법으로 다이나믹 프로그래밍이 있는데 오늘은 이에 대해서 알아보려고 한다.
📌 다이나믹 프로그래밍이란?
큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 즉, 중복되는 연산을 줄이고 메모리를 조금 더 사용해 연산속도를 줄인다는 것이다. 보통 줄여서 DP라고 부르며, 동적계획법이라고 부르기도 한다. 예시를 보며 DP를 좀 더 이해해보자.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다.
다음과 같이 재귀를 이용해 피보나치 수를 구하는 함수를 만들었다고 해보자.
int fibo(int x) {
if (x == 1 || x == 2) return 1;
return fibo(x - 1) + fibo(x - 2);
}하지만 이렇게 구현하게 되면 시간복잡도가 O(2^N)으로, 매우 많은 연산을 수행해야 한다. (예를 들어 N=30이면 약 10억 정도의 연산을 수행하게 된다.)
연산의 과정을 생각해보면, N=5일 때 fibo(4) + fibo(3)을 수행하게 되고, 여기서 fibo(4)에서는 fibo(3) + fibo(2)를, fibo(3)에서는 fibo(2) + fibo(1)을 호출하게 된다. 결국 겹치는 연산이 많아지게 되어 연산량이 늘어난 것이다.
우리는 이 문제를 DP를 이용해 효율적으로 풀 수 있다.
DP를 구현하는 방법 중 한 종류인 메모이제이션(Memoization)을 사용한 코드를 보자.
int d[100];
int fibo(int x) {
if (x == 1 || x == 2) return 1;
if (d[x] != 0) return d[x];
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}실행시켜보면 속도가 훨씬 빠른 것을 볼 수 있다.
이렇게 DP를 적용했을 때의 시간복잡도는 O(N)이 된다! (한 번 구한 결과는 다시 구하지 않기 때문이다.)
하지만 DP는 항상 사용할 수는 없으며, 다음과 같은 2가지 조건을 만족할 때만 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
앞서 본 피보나치 수열은 위의 조건을 만족하는 것을 알 수 있다.
💡 참고 💡
DP는 재귀 함수보다 반복문을 사용하는 것이 성능이 더 좋다.
📌 DP 기법 종류
메모이제이션
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 캐싱(Caching)이라고도 한다.
탑다운 방식 (Top-Down)
위의 예시에서 봤던 것처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 한다.
바텀업 방식 (Bottom-Up)
단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 한다고 하여 바텀업 방식이라고 한다.
피보나치 수열 문제를 바텀업 방식으로 풀면 다음과 같다.
int d[100];
int fibo_bu(int x) {
d[1] = 1;
d[2] = 2;
for (int i = 0; i < x + 1; i++) {
d[i] = d[i-1] + d[i-2];
}
return d[x];
}
DP의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
🔗 참고자료
