동적 계획법 (Dynamic Programming)

 

 

 

한 문제를 여러 부분으로 쪼개서 각각의 문제들을 해결한 다음 해결한 결과들을 합병해 문제를 해결하는 분할 정복과 비슷한 알고리즘이다.

 

동적 계획법은 최하단의 결과를 이용해 상단 결과를 해결하는 방식이고, 이전에 계산한 값을 저장해 다시 계산하지 않게 하는 메모이제이션 기법을 사용해 문제를 효과적으로 풀 수 있게 한다.

 

분할 정복에서는 메모이제이션을 사용하지 않아 쪼갠 문제들의 결과를 활용하지 않는다.

 

public class dp {
    public int dpfunc(int data) {
        int[] num = new int[data + 1];
        num[0] = 0;
        num[1] = 1;
        for (int i = 2; i < data + 1; i++) {
            num[i] = num[i - 1] + num[i - 2];
        }
        return num[data];
    }   
}

 

피보나치함수를 dp로 구현한 예시이다. 

 

간단한 예시를 통해 dp에 대해 감을 잡자.