[문제실습] Ch 8. DP

보통 알고리즘을 작성할 때, 연산 속도와 메모리 공간을 최대한 활용할 수 있도록 효울적으로 작성하는데,

어떤 문제는 메모리 공간을 약간 더 사용하면 연산속도를 비약적으로 증가시킬 수 있는 방법이 있다.

그 방법 중 대표적인 방법이 다이나믹 프로그래밍 기법이다.

 

[ 다이나믹 프로그래밍을 사용할 수 있는 조건 ]
     1. 큰 문제를 작은 문제로 나눌 수 있다.

     2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

다이나믹 프로그래밍을 코드로 구현하기 위해서는 메모이제이션 기법을 사용하는데,
그저 다이나믹 프로그래밍 구현 방법 중 하나라고 생각하면 된다.

메모이제이션 기법은 한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면

메모한 결과를 그대로 가져오는 기법을 의미한다.

(보통 메모리 공간은 dictionary나 list를 사용하는 것 같다)

 

1. 1로 만들기

나의 생각)
가능한 연산은 2,3,5로 나누는 것과 1로 빼는 것이다.

 

메모리에 저장할 값은 정수 i에서 1 ~ i까지의 연산 최소 횟수로 정의하였다.

값을 계산하기 위해 arr[0] = 0; arr[1] = 0; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 1를 미리 초기값으로 지정하였다.

''' 
input 1:[26]
output: 3 
input 2: [20730, 16465, 27368, 21803, 29081, 23215, 16419, 12244, 16602, 25045]
output 2: 10 13 11 13 14 13 11 11 11 10
input 3: [20730, 16465, 27368, 21803, 29081, 23215, 16419, 12244, 16602, 25045]
output 3: 8 10 9 9 11 11 11 8 11 10 
'''
nums = [8000, 6814, 2553, 3918, 7034, 5806, 5471, 3012, 6986, 5347]

def make_to_one(n):
    arr = [0 for _ in range(n+1)]
    arr[0] = 0; arr[1] = 0; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 1

    if n <= 5: 
        print(arr[n])

    operaters = [1,2,3,5]
    for a in range(6, n+1):
        candidates = [30000,30000,30000,30000]
        candidates[0] = arr[a-1] + 1
        if a % 2 == 0:
            candidates[1] = arr[int(a/2)] + 1
        if a % 3 == 0:
            candidates[2] = arr[int(a/3)] + 1
        if a % 5 == 0:  
            candidates[3] = arr[int(a/5)] + 1
        arr[a] = min(candidates)

    print(arr[n], end = ' ')

for num in nums:
    make_to_one(num)

 

2. 개미 전사

주어진 배열에서 한 칸 이상 띄워서 더했을 때 나올 수 있는 최댓값을 구해야 하는 문제이며,

메모리에 저장할 값은 해당 i번째까지 구할 수 있는 최댓값으로 정의하였다.

 

최댓값을 구할 때 나올 수 있는 경우의 수는

     1) 더하지 않을 때: i-1번째에 저장된 값을 저장

     2) 더할 때: i-2번째에 저장된 값에 현재 i값을 더한 값을 저장

 

따라서 i에 저장할 최댓값은 위 경우의 1), 2) 값을 비교하여 나오는 최댓값을 구해서 대입하면 된다.

# n = int(input())
# storage = list(map(int, input().split()))
# print(n, storage)

'''
input 1: 4, [1,3,1,5]
output 1: 8

input 2: 10, [11, 6, 12, 3, 4, 1, 18, 2, 17, 16]
output 2: 62
'''

n, storage = 15, [1, 100, 1, 1, 1, 100, 1, 100, 100, 1, 1, 100, 100, 100, 1]
table_DP = [0 for _ in range(n)]

table_DP[0] = storage[0];
table_DP[1] = max(storage[0], storage[1])

for i in range(2,n):
    candidates = []
    # defore max sum
    candidates.append(table_DP[i-1])
    # front + my sum
    candidates.append(table_DP[i-2] + storage[i])
    table_DP[i] = max(candidates)

print(table_DP[n-1])

 

3. 바닥 공사

