[Algorithm] 동적 계획법 (Dynamic Programming, DP)

동적 계획법 (Dynamic Programming, DP)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘
  • 즉, 똑같은 연산을 반복하지 않도록 만들어준다.
• 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘
• 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것
  
• 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 각 문제의 결과를 저장하여 다시 큰 문제를 해결하는 데 사용한다.
• 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산될 수 있다.
  • 예를 들어 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 O(2ⁿ) 으로, 동적 계획법을 사용하면 O(f(n)) 으로 줄일 수 있다.

 

조건

1. Overlapping Subproblems (겹치는 부분 문제)

• 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
• 작은 문제에서 반복이 일어난다.

 

2. Optimal Substructure (최적 부분 구조)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
• 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.
• 같은 문제는 항상 정답이 같다.

• 만약, A - B 까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B 가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B 가 정답이 된다.
• 위의 그림에서 A - X 사이의 최단 거리는 AX2 이고 X - B 는 BX2 이다. 전체 최단 경로는 AX2 - BX2 이다. 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없다.

 

구현 방법

1. Bottom-Up 방식

• 작은 문제부터 차근차근 구하는 방법
• 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
• dp[0] 부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n] 까지 그 값을 전이시켜 재활용하는 방식
• Tabulation 방식
  • 반복을 통해 dp[0] 부터 하나하나씩 채우는 과정을 "table-filling" 하며, 이 Table 에 저장된 값에 직접 접근하여 재활용하므로 Tabulation 이라는 명칭이 붙었다고 한다. 사실상 근본적인 개념은 결괏값을 기억하고 재활용한다는 측면에서 *Memoization 와 크게 다르지 않다.
    • Memoization(메모이제이션) : 한 번 계산한 문제는 다시 계산하지 않도록 저장해 두고 활용하는 방식

 

2. Top-Down 방식

• 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법 (재귀 방식)
• dp[0] 의 기저 상태에서 출발하는 대신 dp[n] 의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0] 의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

 

vs 분할 정복

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않아 Memoization 기법을 사용 안 한다.

---

동적 계획법 - 위키백과, 우리 모두의 백과사전

동적 계획법(Dynamic Programming) | 👨🏻‍💻 Tech Interview

알고리즘 - Dynamic Programming(동적 계획법)

잔재미코딩 온라인 강의 사이트입니다