Dynamic Programming

Dynamic Programming 이란?

Dynamic Programming(동적 프로그래밍)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 방법으로, 각 하위 문제의 해결책을 저장하고 이를 활용하여 전체 문제의 해결책을 구하는 알고리즘 설계 기법이다.

이 방식은 중복 계산을 줄여주어서 효율적인 문제 해결을 가능하게 한다. 예시( 시간복잡도가 O(n^2) → O(f(n)) 으로 개선 )

해당 기법을 사용하기 위한 조건

Optimal Substructure(최적 부분 구조)

문제의 최적화 된 해결책이 그 문제의 하위 문제의 최적 해결책으로부터 구성될 수 있어야 합니다. 즉 하위 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일해야 합니다.

Overlapping Subproblems(중복되는 하위 문제)

문제를 해결하는 과정에서 동일한 하위 문제가 반복적으로 발생해야만 합니다.

또한 , 동적 프로그래밍은 주로 두가지 접근 방식을 가지고 있는데, 이부분도 알아보도록 하겠습니다.

두가지의 접근 방식

Bottom-Up Approach (상향식 접근법)

가장 작은 하위문제부터 시작하여, 점차적으로 더 큰 문제의 해결책을 구성해 나가는 방식입니다.

Top-Down Approach (하향식 접근법)

큰 문제를 시작으로 하여, 필요할 때 마다 하위 문제로 나누어 해결하는 방식입니다. 이 방식은 보통 재귀 호출을 이용하여 구현되며, 이미 해결한 하위 문제의 해결책들은 메모이제이션을 사용합니다.

Dynamic Programming 의 대표적 예시

대표적 예시는 피보나치 수열을 예시로 들 수 있습니다.
만약 피보나치 수열의 n번째 값을 구하는 문제라면, 각 번호의 피보나치 값은 그 이전 두 번호의 피보나치 값의 합으로 구할 수 있으며, 이 과정에서 중복되는 하위 문제들이 많이 발생합니다. 위에 작성되었던 상향식 또는 하향식 접근법을 사용하여 효율적으로 피보나치 수열의 값을 계산할 수 있습니다.