돌이 코딩하는 방

문제 링크 https://www.acmicpc.net/problem/2243 문제 소개 두가지 행동을 하는 문제이다. 1. x 맛의 사탕의 갯수를 k개 변화시킨다. 2. k번째로 맛있는 사탕의 맛 수치를 출력한다. (1이 가장 맛있고 1000000이 최악) 문제 풀이 1번 쿼리는 굉장히 자주 나오는 쿼리이고 하나도 까다롭지 않게 작용한다. 중요한 것은 2번쿼리로 그니까 1부터 순서대로 늘어놓았을 때 k번째 숫자를 구하고 싶은 것이다. 구간 합 구하기의 가장 간단한 세그를 생각해보면 우리가 얻은 수 있는 값은 구간 의 합이다. 이 문제는 세그에는 추가적인 옵션을 가하지 않고, 이 값을 이용하여 문제를 해결할 수 있다. 이분 탐색이다. 1~i 구간의 합을 구할 수 있다. 그 값이 k이하인지 초과인지에 따라서..

문제 링크 : https://www.acmicpc.net/problem/17411 문제 소개 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이 와 그 갯수를 출력하시오. 문제 풀이 가장 긴 증가하는 부분 수열 즉 LIS를 $O(NlgN)$에 구하는 방법은 여러가지가 있다. 간단한 코딩으로는 lower_bound를 사용할 수 있으며, 이분탐색도 가능하며, 세그먼트 트리도 가능하다. 이 글에서는 세그먼트 트리를 활용한 방법을 설명하고 이를 이용하여 이 문제를 해결하는 방법을 설명하려고 한다. $O(NlgN)$ LIS by segment tree DP로 LIS 를 찾을 때 i번째 수를 마지막으로 하는 LIS값이 Li고, 수열의 값이 Ai라면 우리는 어떤 i에 대해서 1~i-1중 Ai보다 작은 값중 가장 ..

관련 알고리즘과 함께 푼 수열과 쿼리 문제들을 쭉 포스팅 하려고 한다. 문제 링크 : https://www.acmicpc.net/problem/17408 문제 소개 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ $10^9$) 2 l r: l ≤ i b.ff) { return tree[nod]=a; } else return tree[nod]=b; } pll sol(ll l ,ll r, ll s,ll e,ll nod) { if(er) return {0,0}; if(l

문제 링크 : https://www.acmicpc.net/problem/2463 문제 소개 그래프가 주어진다. 이 문제에서 Cost(u,v)는 가장 적은 비용의 간선부터 차례대로 끊어나갈 때, 점 u와 점 v가 처음으로 다른 컴포넌트가 될 때 까지 끊은 간선의 가중치의 총합이다. 이때 주어진 그래프에서 임의의 i

문제 링크 : https://www.acmicpc.net/problem/10067 문제 소개 길이 n의 수열을 k번 자른다. 자를 때 마다, 자른 후 양쪽 수열의 값의 각각의 합을 곱한 것만큼 점수를 얻는다. 이때 얻을 수 있는 최대 점수와 자르는 방법을 구하시오. 문제 풀이 우리는 이 문제를 최종 시점관점에서 보면서 점수에 어떤 값을 이 추가되었는지를 살펴보아야 한다. (a,b,c,d)를 (a,b),(c,d)로 잘랐다고 하자. 이러면 우리는 (a+b)*(c+d)의 점수를 얻게 된다. 이를 다른 식으로 풀어쓰면 ac+ad+bc+bd 만큼의 점수를 얻게 된다는 것이다. 이는 서로 다른 그룹에 속하는 임의의 두 값을 곱해서 더한 값이다. 결국 그전에 어떤 순서로 어떻게 잘랐건 간에, 마지막에 다른 그룹에 있..

문제 태그: https://www.acmicpc.net/problem/7578 문제 소개 2열에 걸쳐 N개의 숫자가 주어진다. 윗줄과 아랫줄에 한쌍의 같은 숫자가 선으로 연결되어있다. 교차되는 선의 쌍의 수를 구하시오. 문제 풀이 일단 같은 숫자끼리 (a,b)의 쌍을 만들어서 생각해보자. 우리는 N개의 (a,b)를 얻을 수 있으며 그중에 i,j 에 대해 $a_{i} b_{j} $ 또는 $a_{i} > b_{i}, a_{j} < b_{j} $를 만족하는 쌍의 갯수를 구하면 된다. 한 쌍의 두 값에 대해서 순서가 바뀌어있는 갯수를 세는 문제이며, 이를 흔히 inversion counting 문제라고 불린다. inversion counting 문제는 merge sort 혹은 se..

