devbelly

문제 https://www.acmicpc.net/problem/5832 알고리즘 Greedy 풀이 겹치는 선분이 있을 때, 해당 구간을 잘라 그리디하게 푸는 문제입니다. $K$ 쌍을 입력받고 선분의 끝점 값을 기준으로 정렬합니다. 현재 보고 있는 선분의 구간이 [u,v] 일 때, 선분들 중 시작점에 있는 값이 v보다 작다면 겹치는 구간이 발생하는 선분입니다. 해당 선분들은 [u,v] 구간을 자를 때 같이 해결이 되므로 $visited$배열을 통해 체크하며 답을 찾으면 쉽게 풀 수 있습니다. $K$쌍이 주어질 때 u>v 일 수도 있으니 u>v라면 swap을 통해 시작점 N >> K; rep(i, K) { int u, v; cin >> u >> v; if (u > v) swap(u, v); vt.emplac..

문제 https://www.acmicpc.net/problem/5872 알고리즘 Greedy 풀이 올바른 괄호문자열을 만들기 위해 몇 개의 문자를 추가해야하는지에 대한 문제와 거의 비슷합니다. 괄호 하나를 뒤집는 것은 두 개의 문자를 추가하는 것과 일치합니다. 왼쪽부터 문자열을 검사하며 만일 닫는 괄호가 더 많아지는 순간에는 바로 해당 괄호를 여는 괄호로 바꿉니다. 문자열 끝까지 검사한 후 괄호쌍이 맞지 않다면 $sum$만큼의 닫는 괄호를 추가해주면 해결가능합니다. 이는 $sum/2$ 횟수만큼 괄호를 뒤집는 것과 일치합니다. 코드 #include #define rep(i, n) for (int i = 0; i s; in..

문제 https://www.acmicpc.net/problem/1887 알고리즘 bitmask 풀이 모든 subset중 특정 subset을 포함하는 여부를 확인하는 문제입니다. $T$제한이 20이므로 비트마스크의 느낌이 팍팍납니다. 현재 subset이 어떠한 subset을 갖고 있는지는 &연산을 통해 바로 확인이 가능합니다. 코드 #include #define rep(i, n) for (int i = 0; i T >> N; rep(i, N) { cin >> cnt; while (cnt--) { cin >> num; num--; cst[i] |= (1

문제 https://www.acmicpc.net/problem/8980 알고리즘 Greedy 풀이 1부터 N까지 트럭이 이동하며 배송을 할 때, 최대 배송량을 구하는 문제입니다. 1마을에서 모든 택배를 들고 있을 때, 포기 해야하는 택배는 1마을로부터 가장 먼 택배들입니다. 이 택배는 오래 들고 있을수록 중간마을에서의 배송을 방해하기 때문입니다. 도착마을을 기준으로 오름차순으로 정렬하여 다른 택배들에게 영향을 덜 주는 순서대로 처리해나가면 풀 수 있습니다. 영향을 준다는 것은 현재 처리하고 있는 택배의 도착지가 다른 택배들의 시작점과 도착점 사이에 있다는 것인데 도착마을을 기준으로 오름차순 정렬하면 이와 같은 일이 최소화 됩니다. 코드 #include #define rep(i, n) for (int i ..

문제 https://www.acmicpc.net/problem/1231 알고리즘 knapsack 풀이 $D$일동안 갯수제한없는 knapsack을 하는 문제입니다. 그리디한 DP임을 눈치채야 풀 수 있습니다. A일에 사서 B일에 파는 것은 A+1일에 해당 주식을 팔지 말지 결정하고 팔았다면 무조건 재매수를 하는 것을 B일까지 반복하는 것과 동일합니다. 만일 10 15 20에 해당하는 주식이 있다면 10에 주식을 사서 3일째 되는 날 20에 팔아 10의 이득을 챙기는 것과 2일째에 15에 팔고 다시 15에 사서 20에 파는 것은 동일합니다. 즉 갯수제한이 없는 knapsack을 D-1일 동안 하는 것과 동일한 문제로 바뀌게 됩니다. $cache[i]$= 현재 사용가능한 돈이 $i$원일때, 얻을 수 있는 최대..

문제 https://www.acmicpc.net/problem/12865 알고리즘 knapsack 풀이 갯수제한이 있는 01 knapsack 문제입니다. $cache[i]$=현재 담은 무게가 $i$ 일때 얻을 수 있는 최대가치 안쪽 포문을 역순으로 고려하면 갯수를 하나 택할 때 상황만을 고려할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> K; rep(i, N) rep(j, 2) cin >> bag[i][j]; rep(i, N) { for (int j = K; j >= bag[i][0]; --j) { cache[j] = max(cache[j], cache[j..

문제 https://www.acmicpc.net/problem/6066 알고리즘 Knapsack 풀이 갯수제한이 없는 01 Knapsack 문제입니다. $cache[i][j]$ = $i$번째 물건까지 택하고 현재 얻은 hay양이 $j$ 일때 지불해야하는 최소 금액 으로 가정하면 풀 수 있습니다. $cache[i][j]$가 갱신하는 다음 상태는 현재 상태에서 hay를 구매했을때 상태인 $cache[i][j+hay]$ 와 현재 물건을 택하지 않고 다음 물건을 택하는 $cache[i+1][j]$가 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >> H; rep(i, N) ..

문제 https://www.acmicpc.net/problem/7045 알고리즘 DFS 풀이 각 정점을 루트로 했을 때, 서브트리 크기의 최댓값이 절반 이하가 되는 정점을 찾는 문제입니다. 문제에서 주어진 $N$ 제한은 1만이므로 각 정점마다 DFS를 돌리면 $O(N^2)$ 이므로 시간초과를 받게 됩니다. 한 정점에서 DFS를 시작하여 임의의 정점에 도달했을 때, 해당 정점의 서브트리의 크기는 재귀적으로 찾을 수 있습니다. 추가적으로 고려해야할 것은 현재까지 탐색한 트리의 크기입니다. 이 정보는 현재까지 탐색했던 트리를 제외한 서브트리 크기의 총합을 안다면 $N-sum[i]$를 통해 구할 수 있습니다. $sum[i]$는 서브트리크기의 총합을 의미합니다. DFS를 수행한 후 각 정점마다 $MAX[i]$ 값..