다이나믹 프로그래밍(DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 기법입니다. 이런 문제에 익숙하지 않은 분들은 처음 DP를 배울 때 점화식을 세우거나 구현하는데 어려워하시는 경우가 많습니다. 이 글에서는 DP 알고리즘을 효과적으로 구현하기 위한 핵심 고려사항들을 살펴보겠습니다.
배열의 정의 확실히 하기
다이나믹 프로그래밍에서 가장 중요한 첫 단계는 DP 배열의 정의를 명확히 하는 것입니다. 이 정의는 여러분이 풀고자 하는 문제의 상태를 정확히 표현할 수 있어야 합니다. 예를 들어, dp[i][j]가 무엇을 의미하는지 한 문장으로 정확하게 설명할 수 있어야 합니다.
배열의 정의가 모호하면 점화식을 세우기 어려워지고, 잘못된 알고리즘으로 이어질 수 있습니다. 가령, 최장 증가 부분 수열(LIS) 문제에서 dp[i]를 "인덱스 i까지의 최장 증가 부분 수열의 길이"로 명확히 정의하면 알고리즘의 방향성이 분명해집니다.
다차원 DP 문제의 경우, 각 차원이 어떤 상태를 나타내는지 명확히 해야 합니다. 예를 들어, 배낭 문제에서 dp[i][w]는 "처음 i개의 물건만 고려했을 때, 최대 무게 w까지 담을 수 있는 최대 가치"로 정의됩니다. 이런 명확한 정의가 있어야 올바른 전이 방정식을 도출할 수 있습니다.
마지막으로, 배열의 인덱스가 어떤 의미를 갖는지도 명확히 해야 합니다. 인덱스가 0부터 시작하는지, 1부터 시작하는지에 따라 기저 조건과 반복문의 범위가 달라질 수 있습니다. 이러한 세부사항들이 명확하지 않으면 엣지 케이스에서 문제가 발생하기 쉽습니다. 이걸 방지하기 위해서 1 based(배열을 1부터 시작)로 문제를 푸는 것도 좋은 선택입니다.
요약하자면, DP 배열의 정의는 그 자체로 알고리즘의 핵심이며, 명확한 정의가 있어야만 올바른 해결책을 도출할 수 있습니다.
모든 경우를 정확히 한 번만 계산하기
다이나믹 프로그래밍의 핵심 원리는 중복되는 하위 문제의 결과를 저장하여 재활용함으로써 계산 효율성을 극대화하는 것입니다. 이는 '모든 경우를 정확히 한 번만 계산하기'라는 원칙으로 요약할 수 있습니다.
재귀적으로 문제를 해결할 때, 동일한 상태에 대한 계산이 반복되는 경우가 많습니다. 예를 들어, 피보나치수열을 순수 재귀로 구현하면 F(n)을 계산하기 위해 F(n-1)과 F(n-2)를 계산하고, F(n-1)을 계산하기 위해 다시 F(n-2)와 F(n-3)을 계산하는 과정에서 F(n-2)가 중복 계산됩니다. 입력이 커질수록 이러한 중복 계산은 기하급수적으로 증가하여 알고리즘의 효율성을 크게 저하시킵니다.
DP에서는 이미 계산한 결과를 메모리에 저장하고 필요할 때 조회하는 '메모이제이션(Memoization)' 기법을 활용합니다. 이는 Top-down 방식의 DP에서 주로 사용됩니다. 또는 Bottom-up 방식으로 작은 부분 문제부터 차례대로 해결하며 결과를 테이블에 채워나가는 '타뷸레이션(Tabulation)' 방식을 사용할 수도 있습니다.
중요한 점은 모든 가능한 상태에 대해 정확히 한 번씩만 계산이 이루어져야 한다는 것입니다. 불필요한 상태까지 계산하거나, 일부 상태를 계산하지 않고 누락하면 잘못된 결과가 도출될 수 있습니다. 따라서 상태 공간을 정확히 파악하고, 모든 필요한 상태에 대해 빠짐없이 한 번씩 계산하는 것이 중요합니다. DP의 정의를 명확히 한다면 이런 실수를 줄일 수 있습니다.
결론적으로, '모든 경우를 정확히 한 번만 계산하기'는 다이나믹 프로그래밍의 성능과 정확성을 결정짓는 핵심 원칙입니다. 이 원칙을 지키면서 알고리즘을 설계한다면, "분명 맞게 코딩했는데 왜 시간초과가 나오지?" 하는 일은 없을 것입니다.
점화식 도출하기
다이나믹 프로그래밍에서 가장 핵심적인 단계는 점화식을 도출하는 것입니다. 이 방정식은 현재 상태와 이전 상태들 간의 관계를 수학적으로 정의하여 문제를 해결하는 열쇠가 됩니다.
하노이 탑 문제를 예로 들어보겠습니다. 하노이 탑은 세 개의 기둥과 크기가 다른 n개의 원판으로 구성됩니다. 모든 원판을 첫 번째 기둥에서 세 번째 기둥으로 옮기되, 한 번에 하나의 원판만 옮길 수 있고 작은 원판 위에 큰 원판이 올 수 없다는 제약이 있습니다.
이 문제의 상태를 DP[n][from][to]로 정의해 봅시다. 이는 'n개의 원판을 from 기둥에서 to 기둥으로 옮기는 최소 이동 횟수'를 의미합니다(더 쉽게 만들 수도 있지만 설명을 위해 이렇게 정의해 보겠습니다). 여기서 점화식을 도출하기 위해 문제를 더 작은 부분 문제로 분해해야 합니다.
n개의 원판을 from에서 to로 옮기려면, 먼저 n-1개의 원판을 from에서 중간 기둥(mid)으로 옮기고, 가장 큰 원판을 from에서 to로 옮긴 다음, n-1개의 원판을 mid에서 to로 옮겨야 합니다. 따라서 점화식은 다음과 같습니다:
DP[n][from][to] = DP[n-1][from][mid] + 1 + DP[n-1][mid][to]
이 방정식에서 mid는 from도 to도 아닌 나머지 기둥을 나타냅니다. 이러한 점화식은 문제의 구조를 명확하게 보여주며, 이를 통해 DP 테이블을 채워나갈 수 있습니다.
점화식을 도출할 때는 현재 상태를 이전에 계산된 상태들과 어떻게 연결할 수 있는지 생각해야 합니다. 최적 부분 구조(Optimal Substructure)를 찾아내고, 그것을 수학적으로 표현하는 것이 핵심입니다. 이 과정에서 그림을 그리거나 간단한 예제를 풀어보는 것이 도움이 될 수 있습니다.
또한, 점화식이 모든 가능한 경우를 포함하는지 확인하는 것도 중요합니다. 일부 경우가 누락되면 잘못된 결과가 도출될 수 있습니다. 따라서 전이 방정식을 세운 후에는 작은 예제를 통해 검증하는 과정이 필요합니다.
다이나믹 프로그래밍은 복잡한 문제를 효율적으로 해결할 수 있는 강력한 도구이지만, 올바른 접근 방식과 세심한 구현이 필요합니다. 배열의 정의를 명확히 하고, 모든 경우를 정확히 한 번만 계산하며, 올바른 점화식을 도출함으로써 DP 문제를 성공적으로 해결할 수 있습니다. 지금까지 배운 원칙들을 실제 문제 해결에 적용하면서 계속 연습한다면, 코딩테스트에 나오는 다이나믹 프로그래밍은 쉽게 해결할 수 있을 것입니다.