문제 태그 : https://www.acmicpc.net/problem/2357 문제 소개 N개의 숫자들이 주어지고 쿼리가 주어진다. 쿼리가 a,b가 주어지면 a번째 숫자부터 b번째 숫자 사이의 최솟값과 최댓값을 구해야 한다. 문제 풀이 지금은 N개의 숫자들이 바뀌지는 않지만, 아무튼 구간의 최댓값과 구간의 최솟값은 Segment Tree를 사용함으로써 한 번 구하는 데 $O(lgN)$에 구할 수 있음이 잘 알려져 있다. 구간합을 구할 때 구하고자 하는 구간에 포함되어지지 않는 노드는 0을 반환한다. 항등원이기 때문이다. 같은 이유로 최솟값 세그트리에서는 항등원인 inf를 반환해야 하고, 최댓값연산에서는 항등원이 -inf이므로 구간이 포함되어지지 않으면 -inf를 반환해야 한다. 코드 1 2 3 4 5 ..

문제 태그:https://www.acmicpc.net/problem/1761 문제 소개 간선의 길이가 있는 트리가 주어지고, 두 정점이 계속해서 주어지면, 그 두 정점사이의 거리를 계속 답하면 된다. 문제 풀이 LCA의 성질을 이용하면 쉽게 이 문제를 해결할 수 있다 a와 b의 LCA를 c라고 했을 때, a와 b사이의 거리는 a와 c사이의 거리+b와 c사이의 거리이다. 하지만 이것도 두 정점사이의 거리이므로, 좀 더 쉽게 이 문제를 해결하기 위해서 관점을 바꾸어보면, a와 b사이의 거리는 루트에서 a까지의 거리+루트에서 b까지의 거리- 2*루트에서 c까지의 거리이다. 우리는 dfs를 돌리는 과정에서 루트에서 어떤 정점까지의 거리를 쉽게 구할 수 있다. 또한 LCA는 이글에 따르면 전처리 과정 $O(Nlg..

문제 링크 : https://www.acmicpc.net/problem/1226 문제 소개 어떤 당이 빠져도 합이 과반수가 안되는 집합을 깔끔한 연합이라고 한다. 가장 큰 크기의 깔끔한 연합을 구하여라. 문제 풀이 가장 큰 크기의 깔끔한 연합을 구하는 것이 아니라 관점을 바꾸어서 크기가 K인 깔끔한 연합이 존재하는 지에 대해서 구해도 된다. 모든 값에 대해서 다 가능성을 구해주면 된다. 일단 기본적으로 몇 개의 값의 합이 K가 되어야 한다. 합이 K가 되는 여러가지 방법중 깔끔한 연합이 될 확률이 가장 높은 것은 것은 연합내의 가장 작은 값이 커야 한다는 것이다. 가장 작은 값만 빼더라도 과반수가 안되면 깔끔한 연합이라고 할 수 있고, 그러기 위해서는 연합내 가장 작은 값이 커야한다. 따라서 N개의 숫자..

문제 태그 : https://www.acmicpc.net/problem/2472 정말 좋은 문제라고 생각한다. 여러가지 테크닉을 같이 써야 문제를 해결할 수 있다. 그런데 최근에 재채점을 당해 틀려서 다시 푼 김에 글을 작성하였다. 문제 소개 그래프가 주어지고 3개의 출발 지점이 주어진다. 만약 지점 A와 B가 존재해서 출발지점 3곳에 대해서 모두 B가 A보다 출발 지점까지의 거리가 짧으면 A에는 매장을 설치할 수 없다. 각 지점에 대해서 질의를 던지면 그 지점에 매장을 설치할 수 있는지 대답을 해야한다. 문제 풀이 일단 그래프 상에서 어떠한 한 노드를 중심으로 다른 모든 점까지의 거리를 각각 구하는 것은 다익스트라를 3번 돌리는 것으로 쉽게 처리해 줄 수가 있다. 다르게 말하면 우리는 모든 노드에 대해..