CP Algorithm & Knowledge (30) 썸네일형 리스트형 타일 채우기 문제를 푸는 테크닉 1 이 게시글에서는 타일을 채우는 것과 관련한 문제에서 특수한 경우에 사용하는 기술을 알아본다. N * M 크기 격자의 상태를 정수 한 개로 표현하기 https://atcoder.jp/contests/abc196/tasks/abc196_d D - Hanjo AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 길이가 1, 2인 블럭으로 H * W 크기의 격자를 채우는 가짓수를 출력하는 문제이다. 이 문제는 $HW \leq 16$이라는 조건과 이러한 타일링 문제에 적용되는 성질로 인해 재미있는 생각을 떠올릴 수 있다. 1. 어떤 행.. 머지 소트 트리 Merge Sort Tree 머지 소트 트리는 세그먼트 트리의 파생형으로 위 그림처럼 각 node가 정렬된 구간을 보유하는 형태로 되어있다. 머지 소트 트리는 세그먼트 트리와 유사하게 구현할 수 있다. 초기화 void set_mst(int node, int start, int end) { vector &cur = mst[node]; if (start == end) { cur.push_back(ar[start]); return; } int m = mid(start, end); set_mst(node * 2, start, m); set_mst(node * 2 + 1, m + 1, end); vector &l = mst[node * 2], &r = mst[node * 2 + 1]; cur.resize(l.size() + r.size()).. 세그먼트 트리로 k번째 작은 수 찾기 이 게시글에서는 길이 N의 수열에서 k번째로 작은 수를 세그먼트 트리로 구할 것이다. 질의당 $O(\log N)$의 시간복잡도가 요구된다. 세그먼트 트리를 구성할 때 배열의 원소값을 index로 하여 해당하는 수가 몇 개 존재하는지 저장한다. 그러면 update 연산은 구간합을 구하는 일반적인 세그먼트 트리의 그것과 동일한 구현을 쓸 수 있다. k번째로 작은 수를 찾는 연산을 할 경우는 k를 매개변수로 전달해줘야 한다. 전달받은 k를 가지고 두 개의 분기로 가지치기를 할 수 있다. 1. 왼쪽 구간에 존재하는 원소의 개수가 k보다 크거나 같으면 왼쪽 구간으로 탐색을 한다. 2. 1에 해당하지 않으면 오른쪽 구간으로 탐색한다. 2번에서 오른쪽 구간으로 가지치기를 하게 되면 왼쪽 구간의 원소들을 배제하게 된다.. 좌표 압축 - 원소의 밀도를 높이자 스위핑이나 탐색을 하면서 어떤 범위를 전부 확인해야 한다고 해보자. 그런데 그 범위가 -100억 ~ 100억 이라면? 단순 선형 탐색도 시간 초과를 피하기 어려울 것이다. 다만 범위에 속한 원소의 개수가 충분히 작다면 각 원소의 좌표들을 원소의 개수만큼의 범위로 압축한다면 빠르게 탐색을 할 수 있다. 이렇게 좌표의 범위를 압축하여 원소 집합의 밀도를 높이는 기법을 좌표 압축이라고 부른다. 이 게시글에서는 C++의 STL로 간단하게 압축하는 방법을 알아본다. 방법은 아주 간단하다. 원소를 벡터로 모두 수집한 다음 std::erase와 std::unique를 이용하여 중복 원소를 모두 제거하면 index와 원소가 일대일 대응하게 되어 좌표 압축을 할 수 있다. std::unique를 사용하기 위해 벡터는 정.. Inversion Counting을 펜윅 트리(BIT)로 풀기 정렬되지 않은 배열을 스왑 기반 정렬(버블, 선택, 삽입 등)로 정렬할 때, 총 스왑 횟수를 구하라. 이 문제는 Inversion Counting 또는 Inversion Index로 불리는 유명한 문제다. (인터넷에서는 Inversion Counting이라는 용어가 더 알려져 있으므로 게시글에서는 Inversion Counting이라 부른다.) 이 게시글에서는 Inversion Counting을 펜윅 트리(Binary Indexed Tree)로 푸는 방법을 소개한다. 어떻게 푸는가? 우리는 배열 A의 i번째 원소 A[i] 뒤에 A[i]보다 작은 원소가 몇 개 존재하는지 펜윅 트리로 저장할 것이다. 그 값을 val이라고 했을 때 i번째 인덱스 뒤에 A[i]보다 작은 원소가 없게 하기 위해 val번 만큼 s.. 이전 1 2 3 4 5 6 다음
