보통 알고리즘을 작성할 때, 연산 속도와 메모리 공간을 최대한 활용할 수 있도록 효울적으로 작성하는데,
어떤 문제는 메모리 공간을 약간 더 사용하면 연산속도를 비약적으로 증가시킬 수 있는 방법이 있다.
그 방법 중 대표적인 방법이 다이나믹 프로그래밍 기법이다.
[ 다이나믹 프로그래밍을 사용할 수 있는 조건 ]
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])
'Algorithm&Problem > [Algorithm] 이.코.테.다' 카테고리의 다른 글
| [문제실습] Ch 7. Search (0) | 2021.02.15 |
|---|---|
| [문제실습] Ch 5. BFS/DFS (0) | 2021.02.08 |
| [문제실습] Ch 6. Sort (0) | 2021.02.07 |
| [문제실습] Ch 3. 그리디(greedy) (0) | 2021.01.23 |
| [7일차] 이.코.테.다! Ch6 정렬 (0) | 2020.10.02 |
