➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.
✔ 다이나믹 프로그래밍이란?
메모리를 적절히 사용하여 수행시간의 효율성을 비약적으로 향상시키는 방법이다. 즉, 한번 해결한 문제는 다시 해결하지 않도록하여 시간복잡도를 줄인다. 이는 동적(Dynamic) 계획법이라고도 불린다. ( != 자료구조에서의 '동적(Dynamic)' : 프로그램이 실행되는 도중)
아래의 두가지 조건을 만족할때 사용한다.
1. 최적 부분 구조(Optimal Substructure) : 큰 문제를 작은 문제로 잘게 쪼갠다.
2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결한다.
◾ 메모이제이션(Memoization)
한 번 계산한 결과값을 메모리공간에 메모해 두는 것이다. 같은 문제를 다시 호출하면 저장되어있던 메모를 불러온다. ( = 캐싱 Caching)
◾ 탑다운( = 메모이제이션, 하향식)
큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출한다.
◾ 보텀업( = 상향식)
◾ 피보나치 수열 예제
-
피보나치 수열
점화식은 재귀함수를 사용해 구현할 수 있다.
피보나치 수열을 트리형태로 표현하면 다음과 같다.
# 점화식을 재귀함수로 구현 def fibo(x): ir x == 1 or x ==2 : return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) -
시간복잡도
피보나치 수열은 O(2^N)인 지수시간 복잡도륵 가지게 된다. 하지만 이는 같은 함수가 여러번 호출되기에 비효율적이다. (중복되는 부분 문제)
-
결론
따라서 피보나치 수열은 트리형태로 문제를 쪼갤 수 있고 동일한 계산이 반복되기에 다이나믹 프로그래밍의 사용조건을 만족한다!
👉 문제해결과정
[탑다운방식]# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 # 100개의 원소를 가지는 리스트 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))[보텀업 방식]
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 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])
색칠된 부분만 계산을 하고 나머지 점선부분은 메모이제이션을 이용하기에 계산 횟수가 줄어든다!👉 시간복잡도
따라서 시간복잡도는 O(N)으로 줄어든다.
✔ 문제1 : 개미 전사
마을에 정해진 수의 식량을 저장하는 식량창고가 있다. 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미전사가 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야한다. (창고 인덱스는 0부터 시작한다)
만약 식량창고가 {1, 3, 1, 5}로 존재하면 개미전사는 최대한 많은 양의 식량은 얻기위해서는 창고1, 창고3을 선택하여야 한다. 따라서 식량창고 N개가 주어졌을때 최댓값을 출력하여라.
👉 문제해결과정
각 식량창고를 선택했을때 가지는 최댓값을 구한다.
if 식량창고 = {1, 3, 1, 5}
만약, 창고3을 선택할경우에는 창고1을 선택했을때 얻는 최댓값과 창고2을 선택했을때 얻는 최댓값을 비교하여 창고3을 털지 안털지 결정한다.
# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화(메모이제이션)
d = [0] * 100
# 보텀업
d[0] = array[0]
# max 둘중에 더 큰 값을 반환
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + array[i])
print(d[n - 1])✔ 문제2 : 1로 만들기
정수X가 주어졌을때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
1. X가 5로 나누어 떨어지면, 5로 나눈다.
2. X가 3으로 나누어 떨어지면, 3으로 나눈다.
3. X가 2로 나누어 떨어지면, 2로 나눈다.
4. X에서 1을 뺀다
연산을 사용하는 횟수의 최솟값을 구하려라.
👉 문제해결과정
트리를 그려 각 단계별 4가지의 트리노드를 그린다. 그 중 최소높이를 가지는 트리를 구한다.
if X = 6 일때, 각 연산별 트리이다.( 6은 5로 나누어떨어지지않으니 생략 )
# 정수 X를 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화(메모이제이션)
d = [0] * 30001
# 보텀업
# 4개의 연산 결과 중 가장 작은값은 d[i]에 넣음
for i in range(2, x + 1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])✔ 문제3 : 효율적인 화폐 구성
N가지 종류의 화폐가 있다. 최소한의 화폐 개수를 이용하여 M원을 만들어라.
👉 문제해결과정
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화(메모이제이션)
# 10001 -> INF(무한) : 특정 금액을 만들 수 있는 화폐 구성이 불가능함(문제에서 1 =< M =< 10000)
d = [10001] * (m + 1)
# 보텀업
d[0] = 0
# arraypi] : 화폐단위
# j : 금액
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])--------- 아래 문제들은 더 공부를 한다음에 다시 강의를 들어봐야겠다😂 ---------
✔ 문제4 : 금광
n x m 크기의 금광이 있다. 맨 처음에는 첫번째 열의 어느 행에서든지 출발할 수 있고, 이후에는 m-1에 걸쳐서 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다. 채굴할 수 있는 금의 최댓값을 구하여라.
👉 문제해결과정
빨간색 동그라미의 칸까지의 최댓값을 구하기 위해서는 빨간색 동그라미 칸과, 빨간색 동그라미로 갈 수 있는 3가지 칸중 가장 많은 값을 가지고 있는 칸을 더한다.
따라서 배열에서 각 위치마다의 최댓값을 계산해 값을 갱신할 수 있다.
최종적으로 맨 오른쪽 열에 값중에 가장 큰 값이 문제에서 요구하는 답이 된다.
✔ 문제5 : 병사 배치하기
🌱 결론
먼저 다른 방법들로 풀어보고 그래도 풀리지 않는다거나, 수행시간을 초과할 경우 다이나믹 프로그래밍의 2가지 조건에 만족하는지 판단한다.
재귀식을 만드는 것이 어렵다. 실제 코테에서도 시간이 오래걸리는 작업이기에 꾸준히 고민해보고 생각해보아야한다.
