알고리즘 공부방

문제 www.acmicpc.net/problem/19456 19456번: Cocktails In the first line of input there are four space-separated integers $n$, $k$, $B$, $C$ ($1 \leq k \leq n \leq 500$, $1 \leq B, C \leq 10\,000$) --- the number of jars, the reach of the blender, the time needed to use the blender, and the time needed to swap www.acmicpc.net 길이 $N$의 수열이 주어지고, 할수 있는 연산은 1. $A_i$의 비용으로 i번째 칸을 체크 2. $B$의 비용으로 연속된 $k$개..

문제 https://www.acmicpc.net/problem/10556 10556번: KAMIONI The first line of input contains the integers N and M (1 ≤ N ≤ 105, 1 6 M 6 105), the number of trucks and the number of pairs of trucks we want to know the number of encounters for. The ith of the following N lines contains the description of the rout www.acmicpc.net 어떤 한 트럭이 수직선 상에서 A1, A2, A3, A4, ... , An (A1>A2A4 ... or A1A3

문제 https://www.acmicpc.net/problem/10355 10355번: Most Influential Pumpkin Pumpkins in Hagrid's garden have come to life! Now they walk, talk, date … and, of course, organize elections to choose the Head Pumpkin! It turns out that it is pretty simple to guess who will win the next elections - it will be one of the pumpkins of t www.acmicpc.net 처음에 입력 수열 A가 주어지고, 각 쿼리마다 [l, r]에 1씩 더하고, 전체 수열의 중앙값을..

문제 https://www.acmicpc.net/problem/1507 어떤 그래프에서의 임의의 두 정점 간의 최단거리가 모두 주어졌을 때, 조건을 만족하며 간선의 개수를 최소화할 수 있는 그래프를 찾는 문제이다. 풀이 기본적인 풀이는 $N^2$ 개의 간선을 모두 생성한 후, 필요 없는 간선을 하나씩 지워 가며 문제를 해결한다. 그렇다면 과연, 필요 없는 정점을 어떻게 구할 수 있을까? u->v 의 간선을 삭제하기 위해서는 u->w->v 의 경로와의 거리와 비교해 볼 필요가 있다. 1) adj[u][v]v 의 간선을 삭제해서는 안된다. u->v 의 최단거리는 다른 경유점을 거쳐 가면 안됀다는 뜻이기 떄문이다. 2) adj[u][v]==adj[u][w]+adj[w][v] u->v 의 간선을 굳이 놔둘 필요..

문제 https://www.acmicpc.net/problem/7626 직사각형 여러개가 주어졌을 때, 그 합집합의 넓이를 구하는 문제이다. 풀이 이 문제에 대한 풀이는 https://codedoc.tistory.com/421 에 매우 자세히 나와 있다. 직사각형들의 x좌표에 대해 직사각형의 왼쪽 변은 +1, 오른쪽 변은 -1을 해주는 이벤트로 생각할 수 있다. 따라서 그러한 이벤트들을 모두 x좌표에 대해 정리한 후 오른쪽으로 쭉 한번 훑어주면서 넓이를 구할 수 있다. 이제 잘 나눈 x좌표들에 대한 구간으로 그 구간 사이의 넓이만 구해주면 된다. x좌표들에 대한 이벤트로 정렬을 때린 후 구간을 나눴으니, 하나의 구간 내에선 구해야 하는 영역의 넓이는 변하지 않는다. 따라서 이벤트들을 잘 관리해주는 자료구..

문제 https://www.acmicpc.net/problem/1395 스위치 n개에 대하여 특정 구간의 스위치를 모두 반전시키거나, 구간에 있는 켜져 있는 스위치의 수를 세는 쿼리를 해결하는 문제이다. 풀이 세그먼트 트리를 이용한다. 세그먼트 트리의 각 노드가 해당 구간의 켜져 있는 스위치들의 수를 갖고 있다면, 2번째 쿼리는 쉽게 해결할 수 있다. 문제는 첫번째 쿼리가 하나의 스위치를 반전시키는 것이 아니라, 특정 구간의 모든 스위치들을 반전시키는 것이다. 따라서 세그먼트 트리 레이지 프로파게이션을 사용해야 한다. 레이지 배열에는 그 구간에 대한 반전 연산이 적용되었는가 여부를 저장한다. 구간합에 대한 레이지처럼 구간 업데이트를 할 때 자신이 완전히 속한 노드에 대해서, 레이지값을 자식들에게 넘겨주며..

문제 https://www.acmicpc.net/problem/2243 i번째 맛의 사탕을 추가/삭제 하는 쿼리와, 상자 안에 들어있는 사탕들 중 k번째로 맛있는 사탕을 뽑는 쿼리를 처리하는 문제이다. 풀이 각 사탕의 맛을 인덱스로 하는 펜윅 트리로 쿼리를 처리한다. 펜윅 트리는 추가/삭제 쿼리를 $O(logN)$ 안에 할수 있다. 두번째 k번째 사탕을 뽑는 쿼리는 1~i까지의 사탕의 개수에 대해서 이분탐색을 해주면 된다. 사탕의 개수를 묻는 쿼리가 $O(logN)$, 이분탐색이 $O(logN)$ 이므로 2번째 쿼리를 $O(log^2N)$ 안에 처리해 줄수 있다. 시간 복잡도 : $O(Qlog^2N)$ #include using namespace std; typedef long long ll; typed..

문제 https://www.acmicpc.net/problem/3653 1~n까지의 영화가 순서대로 쌓여 있을때 i번째 영화 위의 영화의 개수를 출력하고, i번째 영화를 맨 위로 올려놓는 과정을 반복하는 문제이다. 풀이 문제 설명 그대로 시뮬레이션을 하면 된다. N+M개의 칸을 준비해놓고, 영화는 마지막 N개 칸에 모두 넣어 놓은 다음, 하나씩 앞의 칸으로 옮겨 준다. 이때 각 영화 위의 영화 수를 찾아내기 위해서 펜윅 트리의 구간합을 사용한다. 시간 복잡도 : $O((N+M)lg(N+M))$ #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1e5; struct BI..