동적 프로그래밍은 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 중복 계산을 줄이는 알고리즘 기법입니다. DP는 특히 최적화 문제에서 효과적으로 사용되며, 여러 가지 문제에서 복잡한 계산을 효율적으로 수행할 수 있습니다.
DP의 주요 개념
- 최적 부분 구조(Optimal Substructure):
• 문제를 작은 하위 문제로 나누어 해결할 수 있어야 합니다.
• 예를 들어, 피보나치 수열의 경우, F(n) = F(n-1) + F(n-2) 로 정의되므로 큰 문제를 작은 문제로 나누어 계산할 수 있습니다. - 중복되는 하위 문제(Overlapping Subproblems):
• 하위 문제가 여러 번 반복되어 발생하는 경우에 DP가 효과적입니다.
• 예를 들어, 피보나치 수열을 재귀로 계산하면 동일한 하위 문제를 여러 번 계산하게 되므로, 이를 메모이제이션을 통해 중복 계산을 줄일 수 있습니다. - 메모이제이션(Memoization) 또는 탑다운(Top-Down) 방식:
• 하위 문제를 계산할 때, 이미 계산된 결과를 메모리에 저장하여 필요할 때마다 이를 재사용합니다.
• 재귀적인 방식으로 하위 문제를 해결하면서, 계산된 값을 메모리에 기록해 두는 방식입니다. - 타뷸레이션(Tabulation) 또는 바텀업(Bottom-Up) 방식:
• 작은 하위 문제부터 차례대로 계산하여 결과를 저장한 후, 더 큰 문제를 해결해 나가는 방식입니다.
• 배열이나 테이블을 사용해 작은 값부터 계산하여 최종 문제를 해결합니다.
DP 알고리즘의 구현 방식
DP 문제를 해결하는 방식은 크게 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식으로 나눌 수 있습니다.
-
탑다운(Top-Down) 방식 (메모이제이션)
• 재귀 호출을 이용하여 큰 문제를 작은 문제로 쪼개고, 결과를 저장하여 중복 계산을 방지합니다.
• 메모이제이션을 통해 계산된 값을 저장하고 재사용하므로, 시간 복잡도를 줄일 수 있습니다.
예를 들어, 피보나치 수열을 DP로 계산하는 탑다운 방식은 다음과 같습니다:
def fibonacci(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
print(fibonacci(10)) # 10번째 피보나치 수 출력-
바텀업(Bottom-Up) 방식 (타뷸레이션)
• 작은 문제를 먼저 해결한 후, 이를 이용해 점차 큰 문제를 해결해 나갑니다.
• 일반적으로 반복문을 사용하여 계산하며, 테이블(배열)에 결과를 저장해 가면서 문제를 해결합니다.
피보나치 수열을 바텀업 방식으로 해결하는 예시는 다음과 같습니다:
def fibonacci(n):
if n <= 1:
return n
fib = [0] * (n + 1)
fib[1] = 1
for i in range(2, n + 1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
print(fibonacci(10)) # 10번째 피보나치 수 출력DP 알고리즘의 예시 문제
- 피보나치 수열:
• F(n) = F(n-1) + F(n-2)로 정의되는 수열에서, 중복되는 계산을 줄이기 위해 DP를 사용할 수 있습니다. - 최소 비용 경로:
• 2차원 배열에서 좌측 상단에서 우측 하단까지 이동할 때, 이동 경로의 최소 비용을 구하는 문제에서 DP를 사용할 수 있습니다.
• 각 칸의 최소 비용을 이전 칸의 비용을 이용하여 계산해 나갑니다. - 0/1 배낭 문제:
• 무게와 가치가 주어진 물건들을 배낭에 넣을 때, 배낭의 용량을 넘지 않으면서 가치를 최대로 하는 문제입니다.
• DP를 통해 각 물건의 선택 여부를 바탕으로 최대 가치를 구할 수 있습니다. - 최장 증가 부분 수열(LIS):
• 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이를 찾는 문제입니다.
• 각 위치까지의 최장 증가 부분 수열 길이를 저장해가며 문제를 해결할 수 있습니다.
시간 복잡도와 공간 복잡도
DP의 시간 및 공간 복잡도는 문제에 따라 다르지만, 중복 계산을 제거하여 시간 복잡도를 획기적으로 줄이는 장점이 있습니다. 예를 들어:
• 피보나치 수열의 경우 재귀를 사용하면 지수 시간 복잡도 O(2^n)이 되지만, DP를 사용하면 선형 시간 O(n)으로 줄일 수 있습니다.
• 대부분의 DP 문제는 테이블을 사용하는 만큼, 공간 복잡도는 테이블의 크기에 비례합니다.
