몰랐다!나는 몰랐다!
생애 첫 코딩테스트를 보고 나니 느끼는 것들
- 나 알고리즘 공부 제대로 안했다 호호
- 왠지 내장 함수가 있는 python이 c보다 빨리 할 수 있을 것 같다
- 하지만 난 python을 잘 모른다
- 3시간 버티기 제법 힘들ㄷ..
그러니까 공부 대충하지 말자...
고등학교 때 써본 게 마지막이었던 python을 꺼내보자...
물론 문제를 빨리 푸는 게 목적이라 python을 꺼내보는 것 뿐만은 아니고, C만 사용할 줄 안다는 것이 나의 확장성 에 조금 부끄러움을 느꼈기 땜문
하지만 python 1도 기억안나..
설치부터
- pyhton idle ; 불편..안 익숙..
하지만! 두둥!
더 좋은 게 있었다! 두둥!
친구덜이 쓰는 게 뭔가 했더니 vs code였다.. 이제 깨달았어!
역시 나는 비전공생이라 할 만 하구먄 콜록
Knapsack Problem
n개의 item이 있다
각 item의 무게(weight)는 wi, 이득(profit)은 pi
가방에 최대한 넣을 수 있는 무게는 W
W를 넘지 않으면서 이득(profit)을 최대화하려면 각 item을 넣을까(1)/말까(0) 결정해야 한다!
*이 때 만약 item을 쪼개서 넣을 수 있다면 Fractional Knapsack Problem!
그렇지 않다면 0-1 Knapsack Problem!
*참고
설명이 훌륭한 선생님 블로그
boj 평범한 배낭
먼저, DP(dynamic programming)이란
Dynamic Programming
table을 만들어 작은 문제들의 계산값을 기억하며, 그 값을 이용해 간단한- 시간 내에 큰 문제들의 계산을 하려고 하는 것!
DP로 풀 수 있는가
DP로 풀 수 있는지는 Principle of Optimality가 성립하는지 보면 된다.
Principle of Optimality
어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.
라고 블로그 선생님께서는 첨부해두셨다
교과서에는
Principle of Optimality
The Principle of Optimality is said to be applicable to a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances.
결국
큰 문제의 해가 최적(optimal)이다~ 라고 하면 작은 문제의 해도 최적이다~
라고 할 수 있으면 principle of optimality가 성립한다는 거다!
오호
그럼 0-1 Knapsack Problem은 Principle of optimality를 성립하는지 어떻게 알 수 있을까? 증-명해보면 된다.
(생략)
그럼 "큰" 문제들은 "작은" 문제들을 가지고 어떻게 풀 수 있을까
어떻게 반복되는지 확인하면 된다. (점화식 찾기)
점화식
i번째 item을 일단 넣을 수 있는가? 들어가긴 함?
- 들어가긴 함
- 이득이 늘어나니까 넣어야지
- 얘 안 넣는 게 낫겠다
- 안 들어감
이런 경우의 수가 있다.
그러면 각 경우의 수에서는 어떤 것을 선택해야 할까
(w는 total weight 0 < w <= W, P[i][w]는 i번째까지 item 고려 시 무게 한도 w일 때 optimal profit)
- 들어가긴 함 : wi <= w
- 이득 늘어나니까 넣어야지 : P[i-1][w-wi] + pi
- 얘 안 넣는 게 낫겠다 : P[i-1][w]
- 안 들어감 : wi > w : P[i-1][w]
그렇다면 들어가긴 할 때, 둘 중의 최적 optimal은 누구인가
바로, max값! 이득이 최대가 되어야 하니까!
그래서 P[i][w]의 점화식은 이렇다.
P[i][w]
if wi <= w : max( P[i-1][w-wi] + pi , P[i-1][w])
else : P[i-1][w]
이제 작은 문제로 큰 문제를 풀 수 있는 점화식이 완성되었으니 table을 만들어 작은 문제의 해부터 채워보자.
table
(생략)
.
.
.
code
import sys
def knapsack(W, wt, val, n): #W 무게 한도, wt 각 보석 무게, val 각 보석 가격, n 보석 수
K = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i==0 or w==0:
K[i][w] = 0;
elif wt[i-1] <= w:
K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
#print(K[i][w], end=' ')
#print('\n')
return K[n][W]
wt = []
val = []
N,K = map(int,sys.stdin.readline().strip().split())
for i in range(N):
w,v = map(int, sys.stdin.readline().strip().split())
wt.append(w)
val.append(v)
print(knapsack(K,wt, val, N))끄-덕
이 와중에 알게된 python 지식
#map function
map(<function> , <iterable>) *iterable : list, tuple, dictionary, str)
map(int, a) : a를 int형으로
list(map(mul,a)) : list 요소에 3씩 곱해주기#split function
a.split()
공백으로 나누기
a,b,c = map(int, input().split()) *input은 속도가 느리다#strip function
rstrip() : right 공백 제거(\n 제거)
lstrip() : left 공백 제거
strip() : 양쪽 공백 제거#print function
print(,end' ') 공백으로 구분하여 가로로 출력max(a,b)
min(a,b)python에는 c처럼 if(a>b) max = a; else max = b;
해 줄 필요 없이 내장 함수가 있다...!
