동적 계획법(Dynamic Programming, DP)

• 설명

다이나믹 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 간단한 하위 문제들로 나누어 해결하는 알고리즘 설계 기법이다. DP는 주로 중복된 하위 문제들이 존재할 때 효율적으로 문제를 해결하는 데 사용된다. 핵심 개념은 "작은 문제들을 먼저 풀고, 그 결과를 이용해 더 큰 문제들을 해결"하는 것이다.

---

• 접근 방근

1. 상향식 접근 (Bottom-Up Approach):

 

작은 하위 문제들로부터 해결해 나가며 점점 큰 문제를 해결하는 방법이다. 일반적으로 반복문을 사용해 테이블을 채워가며 문제를 해결한다.

 

ex) 피보나치 수열을 계산할 때, 피보나치 수 F(n)을 계산하기 위해 F(0) 부터 F(n - 1)까지 차례로 계산하고, 이를 통해 F(n)을 계산한다.

 

2. 메모이제이션(Memoization):

 

재귀적은 방법을 사용하되, 이미 계산된 하위 문제의 결과를 저장해 두었다가 필요할 때 바로 사용하는 방식이다. 상향식 접근과 달리, 큰 문제를 풀기 위해 작은 문제들을 재귀적으로 해결한다.

 

ex) 피보나치 수열에서 F(n)을 구할 때, F(n - 1)과 F(n - 2)를 먼저 계산하고, 이를 메모이제이션 테이블에 저장한 후 필요시 사용한다.

---

• 장점 & 단점

장점: 많은 중복 계산을 피할 수 있어, 시잔 복잡도를 크게 줄일 수 있다.

 

단점: 메모리 사용량이 늘어날 수 있으며, 문제에 따라 테이블의 크기가 커질 수 있다.

 

결론적으로, 다이나픽 프로그래밍은 최적화 문제를 풀 때 매우 유용한 알고리즘으로, 특히 하위 문제들이 중복되는 문제에서 큰 효과를 발휘한다.

 

 

DP를 사용한 백준 문제 풀이

https://d0ng2.tistory.com/15

[C언어] 백준 1003번: 피보나치 함수