🧩 Dynamic Programing

안녕하세요 :) 오늘은 Dynamic Programing(DP)에 대해 알아보겠습니다. 피보나치 수를 구하는 방법처럼, 특정 문제를 중복되는 작은 문제로 쪼개어 풀 때, 효율적인 방법으로 사용되는 방법입니다. BF 알고리즘에서 한 층 더 발전된 알고리즘으로 접근하시면 좋습니다. 그럼 오늘도 화이팅 입니다🌿

Dynamic Programing 이란 ?

큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로, 주어진 문제의 크기(N)에 대한 점화식과 메모제이션 기법을 통해 문제를 해결하는 방법입니다.

분할정복과 다이나믹 프로그래밍의 차이점

• 분할정복 : 큰 문제를 나눈 작은 문제가 중복이 되지 않아, 모든 작은 문제를 한 번씩 푸는 방법입니다.
• 다이나믹 프로그래밍 : 큰 문제를 나눈 작은 문제가 중복이 되어, 여러번 나오는 각각의 작은 문제들은 단 한 번씩만 푸는 방법입니다.

---

DP 풀이 대상의 특성 2가지

Overlapping Subproblem

• Overlapping Subproblem란 큰 문제를 나눈 작은 문제들이 겹치는 특성을 의미합니다.

• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있습니다.

  → 문제를 작은 문제로 쪼갤 수 있습니다.

Optimal Substructure (최적 부분 구조)

• Optimal Substructure란 문제의 크기와 시점에 상관없이, 한 문제의 정답은 항상 같다는 특성을 의미합니다.

• 어떠한 작은 문제를 풀던, 그 전에 푼 특정 작은 문제의 정답은 변하지 않는다.

  → 큰 문제의 정답을 작은 문제의 정답을 통해 구할 수 있습니다. 즉, 작은 문제들의 정답을 구성하여 큰 문제를 해결할 수 있습니다.

---

DP 핵심

• Overlapping Subproblem

  → 같은 문제들(중복되는 작은 문제들)은 한 번씩만 풀어야합니다. 즉, 모든 작은 문제의 집합은 한 번씩만 풀려야합니다. (중복이 없다는 의미로써의 집합)

• Optimal Substructure

  → 같은 문제들은 시점이나 크기에 상관없이, 구할 때마다 정답이 같으므로, 이전에 구한 정답들을 저장해놓아야합니다. (Memoization)

---

DP 풀이 순서

1. 문제에서 구하고자하는 것을 문장으로 나타냅니다. 즉, 뒤에서 세울 점화식에 대한 정의를 세웁니다.

   N-2 번째 피보나치 수와 N-1 번째 피보나치 수의 합인 N 번째 피보나치 수

2. 해당 문장에서 등장하는 부분 문제들을 정의합니다.

   N 번째 피보나치 수에 대한 부분 문제 : N-2 번째 피보나치 수, N-1 번째 피보나치 수

3. 앞서 정의한 내용들을 사용하여, 수식으로 점화식을 표현하고, 메모제이션을 위한 배열을 만듭니다.

   D[N] = D[N-1]+D[N-2]

---

DP 구현 방법

• 대부분의 문제는 두 방법 모두로 해결할 수 있고, 시간복잡도도 비슷하게 나오므로, 어느 것을 사용해도 상관이 없습니다. 자신 있는 방법으로 선택해서 풀면 됩니다.
• 다만, 두 방법이 항상 상호 대체가 가능한 것은 아닙니다. 두 방법을 구분해서 문제를 풀어야하는 경우도 있습니다만, 이는 어느정도 난이도가 있는 문제에 대한 내용이므로, 이 부분까지 대비한다면 두 방법 모두 골고루 사용하는 것이 좋습니다.

Top-Down

→ 재귀 함수를 사용 : 특정 문제를 해결하기 위해 필요한 부분 문제들부터 해결해나가는 방법

Bottom-Up

→ 반복문을 사용 : 가장 작은 부분 문제의 처음부터 끝까지 차례대로 해결하는 방법