DP 다이나믹 프로그래밍 개념

다이나믹 프로그래밍 구조

다이나믹 프로그래밍(Dynamic Programming)은 주어진 문제를 여러 하위 문제로 나누어 푸는 알고리즘 기법이다. 이를 통해 문제의 해결 방법을 동적으로 계산해서 이전에 계산한 결과를 저장하여 중복 계산을 피하고 효율을 높인다.

다이나믹 프로그래밍은 주로 최적화 문제에서 쓴다. 

그럼 특징을 알아보자.

1. 최적 부분 구조: 큰 문제의 최적 해결 방법이 작은 문제의 최적 해결 방법에서 구현.  작은 문제의 최적 해결 방법을 이용하여 전체 문제의 최적 해결 방법을 구한다.
2. 중복 부분 문제: 작은 문제를 해결하는 과정에서 중복된 하위 문제가 발생.(아파트 인구 문제같은)중복 계산을 피하기 위해 한 번 계산한 하위 문제의 해결 방법을 저장하고 재활용한다.(이전 호수에서 계산한 인구+)

다이나믹 프로그래밍은 보통 다음의 두 가지 방법으로 구현됩니다:

1. 상향식 접근법: 재귀적으로 문제를 해결하면서 이전에 계산한 결과를 저장하여 사용한다.
2. 하향식 접근법 작은 문제부터 시작하여 순차적으로 해결하면서 큰 문제의 해결 방법을 찾는다.

  public static int fibonacci(int n) {
        int[] f = new int[n+1];
        f[1]=f[2]=1;
        for(int i=3;i<=n;i++) {
            n2++;//호출이 일어나는부분2
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }

 

 

다이나믹 프로그래밍을 사용하여 피보나치 수열을 계산하는 대표적인 예시다. 

여기서 f 배열은 중간 결과를 저장하는 데 사용되는데, 이미 계산한 값은 배열에 저장되어 재사용한다. 이렇게 함으로써 중복 계산을 피하고 계산 효율성을 높인다.