썸넬 Img ref :
https://fullmoon1344.tistory.com/67

🌱 DP(Dynamic Programming, 동적 계획법)

---

문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘입니다. 풀이 방법에는 상향식 타뷸레이션과 하향식 메모이제이션이 있습니다. 타뷸레이션은 작은 문제의 정답을 이용하여 큰 문제를 해결하는 식이고, 메모이제이션은 재귀 과정에서 이미 계산된 값인지 확인하고 바로 리턴하고 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 재활용합니다. 따라서 피보나치 수열에서 5번째 값을 구할 때 타뷸레이션에 비해 약 60% 정도의 연산으로 결과를 얻습니다.

Ex) 다익스트라 알고리즘, 0-1 배낭 문제(짐을 쪼갤 수 없는 경우), 피보나치 수열

• 메모이제이션

class Solution:
    dp = collections.defaultdict(int)

    def fib(self, N):
        if N <= 1:
            return N

        if self.dp[N]:
            return self.dp[N]
        self.dp[N] = self.fib(N - 1) + self.fib(N - 2)
        return self.dp[N]

• 파뷸레이션

class Solution:
    dp = collections.defaultdict(int)

    def fib(self, N):
        self.dp[0] = 0
        self.dp[1] = 1

        for i in range(2, N + 1):
            self.dp[i] = self.dp(i - 1) + self.dp(i - 2)
        return self.dp[N]

🌿 동적 계획법이 갖는 2가지 특징

---

최적 부분 구조와 중복된 하위 문제들입니다. 최적 부분 구조는 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 것을 말합니다. 그리고 중복된 하위 문위 문제들의 결과를 저장해뒀다가 풀이해 나갑니다.

🌿 그리디 알고리즘과 DP의 차이

---

그리디 알고리즘은 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이해 나가는 것이고, 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해 나간다는 차이가 있습니다. 결론적으로 중복되지 않은 문제는 DP로 풀이할 수 없습니다. 이것은 보통 분할 정복 방식으로 풀이합니다.

📌 분할 정복 방식

직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 분할한 다음, 그 하위 문제를 해결하여 정복하고 그 결과들을 조합하여 원래 문제의 결과로 만들어 내는 방식입니다. 주로 활용되는 문제로 최적 부분 구조가 있습니다.

Reference URL : 알고리즘 인터뷰 by 박상길