Dynamic Programming

동적 프로그래밍

동적 프로그래밍(Dynamic Programming)은 큰 문제를 작은 부분 문제로 나누어 푸는 방법론입니다. 이 방법은 각 부분 문제의 해결책을 계산하고 저장하여, 동일한 부분 문제를 반복해서 해결하는 비효율성을 줄이는 것이 목표입니다. 주로 최적화 문제나 최단 경로 문제 등에 적용됩니다.

동적 프로그래밍의 핵심 아이디어는 Memoization(메모이제이션)과 Bottom-up(하향식 접근) 방식입니다.

Memoization(메모이제이션): 이미 계산한 결과를 저장해두고, 나중에 같은 계산을 해야 할 때 다시 계산하지 않고 저장된 값을 활용하는 방식입니다. 이는 재귀적인 방법으로 구현될 때 주로 사용됩니다.

Bottom-up(하향식 접근): 작은 부분 문제부터 시작해서 그 해답을 저장하고, 이를 이용하여 큰 문제의 해답을 구하는 방식입니다. 이는 반복문을 사용하여 구현됩니다.

동적 프로그래밍은 다음과 같은 단계로 진행됩니다:

문제 분할(Divide): 주어진 문제를 작은 부분 문제로 나눕니다. 부분 문제 해결(Conquer): 가장 작은 부분 문제부터 해결합니다. 해결책 결합(Combine): 작은 부분 문제의 해결책을 결합하여 더 큰 부분 문제의 해결책을 만듭니다. 동적 프로그래밍은 많은 알고리즘과 문제 해결에 사용됩니다. 예를 들어, 피보나치 수열, 최장 증가 부분 수열(Longest Increasing Subsequence), 최단 경로 문제 등이 그 예시입니다.