poArlim poArlim

동적 계획법(Dynamic Programming) 짧게 줄여서 DP 라고 부르는 이 알고리즘은 분할정복(Divide and Conquer) 알고리즘과 마찬가지로 복잡한 문제를 여러 개의 부분 문제들(Sub-problem) 으로 나누어 푼 후, 그 결과를 이용하여 복잡한 문제를 푸는 알고리즘이다. 다만 분할정복 알고리즘과의 차이는 DP 에서는 각 부분 문제들간에 겹치는 부분이 존재한다는 것인데, DP 는 이러한 겹치는 부분들을 메모이제이션(Memoization) 이라는 기법을 사용하여 단 한 번만 계산하도록 함으로써 알고리즘의 작동 시간을 줄이는 게 핵심입니다. 그렇다면 메모이제이션이라는 것은 무엇인지 알아봅시다. 피보나치 수열을 예로 들면, 아래와 같이 Fib(0) ~ Fib(3) 은 동일한 값을 구하는..