동빈나 님의 이코테 2021 강의 몰아보기 를 보면서 공부한 내용을 정리하고 있습니다. 더 자세한 내용은 이것이 취업을 위한 코딩 테스트다 with 파이썬 을 참고해주세요 학습 도구로는 리플렛 을 사용하고 있고 원본 소스코드는 동빈님의 Github 에서 확인할 수 있고 스스로 공부한 소스코드는 Github 에서 확인할 수 있습니다.다이나믹 프로그래밍
•
메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법
•
이미 계산된 결과는 별도의 메모리영역에 저장하여 다시 계산하지 않도록 한다.
◦
한번 계산해서 해결한 문제는 다시 계산하지 않도록 한다.
•
다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식으로 구성된다.
◦
top-down
◦
bottom-up
•
동적 계획법이라고도 부름!
◦
일반적으로 동적이라는 의미 in programming
◦
자료구조에서 동적할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법
◦
다이내믹 프로그래밍에서 다이내믹은 별다른 의미 없이 사용된 것임
•
다음의 두 경우에 쓴다.
◦
최적 부분 구조
▪
optimal substructure
▪
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
◦
중복되는 부분 문제
▪
overlapping subproblem
▪
동일한 작은 문제를 반복적으로 해결해야한다.
•
예
◦
피보나치수열
피보나치 수열
•
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
•
점화식
◦
인접한 항들 사이의 관계식을 의미
•
피보나치 수열을 점화식으로 표현
•
프로그램 상에서는 수열ㅇ르 배열이나 리스트를 이용해서 표현한다.
# 피보나치 수열# 4 번째 피보나치 수 구하기def fibo(x):
if x == 1 or x == 2:
return 1 return fibo(x-1) + fibo(x-2)
print(fibo(4));# output : 3
Python
복사
•
하지만 이렇게 단순이 재귀함수로 호출할 경우 지수 시간 복잡도를 가지게 됨
◦
N의 값이 조금만 커지더라도 문제가 됨
◦
빅오표기법 : O(2^n)
•
단순히 6번째 피보나치 수만 구하더라도 중복이 5번이나 발생하게 된다.
•
한번 연산된 결과는 메모리에 보관할 수 있도록 한다.
•
f(30) 을 구하기 위해서는 10억 가량의 연산을 수행해야함
•
f(100) 을 구하기 위해서는? 비현실적인 수행시간이 발생하게 된다.
•
해결방법은? 다이나믹 프로그래밍!
◦
다음의 조건을 만족하나?
▪
최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다. -> 만족! f(4) 를 구하기 위해서 f(3), f(2) 를 구해야함
▪
중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결한다. -> 여러번 중복 연산을 하게 됨
◦
만족한다고 판단됨!
메모이제이션
•
한번 계산한 결과를 메모리 공간에 메모하는 기법
◦
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
◦
값을 기록해놓는다는 점에서 캐싱이라고 한다.
◦
그래서 변수도 caching, d, dp, table 등을 사용한다.
•
메모이제이션(탑다운)은 하향식 방법
◦
보텀업 방식은 상향식! -> 반복문을 이용함
•
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
◦
결과 저장용 리스트는 dp table 이라고 부른다.
•
엄밀히 말하자면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미한다.
◦
다이나믹 프로그래밍에 국하된 개념은 아니다.
◦
한번 계산된 결과를 담아놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.
◦
따라서 메모이제이션 != 다이나믹 프로그래밍
상향식 메모이제이션으로 피보나치 수열 해결해보기
•
별도의 리스트를 사용하여 문제를 풀면 답을 계속 기록해나간다는 점에서, 해당 문제가 이전에 해결된적 있는 문제인지 알 수 있다.
# 피보나치 수열# 99 번째 피보나치 수 구하기d = [0] * 100def fibo(x):
if x == 1 or x == 2:
return 1 # 이미 계산된 적 있다면 해당 값을 가져다가 쓴다. if d[x] != 0:
return d[x]
# 한 번 연산을 완료하면 d array 에 값을 넣는다. d[x] = fibo(x-1) + fibo(x-2)
return d[x]
print(fibo(99));# output : 218922995834555169026
Python
복사
하향식 메모이제이션으로 피보나치 수열 해결해보기
# 피보나치 수열# 99 번째 피보나치 수 구하기d = [0] * 100d[1] = 1d[2] = 1n = 99for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
# output : 218922995834555169026
Python
복사
•
메모이제이션을 이용하는 경우 시간 복잡도는 O(N) 이 된다.
◦
메모리를 N만큼 가질 수 있다는 전제하에!
다이나믹 프로그래밍 vs 분할정복
•
공통점 : 모두 최적 부분 구조를 가질 때 사용할 수 있다.
◦
큰 문제를 작은 문제로 나누고
◦
작은 문제의 답을 모아서 큰 문제를 해결한다.
•
차이점 : 부분문제의 중복
◦
다이나믹 프로그래밍 : 각 부분 ㅁ누제들이 서로 영향을 미치고 부분 문제가 중복됨
◦
분할 정복 문제 : 동일한 부분문제가 반복적으로 계산되지 않는다.
•
다이나믹 프로그밍 접근 방법
◦
가장 먼저 그리디, 구현, 완전탐색 아이디어로 문제 해결할 수 있는지 검토
◦
다른 알고리즘으로 풀이방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려한다.
◦
재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있다면 코드를 개선하는 방법을 사용한다.
▪
예) 피보나치 수열
◦
일반적인 코테에서는 기본 유형의 다이내믹 프로그래밍 문제가 출제되는 경우가 많다.
개미전사 문제
•
개미전사는 부족한 식량을 보충하고자 메뚜기 마을의 식량창고를 공격하려고 한다.
•
메뚜기 마을의 식량창고는 일직선으로 이어져있다.
•
각 창고는 정해진 수의 식량들이 저장되어있고 개미 전사들은 선택적으로 약탈하여 식량을 최대한 많이 빼앗을 예정이다.
•
일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있기에 최소 한칸이상 떨어진 식량창고를 약탈해야한다.
•
예시
◦
<창고 0 : 1개> - <창고 1 : 3개> - <창고 2 : 1개> - <창고 3 : 5개>
◦
이때는 두번째와 네번째 창고를 털어야 최대 식량값인 8개를 빼앗을 수 있다.
•
식량창고 N의 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하라!
•
조건
◦
식량창고 N의 개수가 3이상 100이하로 주어진다.
◦
각 창고에 저장된 식량 개수 K 가 공백 기준으로 주어진다.
해결 아이디어
•
N=4 일 때, 총 8가지의 경우의 수가 있음
•
이 때 가장 많은 식량을 약탈하는 경우의 수는 3개와 8개를 약탈하는 8개의 경우이다.
•
ai = i번째 식량창고까지의 최적의 해 라고 가정한다면 다이나믹 프로그래밍을 적용할 수 있다.
•
DP table
◦
a0 = 1
◦
a1 = 3
◦
a2 = 3
◦
a3 = 3+5 = 8
•
왼쪽부터 식량창고를 턴다고 했을 때, 특정 i번째 식량창고에 대해서 털지 안털지 여부를 결정하면 2가지 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다.
# 개미전사 문제n = int(input())
k = list(map(int, input().split()))
d = [0] * 100d[0] = k[0]
d[1] = max(k[0], k[1])
for i in range (2, n):
d[i] = max(d[i-1], d[i-2] + k[i])
print(d[n-1])
Python
복사
1로 만들기 문제
문제
•
정수 x가 주어졌을 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지 이다.
1.
x가 5로 나누어지면 5로 나눈다.
2.
x가 3으로 나누어지면 3으로 나눈다.
3.
x가 2로 나누어지면 2로 나눈다.
4.
x -1을 한다.
•
이 때, 연산 4개를 이용해서 값을 1로 만들고자 할 때, 연산의 최소값을 구하는 문제
•
예시
◦
26 -> 25 -> 5 -> 1
•
조건
◦
x는 1이상 3만 이하로 주어진다.
◦
연산하는 횟수의 최솟값을 출력해야한다.
앞선 그리디 해법으로 풀 수 없는 이유
•
단순히 나누기가 가능할때 나누는 것보다 뺄샘과 나눗셈을 적절하게 사용해서 푸는 것이 훨씬 더 이득이 된다.
•
예를들면, 26의 경우,
◦
2로 나누어진다고 해서 2로 나눗셈을 하는 것보다 -> 6번
◦
1을 먼저하고 5로 두 번 나누는 것이 연산 횟수를 더 최소화할 수 있다. -> 3번
•
오히려 이 문제는 최적 부분 구조와 중복 되는 부분 문제를 만족하므로 다이나믹 프로그래밍을 적용하는 것이 해법이 될 수 있다.
# 1로 만들기 문제# 나누기먼저 -> 뺄샘x = int(input())
d = [0] * 30001# d[0] 는 안쓰는 것으로 가정# d[1] = 0 : 본인이 가장 최소값이므로# 2 -> 1 : 1# 3 -> 1 : 1# 4 -> 2 -> 1 : 2# 5 -> 1 : 1# 6 -> 5 -> 1 : 2# 7 -> 6 -> 2 -> 1 : 3for i in range(2, x+1):
d[i] = d[i-1] + 1 if i % 2 == 0:
d[i] = min(d[i], d[i//2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1)
if i % 5 == 0:
d[i] = min(d[i], d[i//5] + 1)
print(d[x])
# 26# 3
Python
복사
효율적인 화폐구성 문제
문제
•
N가지 종류의 화폐가 있다.
•
화폐 개수를 최소한으로 해서 그 가치의 합이 M원이 되도록 하려고 한다.
•
각 종류의 화폐는 몇 개라도 사용할 수 있다.
•
예를 들어서 2원, 3원 단위의 화폐가 있을 때에는 15원을 만들기 위해서 3원 * 5개를 사용하는 것이 가장 최소한의 화폐 개수이다.
•
M원을 만들기 위한 최소한의 화폐 개수를 출력하세요
•
조건
◦
N, M이 주어진다.
◦
1<= N <= 100, 1<= M <= 10,000
◦
이후의 줄에는 N개 만큼 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수임
◦
불가능 할 때에는 -1을 출력한다.
◦
예시 1)
▪
입력
•
2 15
•
2
•
3
▪
출력
•
5
◦
예시 2)
▪
입력
•
3 4
•
3
•
5
•
7
▪
출력
•
1
해결 아이디어
•
초기화
•
제일 처음 값인 0만 0으로 초기화해주고
•
나머지 값들은 모두 불가능하다는 의미로 현재 주어진 수 범위에서 나올 수 없는 값을 임의로 넣어준다.
•
이 문제에서는 10,001이 될 수 있음 (1<= M <= 10,000)
•
첫번째 화폐 단위인 2를 살펴본다.
•
각 화폐단위의 배수값은 모두 만들 수 있기 때문에 최소화폐금액 + 1 씩 하여 개수를 초기화해준다.
•
이 턴에서는 2, 4, 6, … 등 2의 배수 금액들은 모두 개수가 업데이트 된다.
•
두번째 화폐 단위인 3을 점검한다.
•
3을 통해서 만들 수 있는 화폐 금액인 3, 6, … 등을 업데이트 한다.
•
이 턴에서는 7도 초기화 될 수 있는데 7 의 세칸 앞인 4에서 3을 더하면 7을 만들 수 있기 때문에 3으로 업데이트 할 수 있다. (7 = 2+2+3)
•
세번째 화폐 단위인 5를 점검한다.
•
5를 통해서 만들 수 있는 금액을 업데이트 하고
•
5를 통해서 개수를 줄일 수 있는 수들도 업데이트 한다.
결론적으로 7을 만들기 위한 최소한의 화폐 개수는 2개가 된다!
# 효율적인 화폐구성# n : 화폐의 개수# m : 만들어야 하는 돈의 금액# 화폐의 가치들 : values[]n, m = map(int, input().split())
values = []
for i in range(n):
values.append(int(input()))
d = [10001] * (m+1)
d[0] = 0for i in values:
for j in range(i, m+1):
if d[j-i] != 10001:
d[j] = min(d[j], d[j-i]+1)
if d[m] == 10001:
print(-1)
else :
print(d[m])
# input# 2 15# 2# 3# output# d = [0, 10001, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]# 5
Python
복사
금광 문제
조건
•
입력
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 2 5 0 2 3 0 6 1 2
Plain Text
복사
•
출력
19
16
Plain Text
복사
해결 아이디어
# 금광문제t = int(input())
def mining():
goldmines = []
n, m = map(int, input().split())
nums = list(map(int, input().split()))
idx = 0 # dp table 초기화 for i in range(n):
goldmines.append(nums[idx:idx+m])
idx += m
# dynamic programming for j in range(1, m):
for i in range(n):
if i == 0: left_up = 0 else: left_up = goldmines[i-1][j-1]
if i == n - 1: left_down = 0 else: left_down = goldmines[i+1][j-1]
left = goldmines[i][j-1]
goldmines[i][j] = goldmines[i][j] + max(left_down, left, left_up)
result = 0 for i in range(n):
result = max(result, goldmines[i][m-1])
return result
for i in range(t):
print(mining())
# 2# 3 4# 1 3 3 2 2 1 4 1 0 6 4 7# 4 4# 1 3 1 5 2 2 4 2 5 0 2 3 0 6 1 2
Python
복사