숫자에서 뿐만 아니라 도형적인 패턴에서도 큰 문제를 작은 문제로 쪼갤 수 있는지를 판단하기 위한 문제라고 생각한다.

 

메모리에 저장할 값을 가로가 i일 때, 바닥을 채울 수 있는 모든 경우의 수로 정의하였다.

그러나, [i-1]과 [i]와의 관계성을 구하는데 2x1의 덮개에서 중복이 발생해 이를 해결해야 했다.

 

이를 해결하기 위해서는 [i-1]와 [i-2]와 [i]의 관계를 살펴보아야 하는데,

1) [i-1]에서 [i]까지는 2x1만 채울 수 있다.

2) [i-2]에서 [i]까지는 2x1과 1x2와 2x2가 다 채워질 수 있는데,

                              여기서 2x1은 1)의 경우에서 채울 수 있으므로 

총 우리가 고려해야 하는 것은  [i-1]에서 2x1로 채울 때, [i-2]에서 1x2 또는 2x2로 채울 때만 고려하면 된다.

 

!) 아 참, 큰 수로 나누는 이유는 모든 경우의 수는 값이 커지므로 출력 범위를 줄이기 위함이라고 한다.

#n = int(input())
n = 345
div_num = 796796

'''
input:  [760,    765,    378,    345,    4,  521,    741,    640,    464,    530] # n이 들어있는 배열
output: [536911, 448425, 551139, 336313, 11, 373121, 481185, 496871, 646635, 603879] # n에 해당하는 answer가 들어있는 배열
'''

table = [0 for _ in range(1001)] # 1 <= n <= 1000, table = [0] * 1001
table[1], table[2] = 1, 3

for i in range(3, n + 1):
    table[i] = table[i-1] + 2 * table[i-2]

print(table[n] % div_num)

 

4. 효율적인 화폐 구성

이부분을 풀면서 그리디와 DP를 구분해보았는데 여기서 중요한 건 "정당성"이다. 그리디에서는 화폐의 단위가 배수로 커졌기 때문에 큰 수부터 나누는 것이 맞으나, 화폐 단위끼리 간격이 달라진다면 무조건 큰 화폐로 채우는 것이 최선이 아닐 수 있다.

 

예를 들면 화폐 종류가 3개로 1, 7, 11 이렇게 있다고 하자. 우리가 구해야하는 화폐의 금액은 115원이다.

그리디 방식으로 풀게 된다면, '11' 10개, '1' 5개로 총 15개가 필요하다.

그러나, 11+7=18로 115는 18*6 + 7이므로 따라서 '11' 6개 '7' 7개로 총 13개가 필요하다.이로써 화폐 단위가 다를 때 큰 수부터 나누어 구하는 것이 최선의 값을 보장하지 못한다.

 

다시 DP로 돌아오자면, 메모리에 저장할 값은 화폐로 저장할 수 있는 최소 개수로 정의하였다.화폐 종류가 2 하나라면,a) 2부터 n까지 2로 만들 수 있는 i번째에 값을 갱신한다.

 

화폐 종류가 하나 이상이라면,b1) 화폐 선택  b2) a)를 반복하면 된다.

 

이때 갱신할 값은 현재 자신에 채워진 개수 & 자신이 가진 돈에서 화폐 단위만큼 뺐을 때 최소 개수 + 1을 비교해서 작은 값으로 갱신하면 된다.

# n,m = map(int, input().split()) 
# coins = [0] * n
# table = [10001] * (m + 1) # 0 <= m <= 10000
# for i in range(n):
#     coins[i] = int(input());     table[coins[i]] = 1

# input 1 
n, m = 3, 115
coins = [1, 7, 11]
# ouput 1
14

'''
input 2
n, m = 10, 9668
coins = [50, 46, 80, 85, 66, 28, 95, 22, 99, 7] 
output 2
98
input 3
n, m = 10, 5726
coins = [92, 72, 97, 89, 29, 12, 80, 90, 81, 16]
output 3 
60
'''
table = [10001] * (m + 1) # 0 <= m <= 10000

for coin in coins:
    table[coin] = 1

for coin in coins:
    for step in range(coin, m+1):
            table[step] = min(table[step], table[step-coin] + 1)

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