컴퓨터/알고리즘
[DP] Dynamic Programming 동적 프로그래밍
나한나한나한나
2024. 7. 31. 17:41
1. 동적 프로그래밍이란 무엇인가
복잡한 문제를 Breaking them down into simpler subproblems 해서 해결하는 방법
이것은 효율적으로 문제를 풀기 위한 전략
문제는 분할할 수 있어야 하고, each subproblem은 한 번만 해결하고 어딘가에 저장
이것은 최적화 문제에서 유용, 많은 가능한 해결책 중에서 최적의 해결책을 찾고자 할 때 사용
2. DP는 4가지 단계를 거친다.
- 큰 문제를 → 작은 문제로 분할
- 예를 들어, 피보나치 수열에서 n번째 수를 구하는 문제는 (n-1)번째와 (n-2)번째 수를 구하는 작은 문제로 나눌 수 있다.
- 큰 문제의 해 = 작은 문제의 해로 이루어진 점화식
- 피보나치 수열의 경우: F(n) = F(n-1) + F(n-2)
- DP테이블(배열, 리스트) 순서대로 계산
- 점화식을 바탕으로 작은 문제부터 큰 문제까지 순차적으로 해결
- 각 하위 문제의 해결책을 DP 테이블(보통 배열이나 리스트 형태)에 저장
- 예: F(1)=1, F(2)=1로 시작해서 F(3), F(4), ... 순으로 계산하고 저장
- 정확성 증명
- DP 알고리즘이 모든 경우에 대해 정확한 해답을 제공한다는 것을 수학적으로 증명(주로 귀납법)
3. 최대구간합 문제로 알아보는 DP - 4가지 풀이법
- Brute Force = O(n³)
- 가능한 모든 부분 배열 고려
- 3중 반복문 = O(n³)
- 비효율적이지만 직관적
A = [5,-32,1,-6,7,8,-9,34,56,-43]
max = float('-inf') # 최대값을 저장할 변수, 음의 무한대로 초기화
for i in range(len(A)): # 시작 인덱스
for j in range(i, len(A)): # 끝 인덱스 (i부터 시작)
sum = 0
for k in range(i, j+1): # i부터 j까지의 합 계산
sum += A[k]
if max < sum: # 현재까지의 최대값보다 크면 갱신
max = sum
print(max) # 최대 구간합 출력
- Prefix Sum = O(n²)
- 누적 합(Prefix Sum)을 미리 계산하여 저장
- 이중 반복문 = O(n²)
- 각 구간 = O(1)
- 전체 = O(n²)
A = [5,-32,1,-6,7,8,-9,34,56,-43]
n = len(A)
P = [0] * (n + 1) # 누적 합을 저장할 배열
# 누적 합 계산
for i in range(1, n + 1):
P[i] = P[i-1] + A[i-1]
max_sum = float('-inf')
for i in range(n):
for j in range(i, n):
# i부터 j까지의 구간합 계산
current_sum = P[j+1] - P[i]
if current_sum > max_sum:
max_sum = current_sum
print(max_sum)- Divide & Conquer = O(n*log(n))
- 배열을 반으로 나누어 재귀적으로 해결
- 왼쪽 부분, 오른쪽 부분, 중간을 가로지르는 부분 중 최대값 탐색
- O( n * log(n) )
A = [5,-32,1,-6,7,8,-9,34,56,-43]
// pivot m을 정하고,
// L = m보다 작은 범위 중 max값,
// R = m보다 큰 범위 중 max 값,
// M = m과 m+1을 포함한 범위 중 max 값 중 max
max_interval(A,l,r):
if l >= r : return A[l]
m = (l + r) // 2
L = max_interval(A,l,m)
R = max_interval(A,m+1,r)
// L 계산하는 for문~~
// R 계산하는 for문~~
M = max(L,R)
return max(L,R,M)- DP = O(n)
- 각 위치에서 끝나는 최대 부분합을 계산
- 현재 요소를 포함할지 (이전 최대합에 더하기) 또는 새로운 부분배열을 시작할지 결정
- 한 번의 순회 = O(n)
def max_subarray_sum_dp(A):
n = len(A)
max_ending_here = max_so_far = A[0]
for i in range(1, n):
# i번째 요소로 끝나는 최대 부분합 계산
max_ending_here = max(A[i], max_ending_here + A[i])
# 전체 최대값 갱신
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
A = [5,-32,1,-6,7,8,-9,34,56,-43]
print(max_subarray_sum_dp(A))- DP 방법의 도식화
A[i]: [ 5, -32, 1, -6, 7, 8, -9, 34, 56, -43 ]
│ │ │ │ │ │ │ │ │ │
S[i]: [ 5, -27, 1, -5, 7, 15, 6, 40, 96, 53 ]
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
│ │ │ │ │ │ │ │ │ │
max(5,5) │ │ │ │ │ │ │ │ │
max(-27,5-32) │ │ │ │ │ │ │
max(1,-27+1) │ │ │ │ │ │
max(-5,1-6) │ │ │ │ │
max(7,-5+7) │ │ │ │
max(15,7+8) │ │ │
max(6,15-9) │ │
max(40,6+34) │
max(96,40+56)
max(53,96-43)
- S[i]는 A[i]로 끝나는 최대 구간합을 나타냅니다.
- 점화식: S[i] = max(A[i], S[i-1] + A[i])
- A[i]: 새로운 구간을 시작하는 경우
- S[i-1] + A[i]: 이전 구간에 현재 원소를 추가하는 경우
- 초기값: S[0] = A[0]
- 각 단계에서 두 값(A[i]와 S[i-1] + A[i]) 중 큰 값을 선택합니다.
- 최종적으로 S 배열의 최대값이 전체 배열의 최대 구간합이 됩니다.
여기서는 tabulation/bottom-up 방식을 사용했지만, memoization/top-down 방식을 사용할 수도 있다.
문제에 따라 적합한 방식이 다르다. DP에서 만능열쇠는 없다.
더보기
오해하지 말 것
문제에 따라 적합한 방식이 다르다고 했지만,
둘 중 하나의 방식으로'만' 해결할 수 있는 것은 아니다. 풀이가 어렵고 복잡해질 뿐.
어떤 문제에서는 bottom-up이 닭 잡는 칼이지만, 어떤 문제에서는 소 잡는 칼이 될 수도 있다.
이는 문제를 푸는 당사자가 판단해야 할 몫이다.
이 도식에서 볼 수 있듯이, 각 단계에서 이전 단계의 결과를 이용하여 현재의 최대 구간합을 계산합니다. 이렇게 하면 모든 가능한 구간을 효율적으로 고려할 수 있으며, 단 한 번의 배열 순회로 문제를 해결할 수 있습니다.