동적계획법(Dynamic Programming)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 동적 계획법은 복잡한 문제를 효율적으로 해결하는 알고리즘 설계 기법 중 하나이다.

② 동적 계획법은 일반적으로 다음과 같은 단계로 수행된다.

  ㉠ 문제를 하위 문제로 나눈다.

  ㉡ 가작 작은 크기의 하위 문제부터 해를 구한다.

  ㉢ 작은 하위 문제의 해를 저장하고, 큰 문제의 해를 계산할 때 이를 이용한다.

  ㉣ 모든 하위 문제의 해를 계산하여 최종적인 문제의 해를 구성한다.

③ 동적계획법을 사용하기 위해선 문제가 최적 부분 구조와 중복 부분 문제를 만족해야 한다.

  ㉠ 최적 부분 구조(Optimal Substructure)를 갖는 문제는 큰 문제의 최적해가 작은 하위 문제들의 최적해로 구성되는 경우를 말한다.

    ⓐ 정점 A, B, C, D가 존재하고 각 경로에 가중치가 다음과 같이 주어져 있을 때 간선을 한 번 씩만 지나고 최장경로를 구해보자.

    ⓑ 정점 A에서 정점 D로 가는 최장 경로는 A->C->B->D이다.

    ⓒ 정점 A에서 정점 C로 가는 최장 경로는 A->B->C이다.

    ⓓ 정점 A에서 정점 D로 가는 최장 경로는 정점 A에서 정점 C로 가는 최장 경로를 포함한다. 그러나 A->B->C->B->D는 유효한 경로가 아니기 때문에 최장 경로 문제는 최적의 원칙이 성립하지 않는다고 할 수 있다.

  ㉡ 중복 부분 문제(Overlapping Subproblems)를 갖는 문제는 큰 문제를 해결하기 위해 동일한 작은 하위 문제가 반복적으로 발생하는 경우를 말한다.

    ⓐ 피보나치 수열은 재귀를 이용해 구현할 수 있다.

 

      - Fib(5)를 구하기 위해서 필요한 값은 Fib(4), Fib(3) 이다.

      - Fib(4)를 구하기 위해서 필요한 값은 Fib(3), Fib(2)이다.

      - Fib(3)을 구하기 위해서 필요한 값은 Fib(2), Fib(1)이다.

      - Fib(2)를 구하기 위해서 필요한 값은 Fib(1), Fib(0)이다.

      - Fib(1)과 Fib(0)은 각각 1과 0이다.

    ⓑ 피보나치 수열의 중복 부분 문제를 해결하기 위해 동적 계획법을 사용할 수 있다.

    ⓒ Fib(n)을 구하기 위해서 Fib(n-1)와 Fib(n-2)만 알면 된다.

    ⓓ 초기 조건이 Fib(0) = 0, Fib(1)이므로 이전 두 항을 저장하면 피보나치 수열을 구할 수 있다.

④ 작은 하위 문제들의 해를 저장하여 재사용하는 기법을 메모이제이션(Memoization)이라고 한다. 이는 중복 계산을 피할 수 있게 해준다.

⑤ 작은 하위 문제에서 상위 문제로 올라가면서 해결하는 기법을 Bottom-up Approach 라고 한다.

⑥ 동적 계획법은 중복 계산을 피하고 작은 하위 문제들의 해를 재상용하기 때문에 시간복잡도를 줄일 수 있다.