1. 다중 배낭 문제(multiple 0-1 knapsack) https://atcoder.jp/contests/past202206-open/tasks/past202206_h H - Two KnapsacksAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 각각 무게 제한이 A,B인 2개의 가방이 있다고 하자. 이 2개의 가방에 무게가 W, 가치가 V인 물건을 담고자 한다. 2개의 가방에 담긴 물건 가치 합이 최대가 되도록 하는 방법은? 처음에는... 단순히 무게 제한이 A인 가방에 물건을 담고, 담은 물건은 제외한 다음 무..
12865번: 평범한 배낭 (acmicpc.net) 최대 한도 무게가 K로 정해진 가방 1개에 무게가 W이고 가치가 V인 N개의 물건을 담고자 할때, 가치가 최대가 되도록 담고자 한다. 당연히 하나의 물건은 가방에 한번만 담을 수 있다 1. 1차원 배열 DP[i] = 가방에 담긴 물건들의 무게 합이 i일때, 가치의 최댓값 DP[i] = max(DP[i], DP[i-w] + v) dp = [0]*(K+1)for w,v in bag: for i in range(K,-1,-1): if i-w >= 0: dp[i] = max(dp[i], dp[i-w] + v)print(dp[K]) 주목할 부분은 무게 i = 0,1,2,3,..,K가 아..
15487번: A[j]-A[i]+A[l]-A[k] (acmicpc.net) 크기 N인 주어진 배열 A에서 i N은 최대 1000000이라 4중 for문으로 찾는건 당연히 불가능하다 A[j] - A[i]의 최댓값과 A[l] - A[k]의 최댓값을 나눠서 구하면 좋을 것 같다 근데 i 어떻게 구할 수 있을까? 현재 0 ~ j 구간을 보고 있을때 A[j] - A[i]의 최댓값은, A[j] - (A[0] ~ A[j-1]중 최솟값) dp[j] = i j = 0, 1, 2, 3, ... 가면서 A[j]의 최솟값을 min_value로 항상 갱신해놓는다면, 현재 j에 대해 0~j-1까지 최솟값은 min_value이고 그러므로 A[j] - min_value로 최댓값을 구할 수 있다. 이를 dp[j]에 저장해놓고 ..
E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 대문자 알파벳 A,B,C,..,Z의 개수가 주어질때, 이들로 만들 수 있는 길이 1부터 k까지 모든 문자열의 개수를 구하는 문제 길이가 s일때, 각각 A,B,C,...,Z 문자가 a1,a2,a3,...,a26개 있다고 한다면.. 이들을 일렬로 배열하는 복수순열의 개수와 같으므로, $$\frac{(a1+a2+a3+...+a26)!}{a1!a2!...a26!} = \frac{s!}{a1!..
1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..
1. 방향 비순환 그래프(Directed acyclic graph) 사이클이 존재하지 않는 방향 그래프 정점 u에서 출발했을때, u로 돌아오는 방법이 없다. 다음과 같은 그래프는 방향 비순환 그래프(DAG)이다. 2. 한 정점에서 다른 정점까지 가장 긴 경로의 길이 정점 v에 대하여 DP[v]를 v에서 출발할때 도달할 수 있는 가장 긴 경로의 길이라고 정의한다면... 다음과 같이 v에서 c1,c2,c3,...로 갈 수 있을텐데, c1,c2,c3,...에서 출발하여 도달할 수 있는 가장 긴 경로의 길이 DP[c1],DP[c2],...가 이미 구해져있다면... DP[v] = max(wi + DP[ci])으로 구할 수 있을 것이다. 다이나믹 프로그래밍은 이미 해결한 작은 문제를 이용해서 더 큰 문제를 해결하는..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
