devbelly

문제 www.acmicpc.net/problem/1517 알고리즘 펜윅트리 풀이 $N$제한이 50만이고 배열의 inversion들을 카운트 하는 문제입니다. 버블소트에서의 교환횟수는 inversion의 수와 동일합니다. inversion이란 $i$$A[j]$ 인 상황을 의미합니다. inversion을 찾으면 swap을 진행하고 inversion의 수가 하나 줄어들고 inversion이 0이 되면 소트가 종료됩니다. 이중포문을 통해 $O(N^2)$에 inversion의 수를 구할 수 있지만 $N$제한이 50만이므로 더 빠른 알고리즘이 필요합니다. 이 문제와 비슷하다고 생각되어 좌표압축 + 세그먼트 트리로 해결하여 풀었지만 좀더 간단하게 푸는 방법을 설명해드리겠습니다. inversion을 카운트 하기 위해선..

문제 https://www.acmicpc.net/problem/1280 알고리즘 세그먼트트리 풀이 나무 인덱스 순서대로 나무를 심어나갑니다. 나무를 심을 때 필요한 비용은 지금까지 심은 나무들과의 거리만큼이 필요합니다. 먼저 떠오르는 풀이는 나무를 심을 때 마다, 지금까지 심은 나무들과의 거리를 일일이 탐색해 브루트 포스로 해결하는 것 입니다. 나무당 $O(N)$을 요구하므로 총 시간복잡도는 $O(N^2)$ 입니다. 역시 $N$의 최대는 20만이므로 시간초과 입니다. 하지만 펜윅트리를 활용하게 되면 나무당 쿼리를 $O(logN)$으로 줄일 수 있습니다. 지금까지 심은 나무들은 총 두가지로 나눌 수 있습니다. 현재나무보다 왼쪽에 있는 나무들과 오른쪽에 있는 나무들 입니다. 각각의 정보를 구하기 위해서 필요..

문제 https://www.acmicpc.net/problem/3006 알고리즘 세그먼트트리 풀이 터보소트라는 방법으로 소팅을 할 때, 필요로 하는 교환 횟수를 묻고 있습니다. 일반적인 inversion counting문제는 작은 수부터 inversion들을 세어나가는 문제입니다. 하지만 이 문제에서는 첫 번째로 작은 수, 첫번째로 큰 수, 두 번째로 작은 수, 두번째로 큰 수 와 같이 inversion을 세어나갑니다. 다른 여러 문제들에서도 설명드렸지만, 일반적인 방법으로는 $O(N^2)$의 시간 복잡도가 필요하지만 세그먼트 트리를 이용하게 되면 자신보다 앞에 있는 수, 자신보다 뒤에 있는 수들을 한 임의의 수당 $O(logN)$의 시간 복잡도로 해결 가능합니다. 펜윅트리에는 쿼리를 진행해야 할 인덱스..

문제 https://www.acmicpc.net/problem/1615 알고리즘 세그먼트 트리 풀이 간선들이 주어질 때, 교차점의 개수를 묻고 있습니다. 교차 조건은 두 개의 에지를 (A1, B1), (A2, B2)라 한다면 A1 B2 또는 A1> A2, B1 M; while(M--) { cin >> a >> b; edge.emplace_back(a, b); } sort(edge.begin(), edge.end()); for (auto [A, B] : edge) { ans += query(N) - query(B); update(B,1); } cout

문제 https://www.acmicpc.net/problem/1777 알고리즘 세그먼트 트리 풀이 Inversion counting 문제입니다. 각 숫자의 inversion의 개수가 주어졌을 때, 원래 순열을 구하는 문제입니다. 예제 입력에서 주어지는 inversion의 개수를 풀어서 설명하자면, 나보다 작은 숫자가 뒤에 몇 개나 있느냐를 의미합니다. 순열의 총 크기를 안다면, 나보다 작은 숫자가 앞에 몇 개가 있는지 또한 구할 수 있습니다. 이는 $k$번째가 어디에 위치한 지를 묻는 쿼리와 동등합니다. 이때 여러전략을 선택할 수 있지만, 숫자를 올바른 곳에 배치했다면 해당 인덱스를 제외해야 하므로 삭제 연산 또한 가능한 펜윅트리를 사용했습니다. 시간 복잡도는 $O(NlogN*logN)$입니다. 코드 ..

문제 https://www.acmicpc.net/problem/9426 알고리즘 세그먼트 트리 풀이 $N$초동안 온도를 기록하는데 최근 $K$초의 중앙값들을 모두 더하는 것을 요구하는 문제입니다. 이 문제의 경우는 이전의 값을 삭제하는 연산 없이 계속 추가한 후 중앙값만 처리하면 되므로 최대 힙, 최소 힙 두 개로 $O(NlogN)$에 해결 가능했으나, 가장 최근$K$초의 중앙값만을 계속 구해야 하므로 최근 K초를 제외한 온도를 삭제할 수 있는 자료구조인 세그먼트 트리를 활용하겠습니다. 문제에서 요구하는 핵심쿼리는 중앙값 처리입니다. 트리에서의 인덱스는 온도를 의미합니다. 온도의 개수를 누적시킨다면, 인덱스에 따라 값들이 오름차순으로 정렬되어 있으므로, 이분 탐색을 통해 중앙값을 빠르게 처리할 수 있습니..