🧐 동적 프로그래밍(계획법)이란?
복잡한 문제를 간단한 여러 개의 하위 문제로 나눠서 해결하는 알고리즘을 말한다.
최적 부분 구조(Optimal structure)와 부분 문제 반복(Overlapping subproblems)을 만족하는 문제에서 동적 프로그래밍을 사용하면 효율적으로 문제를 해결할 수 있다.
분할 정복과는 중복되는 문제들을 계속해서 다시 푸는 것이 아니라 처음 문제를 해결하면 그것을 기억해놓은 후, 다시 사용한다는 점에서 차이가 있다.
실제로 재귀를 이용한 알고리즘을 짜다 보면 같은 하위 문제를 반복적으로 풀게 하지만, 동적 프로그래밍을 이용하면 훨씬 효율적으로 문제를 해결할 수 있다.
동적 프로그래밍의 방식으로는 Bottom-up과 Top-down 방식이 있다.
Top-down
주로 재귀를 이용한 방법이고 위에서부터 아래로 내려가는 방식.
재귀를 이용한 대표적인 문제인 피보나치 수열을 해당 방식으로 구현해보면 아래와 같다.
def fibo(n):
global arr
if arr[n]!=0
return arr[n]
if n<3:
arr[n]=1
return arr[n]
else:
arr[n]=arr[n-1]+arr[n-2]
return arr[n]
arr=[0 for _ in range(int(input()))]이렇게 Top-down 방식에서 하위 문제의 값을 기억하는 방법을 memoization이라고 한다.
Bottom-up
주로 반복문을 이용한 방식으로 하위문제부터 차근차근 풀어나간다.
마찬가지로 피보나치 수열을 해당 방식으로 구현해보면 아래와 같다.
def fibo(n):
arr=[0,1,1]
for i in range(3,n+1):
arr.append(arr[i-1]+arr[i-2])
return arr이렇게 Bottom-up 방식으로 하위 문제의 값을 리스트에 기록하는 방법을 Tabulation이라고 한다.
공간 최적화
def fibo(n):
if n<3:
return 1
num1, num2=1, 1
for i in range(3,n+1):
num2, num1=num2+num1,num2
return num2위와 같은 방식을 사용하면 하위 문제의 답을 기억하는 공간을 최적화 할 수 있다.
예제
백준 1003
피보나치 수열을 구현하는 과정에서 0번째와 1번째의 값이 얼만큼 호출되는지를 구하는 문제이다.
def fibonacci_num(n):
global arr
if arr[n]==[0,0]:
if n==1:
arr[n]=[0,1]
return arr
elif n==0:
arr[n]=[1,0]
return arr
else:
arr[n]=[fibonacci_num(n-1)[n-1][0]+fibonacci_num(n-2)[n-2][0], fibonacci_num(n-1)[n-1][1]+fibonacci_num(n-2)[n-2][1]]
return arr
else:
return arr
import sys
for i in range(int(input())):
arr=[[0,0] for _ in range(int(sys.stdin.readline())+1)]
n=len(arr)-1
print(fibonacci_num(n)[n][0], fibonacci_num(n)[n][1])그냥 피보나치 수열을 구하는 것과 다른 점은 0번째가 호출되는 경우와 1번째가 호출되는 경우를 따로 세어주어야 한다는 점이다.
그래서 여기서는 2차원 배열을 이용해 각각 다른 값을 받을 수 있게 하였다.
이 문제에는 시간 제한이 다른 문제보다 짧게 걸려있기 때문에 동적 프로그래밍 방법을 사용하지 않고 그냥 재귀로 문제를 풀면 시간초과로 실패하게 된다.
백준 9184
문제로 주어진 재귀 알고리즘을 동적 프로그래밍을 이용한 알고리즘으로 바꾸는 문제이다.
def w(a,b,c):
global arr
if a<=0 or b<=0 or c<=0:
a,b,c=0,0,0
elif a>20 or b>20 or c>20:
a,b,c,=20,20,20
#이 윗부분은 불필요한 것 같다. 그냥 해당 조건을 만족하면 array에 값을 넣지 않고 숫자를 return 하면 된다.
if arr[a][b][c]!='0':
return arr[a][b][c]
else:
if a<=0 or b<=0 or c<=0:
arr[a][b][c]=1
return arr[a][b][c]
elif a>20 or b>20 or c>20:
return arr[20][20][20]
elif a<b<c:
arr[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
return arr[a][b][c]
else:
arr[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
return arr[a][b][c]
import sys
while True:
arr=[[['0' for _ in range(21)] for _ in range(21)] for _ in range(21)]
a,b,c=map(int,sys.stdin.readline().split())
if a==-1 and b==-1 and c==-1:
break
else:
print(f'w({a}, {b}, {c}) = {w(a,b,c)}')이 문제같은 경우에는 변수가 3개가 있어 3차원 배열을 사용하였다.
처음 3차원 배열을 사용하다보니 맨 처음 array를 설정할 때 조금 헷갈렸다.
백준 1904
가능한 이진법 표기 경우의 수를 구하는 문제이다.
이 문제를 풀면서 재귀는 상당히 비효율적인 방법이라는 걸 깨달았다.
구현하는 방법은 그냥 피보나치 수열을 구현하는 것과 동일하다.
하지만 재귀를 이용한 Top-bottom 방식을 사용하면 문제에서 제시한 수의 범위가 상당히 넓기 때문에 메모리 초과가 난다.
이 문제에서는 아래 코드와 같이 Bottom-up 방식을 사용해야만 메모리 초과가 되지 않는 것 같다.
import sys
sys.setrecursionlimit(10**6)
def binary(n):
a=n-1
global arr
if arr[a]!=0:
return arr[a]
else:
if n==1:
arr[a]=1
return arr[a]
elif n==2:
arr[a]=2
return arr[a]
else:
arr[a]=(binary(n-2)+binary(n-1))%15746
return arr[a]
n=int(input())
arr=[0 for _ in range(n)]
print(binary(n))메모리 초과난 Top-bottom 방식
n=int(input())
arr=[0]*1000001
arr[1],arr[2]=1,2
for i in range(3,n+1):
arr[i]=(arr[i-1]+arr[i-2])%15746
print(arr[n])Bottom-up 방식
한 가지 의문점은 arr을 만드는 과정에서 아래와 같이 만드니 index error가 떴다는 점이다.
n=int(input())
arr=[0 for _ in range(n+1)]이게 더 효율적으로 보이는데 왜 index error가 뜨는지 모르겠다.
아시는 분은 댓글 달아주시면 감사하겠습니다. ^.^
