Namu | 나무 개발자 블로그입니다
[알고리즘] Dynamic programming by namu
[목차]
들어가며
안경잡이개발자님의 이것이 취업을 위한 코딩테스트이다 with python 유튭 강의에서 참조했다.
Dynamic programming
일반적으로 다이나믹dynamic 이라는 용어는 런타임 중 임시 데이터를 힙heap 영역에 동적으로 할당하는 것을 의미하지만, 알고리즘에서는 실제 런타임은 아니지만 이미 계산된 값을 별도의 메모리에 캐싱한다는 점에서 관용적?으로 사용된다.
코딩테스트에서 이 알고리즘이 필요한지 바로 캐치하거나 점화식을 생각해내기 어려운 경우가 많으므로
그리디, 완전탐색 등을 빠르게 적용해 보고 문제해결이 되지 않을 때(냄새가 날때) 적용해 본다.
활용근거는 다음과 같다.
- 최적 부분 구조(Optimal Substructure) 인가?
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결
- 대표적으로 피보나치 수열이 있다(Ni-2 + Ni-1 = Ni)
- 중복되는 부분 문제(Overlapping Subproblem) 인가?
- 동일한 작은 문제를 반복적으로 해결
이것을 구현하는 방식에는 다음 두 가지가 있다.
- 탑다운(Top down)
- 큰 문제에서 작은 문제 순으로 재귀적 호출
- 직관적이고 빠르게 구현 가능하나, stack 메모리를 사용하기에 성능이 상대적으로 느리다
- 피보나치 기하급수 O(2^n)
- 보텀업(Bottom up)
- 작은 문제에서 큰 문제로 반복 수행
- 구현을 생각해내기 까다롭지만 상대적으로 성능이 낫다
- 피보나치 선형 O(N)
피보나치 구현
Fibonacci 는 기하급수적으로 상승하는 O(2^n) 의 대표적인 다이나믹 프로그래밍 예제이다. -> 황금비
| f(1) | f(2) | f(3) | f(4) | f(5) | f(6) | f(7) | f(8) |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
[탑다운]단순 재귀적 구현: 다이나믹의 특징인 최적 부분 구조에 착안해 탑다운으로 단순 재귀 호출을 한다
# simple recursive
def f(n):
if n <= 1:
return n
return f(n - 1) + f(n - 2)
print(f(4)) # 3
print(f(6)) # 8
print(f(8)) # 21
8번째까지의 결과 예상값을 보면 알겠지만, 피보나치에서 모든 순서의 값은 그것의 전과 전전 순서에 대한 연산이 필요하게 된다. 이를 단순 재귀적으로 구현해버리면 최초 입력 값 n 이 증가하는 만큼 동일한 반복연산 횟수도 기하급수적으로 많아진다.
예를 들어 f(6) 을 단순 재귀적으로 호출한다면 동일한 f(4) 연산이 2회, 동일한 f(3) 연산이 3회, 동일한 f(2) 연산이 5회 반복된다.
[탑다운]메모이제이션Memoization: 위와 같이 동일하게 반복되는 중복연산의 결과값을 메모리에 캐싱Caching 해두는 방법이다
# memoization recursive
caching_list = [0] * 100 # max 100
def memoi_f(n):
if n <= 1:
return n
if caching_list[n] != 0:
return caching_list[n] # return caching data
caching_list[n] = memoi_f(n - 1) + memoi_f(n - 2) # caching
return caching_list[n]
결과값 자체는 단순 재귀와 동일하게 기하급수적으로 증가하지만, 메모리 캐싱으로 인해 스택 연산횟수 자체는 딱 n 회이다. -> O(N)
[보텀업]반복문으로 구현: 주어진 수 n만큼 아래에서부터 반복적으로 상승시킨다
# loop, using memoization
caching_list = [0] * 100 # max 100
def loop_caching_f(n):
if n <= 1:
return n
caching_list[0], caching_list[1] = 0, 1
for i in range(2, n + 1): # 2 to n
caching_list[i] = caching_list[i - 1] + caching_list[i - 2]
return caching_list[n]
# loop, using init variable
def loop_init_f(n):
if n <= 1:
return n
result = 0
v1, v2 = 0, 1
for i in range(2, n + 1): # 2 to n
result = v1 + v2
v1 = v2
v2 = result
return result
첫 번째 loop_caching_f() 함수는 메모이제이션에서 재귀호출을 반복문으로 변형한 형태이다. 재귀함수가 반복되면 매번 stack 메모리 영역에 누적되므로, 캐싱 리스트가 있는 경우 그것을 단순 반복하는 것이 성능상 더 효율적이다.
두 번째 loop_init_f() 함수는 loop_caching_f() 함수에서 메모이제이션을 뺀 반복문이다. 여기에서는 원하는 조건에 맞게 초기값만 잘 지정해주면 된다. 정말 보텀업 방식으로 n 크기만큼 단순 반복만 수행하면서도, 캐싱 리스트를 저장하기 위한 메모리 공간조차 불필요하기 때문에 때문에 가장 최적의 DP 구현 코드라고 할 수 있다.
분할 정복
앞서 다이나믹 프로그래밍은 ‘최적부분구조’와 ‘중복되는 부분’ 의 특성이 있다는 것을 살펴보았다.
분할 정복 알고리즘은 DP 와 같이 최적부분구조(작은 문제들로 구성된 큰 문제)의 특성을 가지지만, 중복 부분이 존재하지는 않는다. 한번 분할된 어느 한 부분은 중복해서 사용되는 일이 없기 때문에 메모이제이션과 같은 기법을 활용할 수 없다는 점을 기억해야 한다. 이 알고리즘의 대표적인 예가 퀵정렬이다.
퀵정렬: 기준 원소(pivot)에 대해 분할된 각 부분에 대해 같은 분할작업을 반복 수행한다. 같은 원소에 대한 분할은 중복수행하지 않으면서 작은 분할이 큰 분할을 구성하는 최적부분구조라 할 수 있다.
# quick sort using Divide and Conquer
def partition(num_list, init, end):
pivot = num_list[(init + end) // 2]
while init <= end:
while num_list[init] < pivot:
init += 1
while num_list[end] > pivot:
end -= 1
if init <= end:
num_list[init], num_list[end] = num_list[end], num_list[init]
init, end = init + 1, end - 1
return init
def quick_sort(num_list, init, end):
if end <= init:
return
mid = partition(num_list, init, end) # divide
quick_sort(num_list, init, mid - 1)
quick_sort(num_list, mid, end)
def main(num_list):
quick_sort(num_list, 0, len(num_list) - 1)
print(num_list)
nums = [9, 3, 10, 7, 8, 2, 5, 1, 6, 4]
main(nums)
퀵정렬은 대부분의 프로그래밍 언어의 sort() 함수에서 활용하는 기법이다. 이상적인 pivot 값이 선택되었을 때 가장 효율적이고 처리속도가 빠르기 때문이다( -> O(NlogN) ). 하지만 사례 원소 수가 적어 pivot 선택이 한쪽으로 치우치게 되면 효율성이 급격히 떨어질 수도 있다( -> O(N^2) ). 그래서 보통 퀵정렬과 함께 병합 정렬과 같은 알고리즘을 함께 활용하도록 구현된다.
예제 풀이
다이나믹 프로그래밍 알고리즘을 활용한 다음의 예제들을 살펴보자.
개미 전사: 개미 전사가 일직선으로 이어진 창고들을 털때, 서로 인접하지 않은(최소 한칸 이상 떨어진) 창고들을 공략하면서 확보할 수 있는 가장 많은 양의 식량 구하기. N 번째 창고까지 턴다고 가정한다.
풀이 아이디어는 주어진 N 보다 작은 i 번째 창고까지의 최대 식량 개수를 중복 활용하는 것이다.
i 일때 i - 3 번째 창고는 무조건 털 수 있으므로 i - 2 번째와 i - 1 번째 중 더 큰값을 구하면 된다.
i - 2 일때는 i 번째 값을 포함하고, i - 1 일때는 인접하므로 포함하지 않는다.
house_list = [1, 3, 1, 5, 6, 5, 8, 2, 3, 1, 9]
def solution(houses, N):
d = [0] * (N + 1) # max count until 'i'
d[0] = 0
d[1] = houses[0]
d[2] = max(houses[1], houses[2])
for i in range(3, N + 1):
d[i] = max(d[i - 1], d[i - 2] + houses[i - 1])
return d[N]
- 주어진 창고의 연속 리스트 houses 를 차례로 하나씩 탐색하며 가장 큰 값(max)을 구한다
- 중복 부분의 특성에 따라 각 인덱스의 최대값을 메모이제이션하기 위하여, 주어진 N 크기의 최대값 리스트 d 를 정의한다
- 인덱스를 0이 아닌 1부터 시작하기 위하여 d 의 0번 인덱스 값은 0으로 초기화 한다
- 0번 인덱스 초기값을 제외하고 구해야 하기 때문에 N + 1 만큼 최적부분구조로 반복한다
1로 만들기: 주어진 정수 X 에 대해서 5, 3, 2 중 하나로 나누어 떨어지면 그것으로 나누는 연산과 1 을 빼는 연산을 활용하여 값을 1로 만들 때, 연산을 사용하는 횟수의 최소값 구하기
def make_one_solution(X):
d = [0] * (X + 1) # d[0] and d[1] is 0
for i in range(2, X + 1): # 상향식 역추적
d[i] = d[i - 1] + 1 # 1 빼는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1) # 2 로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1) # 3 로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1) # 5 로 나누어 떨어지는 경우
return d[X]
이 문제는 그리디로 보일 수 있으나, ‘순서에 관계 없이’ 그리고 ‘최소연산횟수’ 의 조건으로 인해 단순히 탐욕적으로 따라가는 방식(단순 탑다운)으로는 결과값을 알수 없게 되었다. 주어진 수 X 에 대하여 1부터 뺄지 5로 나눌지 바로 알 수는 없기 때문이다.
이 문제는 메모이제이션을 활용한 다이나믹 프로그래밍을 활용해 보텀업 방식으로 풀 수 있다. 주어지는 수가 0 일 때, 1 일 때, 2 일 때, … 순으로 역추적하여 각각의 최소연산횟수를 캐싱하는 것이다.
X = 0 일 때 결과값 0, X = 1 일 때 결과값 0 으로 초기화하고(문제의 조건 중 해결 방법이 없음), 보텀업 방식으로 풀면 특정 인덱스 i 에 대하여 i - 1 의 값을 사전에 알기 때문에 이전 인덱스의 결과값으로부터 최소 횟수인 1 만을 증가시킬 수 있는 다음 연산조건이 어떤 것인지 파악 가능하다.
위 코드의 반복문 안에서는 보텀업 방식이기 때문에 각 인덱스를 추적할 때마다 최소횟수인 1 을 더했다.
효율적인 화폐 구성: N 가지 종류의 화폐를 자유롭게 이용하여 M 원이 되도록 구성할 수 있는 가장 최소한의 화폐 개수 구하기 단, 주어진 화폐 종류로 구할 수 없다면 -1 을 반환한다.
def money_solution(N, M, money_list):
# 각 인덱스를 들어올 수 없는 큰 수인 10001 로 초기화(최소값 구하기)
d = [10001] * (M + 1)
# 0 원은 당연히 0 개
# 1 원은 1원짜리가 들어올 수도 있음
d[0] = 0
for i in range(1, M + 1):
for money in money_list:
if i - money >= 0: # 유효한 금액(index)인지 확인
# money 액수만큼의 이전항 + 1 과 현재의 i 인덱스 값 중
# 더 작은 값이 최소 화폐 개수이다
# 이 작업은 money 종류만큼 반복한다
d[i] = min(d[i], d[i - money] + 1)
return d[M] != 10001 and d[M] or -1
보텀업 방식의 다이나믹 프로그래밍이다. 각 금액의 최소값을 캐싱하는 메모이제이션도 사용되었다.
아이디어는 최소값을 캐싱하는 리스트 d 에서 M 원의 중복 부분인 i 원 기준으로 반복하며 각 화폐 단위인 money 만큼 이전의 인덱스로부터 화폐 개수 1 씩을 증가시킬 때 그 횟수가 최소값인 경우의 횟수만 d 에 저장하는 것이다.
보텀업 방식으로 money 만큼 이전 항의 최소개수를 이미 알기 때문에 다음 항도 알 수 있게 된다.
금광 문제: n x m 크기 금광의 첫 번째 열에서부터 금을 캐기 시작해 m 번에 걸쳐서 오른쪽 위, 오른쪽, 오른쪽 아래의 세 가지 중 하나의 위치로 이동하며 채굴한 최대값을 구하기
def mining_solution(n, m, mine):
dd = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
dd[i][j] = j == 0 and mine[i][j] or -1
for j in range(1, m):
for i in range(n):
if i - 1 >= 0:
left_up = dd[i - 1][j - 1]
else:
left_up = 0
if i + 1 <= n - 1:
left_down = dd[i + 1][j - 1]
else:
left_down = 0
left = dd[i][j - 1]
dd[i][j] = mine[i][j] + max(left_up, left, left_down)
print(f'after dd : {dd}') # 인덱스별 채굴 결과의 누적 리스트 확인
result = 0
for row in dd:
max_value = max(row)
result = max_value > result and max_value or result
return result
직접 찾아가기는 힘들다. 컴퓨터의 힘을 빌려야 한다.
아이디어는 보텀업 방식으로 j - 1 번 열의 left_up, left, left_down 중 max 를 활용하는 것이다.
초기값은 주어진 mine 리스트의 j = 0 번 값들을 그대로 넣어주고, 점화식은 다음과 같이 작성한다.
dd[i][j] = mine[i][j] + max(left_up, left, left_down)
완성된 누적 dd 리스트에서 마지막 j 열의 최대값을 반환하면 된다.
실전 풀이
프로그래머스 고득점 kit 에 출제된 문제들이다.
N으로 표현: 주어진 수 N 과 사칙연산을 활용해서 number 를 표현할 수 있는 방법 중 N 사용횟수의 최소값 구하기
N = 5, number = 12 로 주어졌을 때,
12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5
로 5 를 사용한 횟수는 각각 6, 5, 4 이고, 이중 가장 작은 경우는 4 이다(5 를 4 번 사용한 경우)
제한사항은 다음과 같다
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
| N | number | return |
|---|---|---|
| 5 | 12 | 4 |
| 2 | 11 | 3 |
def solution(N, number):
answer = 0
return answer
N 사용횟수의 최소값은 8 보다 클수 없는 제한조건에 착안하여 N 의 개수 1 에서부터 N 의 개수 8 까지의 각각 조합 가능한 number 의 목록을 캐싱하여 반환한다.
Written on September 14th, 2020 by namu