devmoon

Heavy Light Decomposition, 줄여서 HLD라고 불리는 알고리즘은 하나의 트리를 여러 개의 서브 트리로 분할하는 방법이다. 이름에 나와있듯이 트리를 무거운(Heavy) 서브트리와 가벼운(Light) 서브 트리로 분할하게 된다. 일반적으로 이 알고리즘은 세그먼트 트리를 트리위에서 적용하기 위해 사용한다. 예를 들자면, 트리위의 어떤 두 정점 $u$와 $v$가 주어졌을 때, 두 정점을 잇는 경로 길이의 합이나 경로 사이에 존재하는 가중치의 최솟값을 여러 번 구하는 문제이다. 가장 먼저 1차원 배열 위에서의 세그먼트 트리의 적용이 아닌 트리 위에서의 세그먼트 트리 적용이기 때문에 어떤식으로 정점들을 구성해서 세그먼트 트리를 사용할 수 있도록 변형할지 생각해봐야 한다. 이를 위해 아래와 같이 ..

1. 문제 출처 https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 2. 문제 접근 특정 구간내에 그래프가 연결되어 있는지의 정보를 O(log N)의 시간만에 알아내기 위해 세그먼트 트리 자료구조를 사용해야 했다. 하지만, 트리 구조이기 때문에 트리구조를 체인으로 분할 하는 heavy-light-decomposition 을 적용하여 문제를 해결해야 한다. 먼저 트리의 루트는 항상 1이라고 고정된 상태이기 때문에, 1을 루트로..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 1이상 4,000,000 이하의 수 $N$ 개를 입력받고 $K$개의 임의의 수 $k$를 입력 받았을 때, $N$ 개의 수에서 $k$ 보다 큰 수들 중 가장 작은 수를 출력하면 되는 문제이다. 따라서 입력받는 대로 모든 수를 정렬하고, upper_bound 로 만족하는 결과를 얻을 수 있는 set 의 자료 구조의 사용을 바로 떠올렸다. set s..

1. 문제 출처 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2. 문제 접근 https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exac..

1. 문제 출처 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 문제 접근 기존에 알고 있었던 세그먼트 트리이지만, 업데이트해야 하는 것이 하나의 값이 아니라 구간에 대해서 업데이트를 진행해야 했다. 해당 구간에 대해서 일일이 업데이를 진행하는 것보다 lazy propataion방법을 사용하면 더 효율적으로 풀이가 가능했다. lazy propagation에 대한 정보가 없었..

※ 이 게시물은 에 나오는 KMP부분을 읽고 개인이 정리하는 글입니다. 더 자세한 설명은 위의 책에 나와있습니다. KMP알고리즘은 아주 긴 문자열 $S_{1}$과 $S_{2}$가 주어졌을 때, $S_{1}$속에 $S_{2}$가 몇 번이나 등장하는지 빠르게 알아낼 수 있는 알고리즘이다. 두 문자열을 비교할 때, 가장 쉬운 방법은 $S_{1}$의 모든 index를 순회하면서, $S_{2}$의 길이만큼 서로 문자 같은지 비교를 진행하는 것이다. 하지만 이럴 경우 총 ($S_{1}.length-S_{2}.length + 1) \times S_{2}.length$만큼 비교를 진행해야 한다. 하지만, 구현이 단순하다는 장점이 존재한다. 이 장점 때문에 C에서는 strstr(), C++에서 string:find(),..

1. 문제 출처 https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 2. 문제 접근 $N$이 주어졌을 때, 100 자릿수 이하인 $N$의 배수를 구하는 데에는 시간도 매우 많이 걸리고, 해당 수를 담을 자료형도 long long으로 부족하기 때문에 string연산으로 해결을 해줘야 한다. 따라서 반대로, 1과 0으로 이루어진 수들을 작은 자리 수부터 생성을 하고, 그 수가 $N$의 배수인지 ($N$)으로 나눈 나머지가 0인지) 확인만 해주면 되었다. 1과 0으로 이루어진 100자리의 수 역시 매우 큰 수 이므..

1. 문제 출처 https://www.acmicpc.net/problem/11402 11402번: 이항 계수 4 첫째 줄에 $N$, $K$와 $M$이 주어진다. (1 ≤ $N$ ≤ 1018, 0 ≤ $K$ ≤ $N$, 2 ≤ $M$ ≤ 2,000, M은 소수) www.acmicpc.net 2. 문제 접근 $10^{18}$ 이하의 자연수 $n$과 $n$ 이하의 음이 아닌 정수 $k$가 주어졌을 때, $_nC_k$의 값을 구하는 문제이다. $_nC_k$ 의 값이 매우 커질 수 있으므로, 2000 이하의 임의의 소수 $m$이 주어지고 $_nC_k$의 값을 $m$으로 나눈 나머지를 출력하면 된다. 이 문제를 해결하기 위해서는 뤼카의 정리에 대해서 알아야 한다. 뤼카의 정리는 $_nC_k..