알고리즘 - 다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍?

---

다이나믹 프로그래밍이란 큰 문제를 작은 문제로 나누어 해결하고 작은 문제의 결과를 재사용하면서 중복 계산을 피하며 작업을 줄여 효율적으로 문제를 해결하는 방법이다. 이때, 작은 문제를 하위 문제라고 한다. 하위 문제는 동일한 문제를 작게 만들어 해결함으로써 어떤 문제를 풀 때 더 작은 문제이다.

 

재귀 호출은 프로그램을 단순하게 만들 수 있지만, 불필요한 재귀 호출이 일어나면 재귀 코드의 속도를 느리게 만들 수 있다. 그래서 불필요한 재귀 호출이 일어나지 않도록 해야 한다. 하위 문제가 중첩되는 이유는 같은 함수를 여러 번 중복해서 호출하기 때문이다. 이러한 불필요한 호출을 줄이기 위해서 필요한 함수 호출을 한 번만 하고 그 결과를 변수에 저장한다.

 

피보나치 수열

다이나믹 프로그래밍으로 해결하면 좋은 전형적인 문제인 피보나치 수열을 예시로 들어보자.

const fibonacci = (n) => {
	if( n === 0) return 0;
    if( n === 1) return 1;
    
    return fibonacci(n - 2) + fibonacci(n - 1)
}

 

- 베이스 케이스 : n이 0일 경우 0을 반환한다. n이 1일 경우 1을 반환한다.

- 나머지 숫자가 n인 경우 : 현재 피보나치 수 = 피보나치 두 번째 전 값 + 피보나치 바로 이전 값

 

예를 들어 n이 5라고 가정한다면,

트리가 균형하다고 가정한다면 주어진 숫자만큼의 깊이 있는 트리가 만들어 진다. 총 개수는 n^2개 만큼 되므로 빅오는 O(n^2)이다. 수가 증가할수록 급격하게 실행 속도가 느려질 것이다. 이렇게 급격하게 느려지는 이유는 중복된 계산 때문이다. 

위 문제를 다이나믹 프로그램으로 해결해보자.

 

하향식 다이나믹 프로그래밍 (메모이제이션)

메모이제이션은 계산된 결과를 미리 저장해 두었다가, 이미 계산했다면 계산된 결과를 사용하도록 해서 불필요한 재귀 호출을 없애는 방법이다.

 

const fibonacci = ( n, memo = []) => {
	if(n===0) return 0;
    if(n===1) return 1;
    
    if(!memo[n]) {
    	memo[n] = fibonacci(n-2, memo) + fibonacci(n-1, memo);
    }
    
    return memo[n];
}

memo라는 파라미터에 계산한 값을 저장하고 함수로 전달해 주면서 재사용을 한다. 이미 저장되어 있으면 저장된 값을, 저장되어 있지 않다면 계산을 해서 저장을 해놓고 그 값을 반환한다.

 

아래 트리를 보면 왼쪽으로만 뻗어나가는 모양인 것을 확인할 수 있다. 입력이 N일 때 N개 정도가 생기기 때문에 빅오 표기법으로 표현하면 O(N)이라고 할 수 있다.

그러나 이러한 메모제이션 방법은 추가적으로 메모리를 사용하고 재귀적인 호출은 스택을 필요로 하기 때문에 메모리적으로 비효율적이다.

 

상향식 해결 방법

상향식 해결 방법은 재귀가 아닌 다른 루프 함수나 다른 방식을 사용해서 해결하는 것으로 아예 반복적인 재귀 호출이 일어나지 않도록 할 수 있다.

const fibonacci = (n, current = 2, a = 0, b = 1) => {
	if(n===0) return 0;
    if(n===1) return 1;
    if(n===current){
    	return a + b;
    }
    
    return fibonacci(n, current + 1, b, a + b);
}

상향식 해결 방법의 특징은 이전에 저장된 것을 계속 가지고 간다는 것이다.

 

위 코드를 그림으로 보면 이러한 구조를 보인다. 실행 속도를 확인하면 하향식보다 조금 빨라진 것을 확인할 수 있다. 증가하는 단계 수와 n이 증가할 때 단계가 똑같이 증가하기 때문에 빅오로 O(N)이라는 것을 알 수 있다. 보통 재귀가 매우 직관적이지 않은 이상 상향식을 택하는 방법이 낫다. 재귀가 더 직관적이면 재귀를 사용하되 메모제이션으로 빠르게 만들어야 한다.