ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 동적 계획법(Dynamic Programming) - 기본
    CS/Algorithms 2020. 12. 9. 21:24

    동적 계획법(Dynamic Programming) 짧게 줄여서 DP 라고 부르는 이 알고리즘은 분할정복(Divide and Conquer) 알고리즘과 마찬가지로 복잡한 문제를 여러 개의 부분 문제들(Sub-problem) 으로 나누어 푼 후, 그 결과를 이용하여 복잡한 문제를 푸는 알고리즘이다.

    다만 분할정복 알고리즘과의 차이는 DP 에서는 각 부분 문제들간에 겹치는 부분이 존재한다는 것인데, DP 는 이러한 겹치는 부분들을 메모이제이션(Memoization) 이라는 기법을 사용하여 단 한 번만 계산하도록 함으로써 알고리즘의 작동 시간을 줄이는 게 핵심입니다.

     

     

    그렇다면 메모이제이션이라는 것은 무엇인지 알아봅시다.

     

    피보나치 수열을 예로 들면,

    아래와 같이 Fib(0) ~ Fib(3) 은 동일한 값을 구하는 연산이 중복되어 나타나 시간의 낭비가 생기는 것을 알 수 있습니다.

     

    이러한 낭비를 줄이기 위해 사용하는 방법이 메모이제이션입니다. 한 번 계산한 값은 메모리에 저장해두고 필요할 때 꺼내쓸 수 있도록 하여 연산의 중복을 줄이는 것입니다.

     

    이러한 메모이제이션을 이용하여 피보나치 수열을 구현하면,

    int Fibonacci(int n){
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // 이미 계산한 값을 가지고 있으면 더이상 진행하지 않고 해당 값을 리턴
        if (seq[n] != -1) return seq[n];
        
        seq[n] = Fibonacci(n-1) + Fibonacci(n-2);
        return seq[n];
    }

    위와 같이 구현할 수 있습니다.

    벡터의 초기화는 피보나치 수열에서 계산의 결과값으로 나올 수 없는 값인 -1로 해주었습니다.

     

    이처럼 메모이제이션을 사용하여 피보나치 수열을 구하는 알고리즘은 각 n 마다 하나의 값들을 구하면 되므로 O(n) 으로 일반적인 재귀형 알고리즘으로 피보나치 수열을 구현하였을 때 지수형 시간복잡도가 나오는 것과 비교하여 보면 매우 효과적이라고 볼 수 있습니다.

    'CS > Algorithms' 카테고리의 다른 글

    [알고리즘] 재귀(Recursion) - 하노이탑  (0) 2020.08.04
Designed by Tistory.