- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 시키는 방법
- 이미 계산된 작은 문제에 대한 결과는 별도 메모리 영역에 저장해 다시 계산하지 않는다.
- 보통 선형 탐색문제를 이렇게 해결하면 비약적으로 시간 효율을 향상 시킬 수 있다.
- 구현은 보통 탑다운, 바텀업으로 구성된다.
자료구조에서 Dynamic Allocation은 프로그램이 실행되는 도중 실행에 필요한 메모리를 할당하는 기법을 의미다이나믹 프로그래밍에서는 별다른 의미 없이 사용된 단어- 아래 조건을 만족할 때 사용가능
- Optimal Substructure(최적 부분 구조)
- 큰 문제를 작은문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제 해결할 수 있다.
- Overlapping Subproblem(중복되는 부분 문제)
- 동일한 작은 문제를 반복적으로 해결해야 한다.
- Optimal Substructure(최적 부분 구조)
피보나치 수열
- 점화식이란 인접한 항들 사이의 관계식을 의미한다.
- 피보나치 수열은 점화식으로 표현할 수 있다.
- 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.
- 수열은 리스트나 배열을 통해 표현하여 연산을 기록한다.
- 이러한 리스트나 배열을 테이블이라고 부르기도한다.
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))- 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다.
-
중복되는 부분 문제가 존재하기 때문이다.
-
O(2^N)
-
피보나치는 다이나믹 프로그래밍의 사용 조건을 만족한다.
- 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다.
- 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결한다.
Memoization
- 한번 계산한 결과를 메모리 공간에 메모하는 기법
- Caching이라고도 한다.
- 같은 문제 다시 호출 시 메모했던 결과를 바로 호출
Top-Down vs Bottom-UP
- Top-Down(memoization) 방식은 하향식
- 구현 과정 중 재귀함수를 이용한다.
- Bottom-UP 방식은 상향식
- 작은 문제를 해결해 나가면서 그 다음의 문제를 해결해 나간다.
- 전형적인 형태이다.
- 결과 저장용 리스트는 DP Table 이라고 부른다.
- 메모이 제이션은 이전 계산된 결과를 일시적으로 기록해 놓은 넓은 개념을 의미한다.
- 다이나믹 프로그래밍에 국한된 개념 X
- 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍 시 활용하지 않을 수 있다. 메미오제이션과 다이나믹 프로그래밍은 다른 개념인 것이다.
d = [0] * 100
def fibo(x):
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
print(fibo(99))- 이미 계산된 결과를 메모리에 저장하면, 아래에서 처럼 색칠된 노드만 처리할 것을 기대할 수 있다.
- 메모이제이션 사용시 시간 복잡도 O(N)
- 지수 시간 복잡도 -> 선형 복잡도
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])다이나믹 프로그래밍 VS 분할 정복
- 모두 최적 부분 구조를 가질 때 사용할 수 있다.
- 차이점은 부분 문제의 중복
- 다이나믹 프로그래밍에서는 각 부분 문제들이 서로 영향을 미치며 문제가 중보된다.
- 퀵 정렬의 경우 생각해보면 피벗이 변경해서 자리를 잡으면 기준 원소의 위치는 더이상 바뀌지 않음 -> 한번이 분할이 이뤄지면 다른 곳에 미치는 영향 없음 (부분문제 중복 X)
- 다이나믹 프로그래밍 유형인지 파악하는 것이 중요
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해본다.
- 일단 탑다운에서 코드를 개선하는 방법 사용 가능
효율적인 화폐 구성
# n : 화폐 종류 개수, m : 최종으로 만들어야되는 화폐
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(int(input())
d = [1001] * (m + 1)
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j - array[i]] != 10001:
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])- i 번째를 만들기에 필요한 각 화폐 단위마다의 화폐 개수를 바텀업으로 구하면서 최종 m에 필요한 동전 최소 개수를 구한다.
금광
- 금광의 모든 위치에 대해 세가지만 고려하면 된다.
- 왼쪽 위에서 오는 경우
- 왼쪽 아래에서 오는 경우
- 왼쪽에서 오는 경우
- array[i][j] : 금의 양
- dp[i][j] : 해당 요소까지의 최적해 (얻을 수 있는 금의 최댓값)
n, m = map(int, input().split())
array = list(map(int, input().split()))
dp = []
index = 0
for i in range(n):
dp.append(array[index: index + m])
index += m
for j in range(1, m):
for i in range(n):병사 배치하기
- LIS (Long Increasing Subsequence) 가장 긴 증가하는 부분 수열 알고리즘을 이용
- D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
- 점화식 : 모든 앞쪽에있는 원소 j, 0 <= j < i에 대해 D[i] = max(D[i], D[j] + 1) if array[j] < array[i]
- O(N^2)
...
array.revers() # 순서를 뒤집어 최장 증가 부분 수열 문제로 변환 LIS
dp = [1] * n # 각 원소를 마지막으로 갖는 배열은 하나씩 있으므로 1로 초기화
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))
OnePunchLotto