동적 계획법

thsamajiki·2022년 10월 25일

알고리즘

목록 보기

4/8

배경

피보나치 수열

동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있다. 피보나치 수열은 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된다. 제0항은 생략하기도 한다. 수열은 아래와 같다.

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현한다.

아래는 피보나치 수열의 n번째 수를 구하는 함수이다.

int fibo(int n)
{
    if (n <= 2) {
	      return 1;
		} else {
	      return fibo(n - 1) + fibo(n - 2);
		}
}

fibo(6)은 어떻게 실행될까? 아래 사진을 보자.

Untitled

fibo(4)의 연산이 두 번, fibo(3)의 연산이 세 번 진행되는 것을 볼 수 있다. 이미 진행됐던 연산인데도 불구하고 말이다.

동적 계획법의 등장

위의 예시처럼 이미 했던 연산이 반복되는 결점을 보완하기 위해서 동적 계획법(Dynamic Programing, DP)이 고안되었다. 원리는 간단하다. 처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져오는 것이다.

동적 계획법으로 구하는 피보나치 수열

int[] fiboData = new int[100];

int fibo(int n)
{
	  if (n <= 2) {
		    return 1;
		}

		if (fiboData[n] == 0) {
		    fiboData[n] = fibo(n - 1) + fibo(n - 2);
		}

		return fiboData[n];
}

fiboData라는 배열을 생성한다. 이 배열에는 연산한 값들이 저장될 예정이다. n이 2 이하일 경우 1을 반환하고, 그 이상일 경우 fiboData[n]에 연산 값이 없는지 검사합니다. 없을 경우, 새로 연산해서 fiboData[n]에 값을 저장하고, 반환합니다. 만약 연산 값이 존재한다면 바로 fiboData[n]을 반환하게 됩니다. 재귀와는 다르게 중복되는 연산이 사라졌죠?

개념

피보나치 수열을 재귀로 표현했을 때의 결함을 동적 계획법으로 보완한 사례를 보면서 눈치챘을 것이다. 동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘이다.

메모이제이션(Memoization)

위의 코드에서는 하위 문제를 해결할 때 그 해결책을 저장해 두고, 똑같은 문제가 발생했을 때 저장되어 있던 해결책을 가지고 간단하게 해결했다. 이렇게 동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것을 메모이제이션(Memoization)이라고 한다.

TOP-DOWN

문제 풀이가 위에서 아래로 진행되는 것을 말한다. 위의 코드를 다시 보자.

int[] fiboData = new int[100];

int fibo(int n)
{
	  if (n <= 2) {
		    return 1;
		}
	  if (fiboData[n] == 0) {
		    fiboData[n] = fibo(n - 1) + fibo(n - 2);
		}
  
		return fiboData[n];
}

fibo(6)을 호출하게 되면 fibo(6)부터 작은 수를 호출하며 가장 작은 수까지 도달하게 되는 방식이다. 이 방식에서는 메모이제이션이 사용되었다.

BOTTOM-UP

TOP-DOWN 방식과 다르게 문제 풀이가 아래에서 위로 진행되는 것을 말한다.

int fibo(int n)
{
	  fibodata[0] = 0;
	  fiboData[1] = 1;
	  for (int i = 2; i <= n; i++) {
		    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
		}

		return fiboData[n];
}

fibo(6)을 호출하게 되면 어떤 흐름으로 전개될까? for문 내에서 fiboData[2]부터 fiboData[6]까지 점진적으로 계산해 나갈 것이다. 이렇게 처음 값부터 계산해 최종 값까지 계산해 내는 것이 BOTTOM-UP 방식이다.

장점과 단점

동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘이다. 여기서 그리디 알고리즘(탐욕 알고리즘)과 대비된다.

그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식이다. 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없다.

하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택한다. 그런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있다.

동적 계획법과 재귀적 방법의 비교

재귀 함수를 이용한 피보나치 수열

int recursiveFibo(int n){
    if(n == 1 || n == 2) {
				return 1;
		}

    return recursiveFibo(n - 1) + recursiveFibo(n - 2);
}

재귀 함수는 일단 보기 편하고 다른 변수를 많이 사용하지 않아도 표현할 수 있다는 장점이 있다. 재귀 함수는 자신을 리턴해주기 때문에 변수 자체를 많이 쓰지 않는다.

문제는 재귀 함수를 사용할 경우 반복문에 비해서 메모리를 많이 먹고 느리다.

보통 함수를 호출할 때 스택에 여러 변수들과 리턴값, 함수가 종료되고 돌아갈 주소 등이 저장된다. 이 때 재귀 함수를 쓸 경우 반복적으로 호출하기 때문에 스택에 메모리가 많이 쌓이고, 상황에 따라 Stack Overflow가 발생할 수 있다. 또한 스택 프레임을 구성, 해제하는 과정에서 당연히 시간이 들기 때문에 기본적인 반복문에 비해 시간도 많이 걸린다.

이런 단점을 보완하고자하는 방법이 반복문을 이용한 동적 계획법(Dynamic Programming) 이다. 반복문을 사용하며 배열을 이용해 결과값을 저장하고 그것을 다시 재활용하기 때문에 재귀함수에서 $O(n^2)$ 시간이 들 수 있는 알고리즘을 $O(n)$ 시간으로 단축할 수 있는 효과가 있다.

동적 계획법을 이용한 피보나치 수열

int dpFibo(int n){
		int[] dp = new int[3];
    dp[0] = 0;
    dp[1] = 1;
    int i = 2;
    while(i <= n){
        dp[2] = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = dp[2];
        i++;
    }
    
    return dp[2];
}

핵심은 dp라는 배열 3개만으로도 결과를 도출할 수 있다는 것이다. 일단 dp[2]에는 현재값을 저장하고 DP[1]에 있던 값을 dp[0]에 옮기고, dp[2]에 있는 현재값을 DP[1]에 옮김으로써 원래라면 dp[3]에 가야하는 값을 dp[0] + dp[1] (원래는 dp[1] + dp[2]의 값)을 연산하고 dp[2]에 다시 저장함으로써 저장공간을 극도로 아낄 수 있다. 단점은 2개의 값 말고 이전의 값들을 재활용 할 수 없다는 것이다. 이 경우 피보나치의 수열의 마지막 값을 구하고자 하는 것이 목표이기 때문에 이런 활용도 가능하다.

시간을 분석하면 아래와 같이 나온다.
Untitled