이것이 코딩 테스트다 PART2 with python : 다이나믹 프로그래밍

이것이 코딩 테스트다 PART2 with python : 다이나믹 프로그래밍

• 다이나믹 프로그래밍(Dynamic programming)
  : 중복되는 연산을 줄여 연산속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘

# 피보나치 수열

def fibo(x):
	if x==1 or x ==2:
    	return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4))

n이 커지면 커질수록 수행시간이 기하급수적으로 늘어난다.
시간 복잡도 : O(2^N)

따라서 문제를 효율적으로 해결 할 수 없는데 이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결 할 수 있다.

다이나믹 프로그래밍을 사용하기 위한 조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 퐇마하는 큰 문제에서도 동일하다.

• 메모이제이션(memoization): 다이나믹 프로그래밍 구현 방법 중 한 종류로, 한 법 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

따라서 리스트, 딕셔너리 등에 구한 정보를 저장하고 가져오면 된다!

# 피보나치 수열 (다이나믹 프로그래밍)
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))

시간 복잡도 : O(N)

탑다운(top-down) : 큰 문제를 해결하기 위해 작은문제를 호출하는 방식
ㄴ 다이나믹 프로그래밍
보텀업(bottom-up): 작은문제무터 차근차근 답을 도출하는 방식
ㄴ 단순 반복문

# 피보나치 수열 (bottom-up방식)
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))

실전문제

1로 만들기

정수 x가 주어질 때 정수 x에 대해 사용할 수 있는 연산
1. x%5 == 0 , x/5
2. x%3 == 0 , x/3
3. x%2 == 0 , x/2
4. x - 1

연산 4개를 적절히 사용해 1을 만든다. 연산을 사용하는 횟수의 최소값을 출력하라.
1<= x <= 30,000

# 1로 만들기
x = int(input())

# d[i]: i가 만들어지기 위해 연산을 호출한 횟수
d = [0] * 30001

for i in range(2, x+1):
	# 빼기 연산은 모든 경우에 가능함. 연산 횟수 1증가
	d[i] = d[i-1] + 1  
    # 2로 나누어 떨어지는 경우
    if i % 2 == 0:
    	# min: 연산 횟수 최소화
    	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)
    
    # % 2 == 0
    # d[6] = min(d[6] , d[3] +1 )
    # 여기서 d[6] = d[3] '+1'은 나누기(/2) 연산으로 연산횟수 1증가.
    
print(d[x])

개미전사

최소한 한 칸 이상 떨어진 식량창고를 약탈하여 최대한 많은 식량을 얻기를 원한다.
N:식량창고 개수 (3<= N <100)
input : 4
1 3 1 5
output: 8

# 개미전사
n = int(input())

array = list(map(int,input().split()))

d = [0] * 100

d[0] = array[0]
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])    

바닥공사

가로길이 : N, 세로길이: 2인 직사각형 형태의 얇은 바닥을 1x2, 2x1, 2x2 덮개를 이용해 채우고자한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. (1<=N<=1000)

# 바닥공사
n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3,n+1):
	d[i] = (d[i-1] + 2 * d[i-2] ) % 796796
print(d[n])    

효율적인 화폐 구성

N가지 종류의 화폐를 최소한으로 이용해서 그 가치의 합이 M원이 도록하려고 한다. (1<=N<=100, 1<=M<=10000)

# 효율적인 화폐 구성
n, m = map(int,input().split())

coin = []
for i in range(n):
	coin.append(int(input()))

d = [1001] * (m+1)

d[0] = 0
#  ai : 금액 i를 만들 수 있는 최소한의 화폐 개수 :
# 화폐의 단위 : k
# a(i-k) : (i-k)를 만들 수 있는 최소한의 화폐 개수

for i in range(n):
	for j in range(array[i], m+1):
    	if d[j-coin[i]]!= 10001: #(i-k)원을 만드는 방법이 존재하는 경우
        	d[j] = min(d[j],d[j-coin[i]] + 1)

if d[m] == 10001:
	print(-1)
else:
	print(d[m])