다이나믹 프로그래밍
한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다
피보나치 수열의 점화식은 다음과 같다
재귀함수를 이용해서 코드로 나타낼 수 있다
def fibo(x):
if x == 1 or x ==2 :
return 1
return fibo(x-1)+fibo(x-2)
print(fibo(4))
하지만 위와 같이 작성하면 f(n) 함수에 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 생길 수 있다. 시간복잡도는 O(2ⁿ) 정도로 소요된다.
위의 코드를 다시 생각해보면 동일한 함수가 반복적으로 호출된다. 이미 한번 계산했지만, 계속 호출할 때마다 계산을 다시 한다. fibo(6)을 구하기 위해 f(3)은 3번 계산된다. 그래서 효율적이지 못하다
하지만 아래의 조건이 만족할 때 다이나믹 프로그래밍을 이용한다면 효율적으로 해결할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다
피보나치 수열은 위의 조건을 만족하는 대표적인 문제이며, 메모이제이션 기법을 이용해 풀 수 있다.
메모이제이션
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로 한번 구한 겨로가를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다
탑다운 방식
위에서 아래로 내려가면서 문제를 해결
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))
보텀업 방식
아래에서 위로 올라가면서 문제를 해결
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])
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
보텀업 방식에 사용되는 결과 저장용 리스트를 “DP 테이블”이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로 다이나믹 프로그래밍과는 별도의 개념이다. 계산된 결과를 저장해 놓기만 하고, 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.
다이나믹 프로그래밍 접근 방법
- 문제가 다이나믹 프로그래밍 유형인지 파악
- 문제가 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래걸리면 DP를 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인
- 재귀함수로 프로그램을 작성해본 후, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선해 본다.
- 가능하다면 재귀함수를 보텀업 방식으로 구현한다
- 스택 크기가 한정되어 있을 수 있기 때문
문제 8-2 1로 만들기
문제
정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다.
- x가 5로 나누어 떨어지면 , 5로 나눈다.
- x가 3로 나누어 떨어지면 , 3로 나눈다.
- x가 2로 나누어 떨어지면 , 2로 나눈다.
- x에서 1을 뺀다.
정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 출력하시오
x = int(input())
# d[i]는 숫자 i가 1이 되기 위해 해야되는 연산을 말한다
d = [0]*30001
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])
문제 8-3 개미전사
개미가 식량창고를 약탈하려고 한다. 식량창고가 n개가 있을 때 연속해서 약탈할 수는 없고 최소 한칸 이상 떨어진 식량창고를 약탈해야 한다. 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오
n = int(input())
arr = list(map(int,input().split()))
d = [0]*1000
d[0]=arr[0]
d[1] = arr[1]
for i in range(2,n):
d[i] = max(d[i-1],d[i-2]+arr[i])
print(d[n-1])
- 탑다운 방식으로는 생각이 나는데 보텀업 방식으로 생각하기가 쉽지 않다 ㅠ 조금 더 문제를 많이 풀어봐야겠다 ㅠㅠㅠ
문제 8-4 바닥공사
문제 가로 길이가 n,세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있을 때, 얇은 바닥을 12 덥개, 21 덥개,2*2 덥개를 이용해 채우는 경우의수를 출력하시오, 단 출력할 때 방법의 수를 796796으로 나눈 나머지를 출력한다.
n = int(input())
d = [0]*1001
#가로 길이가 1일때 경우의 수
d[1]=1
#가로 길이가 2일때 경우의 수
d[2]=3
for i in range(3,n+1):
d[i] = (d[i-1]+2*d[i-2])%796796
print(d[n])
- 아직 나에겐 점화식 세우는게 가장 어려운 것 같다.
- 2*n개의 바닥이 가로 n-1까지 다 덮여 있다고 가정하면
- 남은 2*(n-1) 바닥을 채우는 방법은 2*1 덮개 하나를 덮으면 되니까, 1가지이다.
- 2*n개의 바닥이 가로 n-2까지 다 덮여 있다고 가정하면
- 남은 2*(n-2) 바닥을 채우는 방법은 22 덮개를 하나 덮는 방법 1가지, 12덮개 2개를 덮는 방법 1가지, 총 2가지이다.
- 사용할 수 있는 덮개의 형태가 최대 2*2의 직사각형이기 때문에 더 이상의 경우의 수는 생각해 보지 않아도 된다.
따라서 점화식은 다음과 같다.
문제 8-5 효율적인 화폐 구성
N가지 종류의 화폐가 있는데 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다르면 같은 경우로 구분한다.
n,m = map(int,input().split())
arr = []
d=[100000]*(m+1)
d[0]=0
for i in range(n):
arr.append(int(input()))
for i in range(1,m+1):
countList = []
for k in arr :
if (i-k)>= 0:
countList.append(d[i-k])
if len(countList) != 0 :
d[i] = min(countList) + 1
else :
d[i] +=1
if d[m] >= 100000:
print("-1")
else:
print(d[m])
알고리즘 - 이것이 코딩테스트다