🙌 DP(Dynamic Programming)와 메모이제이션(Memoization)

---

🧮DP(Dynamic Programming)

• 동적 프로그래밍은 문제를 작은 부분 문제로 나누고, 그 해를 결합하여 원래 문제를 해결하는 알고리즘 설계 패러다임입니다.

동적 프로그래밍은 복잡한 문제를 여러 개의 작은 부분 문제(sub-problems)로 나누어 해결하는 알고리즘 설계 패러다임입니다. 이러한 부분 문제의 해를 저장하여, 같은 부분 문제가 여러 번 나타날 때 다시 계산하지 않고 저장된 값을 재활용하는 것이 동적 프로그래밍의 핵심 아이디어입니다.

• 시간 복잡도 : $O(n)$

• 공간 복잡도 : $O(1)$

탑-다운 (Top-Down)

재귀로 구현, "기저 조건(Base Case)" 필수

1. 코드 이해하기 쉬움: 재귀적인 구조는 문제를 자연스러운 형태로 나누기 때문에 코드가 더 이해하기 쉬울 수 있습니다.

2. 개발 속도 빠름: 재귀 함수를 사용하면 복잡한 문제도 비교적 빠르게 구현할 수 있습니다.

3. 함수 호출 오버헤드: 재귀 호출에는 일정한 오버헤드가 발생합니다.

4. 메모리 사용량: 재귀 호출로 인해 스택 메모리가 늘어날 수 있습니다.

5. 따로 최적화 필요: 꼬리 재귀 등을 활용하지 않으면 스택 오버플로우의 위험이 있습니다.

바텀-업 (Bottom-Up)

반복문을 통해서 구현

1. 효율성: 일반적으로 함수 호출 오버헤드가 없고, 루프를 통해 연산을 수행하기 때문에 빠를 수 있습니다.

2. 메모리 최적화: 필요한 만큼의 메모리만 사용하므로 메모리 효율성이 높을 수 있습니다.

3. 코드 이해하기 어려움: 문제를 비재귀적으로 풀어야 하므로, 코드의 이해가 복잡해질 수 있습니다.

4. 개발 속도 느림: 작은 문제부터 차근차근 해결해야 하므로 개발 속도가 느릴 수 있습니다.

---

📝메모이제이션(Memoization)

• 메모이제이션은 동적 프로그래밍에서 사용하는 테크닉 중 하나로, 이미 계산한 부분 문제의 해를 저장해두는 것을 의미합니다.

메모이제이션은 동적 프로그래밍의 한 방법으로, 이미 계산한 부분 문제의 해를 저장해두는 테크닉을 의미합니다. 이렇게 하면 동일한 부분 문제가 다시 나타났을 때, 불필요한 계산을 피하고 저장된 값을 사용하여 효율성을 높일 수 있습니다.

• 시간복잡도 : $O(2^n)$

• 공간복잡도 : $O(n)$

---

🥕 DP(Dynamic Programming)와 메모이제이션(Memoization)의 관계

동적 프로그래밍(Dynamic Programming, DP)과 메모이제이션(Memoization)은 밀접하게 관련되어 있지만, 정확하게 같은 개념은 아닙니다.

메모이제이션은 동적 프로그래밍의 일종이라고 볼 수 있으며, 동적 프로그래밍을 구현할 때 자주 사용되는 방법 중 하나입니다.