devmoon

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

※ 이 게시물은 에 나오는 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(),..

선분 교차 판단 알고리즘은 2차원 평면 위에서 두 선분이 주어졌을 때, 두 선분이 서로 교차하는지 교차하지 않는지 판단하는 알고리즘이다. 이 알고리즘을 학습하기 위해서 선행되어야 하는 기하 알고리즘이 있는데, 그 개념은 CCW이다. CCW (Counter Clock Wise)는 2차원 평면 위에 놓인 3개의 점에 대해서 어떤 방향성이 있는지 알려주며 이 방향성 정보를 사용해 선분이 서로 교차하는지 판단하게 된다. CCW 먼저 3개의 점으로 나타낼 수 있는 방향성의 종류에는 무엇이 있는지 알아봐야 한다. 3개의 점을 임의의 순서대로 이어서 나온 방향성은 아래와 같이 1) 시계 방향 2) 반시계 방향 3) 일직선 3종류가 있을 수 있다. 그러면 이제 3개의 각 점에 대한 좌표정보가 주어지면 그 방향성을 어떻..

1. 관련 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 2. Meet in the middle 최대 길이 40의 수열이 주어졌을 때, 이 수열의 원소들 중 몇 개를 중복되지 않게 선택하여 모두 더한 값이 S가 되도록 하는 경우의 수가 몇 개나 있는지 찾는 문제이다. 시간, 공간 복잡도를 생각하지 않고 간단하게 접근했을 때, 모든 원소들을 순회하면서 [포함 / 미포함]으로 둘 수 있기 때문에 최대 ..