- 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능
- 중복되는 부분 문제 (Overlapping SUbproblem)
- 동일한 작은 문제를 반복적으로 해결해야 함
피보나치 수열은 다음과 같은 형태의 수열이며, DP로 효과적으로 계산 가능
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
점화식이란 인접한 항들 사이의 관계식을 의미
피보나치 수열을 점화식으로 표현하면 다음과 같음
피보나치 수열이 계산되는 과정은 다음과 같이 표현 가능하며, 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현
피보나치 수열이 계산되는 과정은 다음과 같이 표현 가능하며, n번째 피보나치 수를 라고 할 때, 4번째 피보나치 수 를 구하는 과정은 다음과 같음
피보나치 수열 : 단순 재귀 소스코드
def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print (fibo(4)) >>> 3
피보나치 수열의 시간복잡도 분석
단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됨
다음과 같이 가 여러 번 호출 되는 것 확인 가능 (중복되는 부분문제)
피보나치 수열의 시간복잡도는 다음과 같음
세타 표기법 :
빅오 표기법 :
빅오 표기법을 기준으로 을 계산하기 위해 약 10억가량의 연산을 수행해야 한다. 그렇다면 을 계산하기 위해 얼마나 많은 연산이 필요할까?
- 피보나치 수열의 효율적인 해법 : DP
- DP의 사용 조건을 만족하는 지 확인한다
- 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있음
- 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결
피보나치 수열은 DP의 사용조건을 만족함
# 한 번 계산된 결과를 Memoization 하기 위한 리스트 초기화 d = [0] * 100 # 0~99까지의 인덱스를 갖게 됨 def fibo(x): # 종료조건 (1 or 2일 때, 1 반환) 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)) >>> 218922995834555169026
# 앞서 계산한 결과를 저장하기 위한 DP 테이블 초기화 d = [0] *100 >>> # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1 d[1] = 1 d[2] = 2 n = 99 # 피보나치 함수 반복문으로 구현(보텀업 DP) for i in range(3, n+1): d[i] =d[i-1] + d[i-2] print(d[n]) >>> 218922995834555169026
d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end = ' '_ 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] fibo(6) >>> f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)
피보나치 수열 : 메모이제이션 동작 분석
이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대 가능
실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문함
분할정복의 대표적인 예시 : 퀵 정렬
한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면, 그 기준 원소의 위치는 바뀌지 않음
분할 이후, 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않음
n= int(input()) # 4 array = list(map(int, input().split())) # [1, 3, 1, 5] # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 100 # DP 진행 (보텀업) d[0] = array[0] # 1 d[1] = max(array[0], array[1]) # max(1, 3) = 3 for i in range(2, n): # 2~3 # 특정한 i 창고를 안털면 [i-1], 특정한 i 창고를 털면 [i-2] d[i] = max(d[i-1], d[i-2] + array[i]) # d[2] = max(d[2-1]), d[2-2] + array[2] -> max(3, 1+1) = 3 # d[3] = max(d[3-1]), d[3-2] + array[3] -> max(3, 3+5) = 8 print(d[n-1]) # d[4-1] = d[3] = 8
x = int(input()) # input = 4 # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 30001 for i in range(2, x+1): #2 ~ 4 d[i] = d[i - 1] + 1 # 현재 수 - 1 # i = 2, d[2] = d[2-1] + 1 = 1 # i = 3, d[3] = d[3-1] + 1 = 1+1= 2 # i = 4, d[4] = d[4-1] + 1 = 2+1= 3 if i % 2 == 0: d[i] = min(d[i], d[i//2] + 1) # i = 1, min(d[2], d[2//2] + 1) =min(1, 1+1) = 1 # i = 4, min(d[4], d[4//2] + 1) =min(3, 2) = 2 if i % 3 == 0: d[i] = min(d[i], d[i//3] + 1) # i = 3, min(d[3], d[3//3]+1) = min(2, 2) = 2 if i % 5 == 0: d[i] = min(d[i], d[i//5] + 1) print(d[x]) >>> 2
n, m = map(int, input().split()) arr = [] for i in range(n): arr.append(int(input())) # 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [10001] * (m + 1) # DP 진행 (보텀업) d[0] = 0 for i in range(n): for j in range(arr[i], m + 1): if d[j - arr[i]] != 10001: # (i-k)원을 만드는 방법이 존재하면 d[j] = min(d[j], d[j - arr[i]] + 1) # 계산된 결과 출력 if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우 print(-1) else: print(d[m])
for tc in range(int(input())): n, m = map(int, input().split()) arr = list(map(int, input().split())) # DP를 위한 2차원 DP 테이블 초기화 dp = [] index = 0 for i in range(n): dp.append(arr[index:index + m]) index += m # DP 진행 for j in range(1, m): for i in range(n): # 왼쪽 위에서 오는 경우 if i == 0: left_up = 0 else: left_up = dp[i - 1][j - 1] # 왼쪽 아래에서 오는 경우 if i == n - 1: left_down = 0 else: left_down = dp[i + 1][j - 1] # 왼쪽에서 오는 경우 left = dp[i][j - 1] dp[i][j] = dp[i][j] + max(left_up, left_down, left) result =0 for i in range(n): result = max(result, dp[i][m - 1]) print(result)
n = int(input()) arr = list(map(int, input().split())) arr.reverse() # 순서를 뒤집어, '최장 증가 부분 수열' 문제로 변환 # DP를 위한 1차원 DP 테이블 초기화 d = [1] * n # 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행 for i in range(1, n): for j in range(0, i): if arr[j] < arr[i]: d[i] = max(d[i], d[j] + 1) # 열외해야 하는 병사의 최소 수를 출력 print(n-max(d))