동적 계획법

동적 계획법은 알고리즘 대회에서 가장 많이 나오는 문제 유형 중 하나로, 문제가 반복되는 부분 문제로 이루어졌을때 사용하는 기법입니다.

동적 계획법을 모든 문제에 적용할 수 있는것은 아니며 아래의 두 조건이 충족되어야 합니다.

  • 최적 부분 구조(Optimal Substructure)
    • 원래 문제의 답이 부분 문제의 답으로부터 만들어지는 구조
  • 중복되는 부분 문제(Overlapping Subproblems)
    • 원래 문제를 작은 문제로 쪼갤 수 있음
    • 큰 문제와 작은 문제가 같은 방법으로 해결이 가능함
메모이제이션 (Memoization)

메모이제이션이랑 동일한 계산이 반복될 때 계산한 값을 저장하고 나중에 다시 계산하지 않고 이전에 미리 저장한 계산값을 다시 사용하는 기법을 말합니다. 이 기법은 동적 계획법과 떨어질래야 떨어질수 없는데 왜냐하면 동적 계획법을 적용할 수 있는 문제는 중복되는 부문 문제가 있기 때문에 메모이제이션을 해야 시간 복잡도를 크게 줄일수 있기 때문입니다.

동적 계획법의 가장 기초적이며 대표적인 문제인 피보나치 수를 이용하여 설명해 보겠습니다.

int fibonacci(int n){
    if (n < 2) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

피보나치 수를 구하는 평범한 재귀 함수입니다. 만약 fibonacci(6)을 호출하면 어떤 일이 발생할까요? 아래 이미지 처럼 재귀적으로 함수를 호출하게 되는데 여기서 fibonacci(2)fibonacci(3)이 여러번 호출되는 것을 알 수 있습니다. 피보나치 함수의 입력값이 커질 수록 중복 호출 수는 더 많아질 것이고 중복 호출은 매우 비효율적인 작업입니다. 왜냐하면 피보나치 함수의 결과 값은 입력값에 의해 결정되는, 참조 투명성을 보장하는 순수 함수이기 때문입니다. 그러므로 fibonacci(n)의 결과를 구했다면 그 결과를 다른 곳에 저장해놓았다가 나중에 똑같은 호출을 하게되면 다시 계산하지 않고 미리 구해놓은 값을 사용하면 실행 시간을 크게 줄일수 있습니다.

메모이제이션을 적용한 피보나치 함수는 아래와 같습니다.

int memo[1001];

int fibonacci(int n){
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

메모이제이션을 적용하면 이제 한 번 계산한 값은 더 이상 계산하지 않고 저장된 값을 반환하기 때문에 같은 함수 호출에 대해 첫 호출 이후에는 O(1)의 시간으로 답을 구할 수 있습니다.

탑다운(Top-Down), 바텀업(Bottom-Up)

동적 계획법은 두 가지 방식으로 구현이 가능합니다. 바로 탑다운 방식과 바텀업 방식인데, 이 둘의 구현은 상황에 따라 성능 차이가 크게 날 수도 있기 때문에 두 방식 모두 구현할줄 아는것이 좋습니다.

탑다운 방식은 큰 문제를 작은 문제로 나눈 뒤 작은 문제를 해결해가며 큰 문제를 해결하는 방식으로 대개 재귀 함수로 구현합니다. 위의 메모이제이션 설명에서 구현한 코드가 바로 탑다운 방식입니다.

바텀업 방식은 작은 문제를 먼저 해결하고 순차적으로 큰 문제를 해결하는 방식입니다. 아래는 바텀업으로 구현한 피보나치입니다.

int memo[1001];
int fibonacci(int n){
    memo[0] = memo[1] = 1;
    for(int i = 2; i <= n; i++)
        memo[i] = memo[i - 1] + memo[i - 2];
    return memo[n];
}