알고리즘 공부방

1. 문제에서 구하고 싶은 구조 (트리에서의 경로 / 트리에서의 연속 컴포넌트)를 루트를 정해놓고, 그 루트를 지나는 것들만 고려했을 때 쉽게 풀 수 있다면 Centroid Decomposition을 이용하여 전체 문제를 해결할 수 있다. 만약 트리에서의 루트가 고정되어 있고, 루트를 지나는 구조들에 대해서는 쉽게 풀 수 있다면, 이제 그 루트를 지나지 않는 경우에 대해서는 Centroid Decomposition의 분할정복 과정에서 다음으로 탐색할 것이다. 이와 같이 생각하면 장점이, 루트를 지나는 경로 / 컴포넌트 등은 각 서브트리에서 문제를 독립적으로 해결할 수 있으니, 가능한 모든 정점쌍 / 집합쌍을 고려하는 대신, 한 서브트리의 정점들을 자료구조 안에 삽입한 후 다른 정점들을 빠르게 찾을 수도 ..

문제 oj.uz/problem/view/JOI18_bitaro 문제 보기 - Bitaro’s Party (JOI18_bitaro) :: oj.uz 문제 보기 - Bitaro’s Party (JOI18_bitaro) oj.uz 정점 개수 N, 간선 개수 M개의 DAG가 주어진다. 이 때, 다음과 같은 쿼리에 답해야 한다. 정점 v로 오는 경로들 중, 시작점이 u1, u2, ..., uk 중 하나인 경로들을 제외했을 때 최장경로의 길이룰 구하라. $N

문제 oj.uz/problem/view/JOI20_building4 문제 보기 - 건물 4 (JOI20_building4) :: oj.uz 문제 보기 - 건물 4 (JOI20_building4) oj.uz 길이 2N의 배열 A와 B가 주어진다. 각 i에 대해, A, B중 정확히 하나씩 골라 만든 길이 2N짜리 수열이 증가 수열이어야 한다. 또한, A를 정확히 N개, B를 정확히 N개 골라야 한다. 이와 같이 고르는 것이 가능한지, 가능하다면 그 예를 하나 보여야 한다. $N

문제 oj.uz/problem/view/APIO19_strange_device 문제 보기 - 이상한 기계 (APIO19_strange_device) :: oj.uz 문제 보기 - 이상한 기계 (APIO19_strange_device) oj.uz parameter t에 대해, 순서쌍 (x, y)는 다음과 같이 정의된다. $x=(t+[\frac{t}{B}]) mod A$ $y=t mod B$ 이 때, t의 disjoint한 구간 n개가 주어지고, 모든 구간의 합집합의 t에 대해, 서로 다른 (x, y)의 개수를 세야 한다. $A, Bfirst; } printf("%lld\n", ans); }

문제 oj.uz/problem/view/APIO20_swap 문제 보기 - 자매 도시 (APIO20_swap) :: oj.uz 설명 인도네시아에는 $N$ 개의 도시가 있고, $0$부터 $N - 1$까지 번호가 매겨져 있다. 또 $M$ 개의 양방향 도로가 있는데, $0$ 부터 $M - 1$까지 번호가 매겨져 있다. 각 도로는 두 개의 서로 다른 도시 oj.uz 정점 개수 N, 간선 개수 M개의 연결 무방향 그래프가 주어질 때, 쿼리로 두 정점 X, Y가 주어진다. 이 때, 한 명은 X에서 Y로, 한 명은 Y에서 X로 이동한다. 이때 두 명이 만나서는 안되고, 한 간선을 가다가 중간에 돌아가는 등의 일은 할 수 없다. 이 때 두 사람이 이용하는 간선들의 가중치의 최댓값을 최소화한 값을 출력하자. $N=0; ..

문제 oj.uz/problem/view/APIO20_paint 문제 보기 - 벽 칠하기 (APIO20_paint) :: oj.uz 설명 성렬이는 자기가 사는 집의 벽을 칠한지 한참 되었기 때문에 다시 칠하려고 한다. 벽은 $N$개의 구간으로 되어 있는데, $0$부터 $N - 1$까지 번호가 매겨져 있다. 이 문제에서, $K$ 가지 다른 oj.uz 길이 N의 배열을 각 칸을 $C_i$의 색으로 칠하려고 한다. 색의 종류는 K개, M명의 일꾼이 있으며, 각 일꾼마다 좋아하는 색의 목록이 있다. 색을 칠할 수 있는 방법은, 길이 M의 연속된 구간과 구간의 첫 시작점을 칠할 일꾼을 한 명 골라, i번째 칸은 (i+S) mod M번 일꾼이 칠하도록 하는 것이다. 이때 색칠해야 하는 칸의 색을 그 일꾼이 좋아해야 ..

www.acmicpc.net/problem/10806 10806번: 공중도시 첫 줄에는 도시의 개수 N과 다리의 개수 M이 주어진다. 두 값의 범위는 3 ≤ N ≤ 100,000, N-1 ≤ M ≤ 200,000이다. 그 다음 M개의 줄에 걸쳐 각 줄에는 다리로 직접 연결된 두 도시 C1과 C2가 차례대로 주 www.acmicpc.net 간단한 BCC 문제. Edge-disjoint BCC로 주어진 그래프를 쪼갠 후, JOISC Mergers와 같은 트리를 덮기 위한 경로의 최소 갯수는 ceil(리프/2)이고, 오일러 순으로 정렬한 후 첫번째 값과 가운데 값을 하나씩 차례로 연결해 주면 된다. 중복 간선이 있다는 점에서 단절선 처리에 주의하자. www.acmicpc.net/problem/19297 192..

2학년 2학기 기말고사가 거의 끝났고, 드디어 2021년 선발고사가 코앞으로 다가오고 있는 만큼, 체계적으로 계획을 세우고 정보 공부를 해보려 한다. 코로나 사태 덕분에(?) 온라인 수업이고 집에서 컴퓨터를 잡고 있을 시간이 그만큼 더 많이 생겼으니까 마지막 기회라 생각하고 열심히 공부를 해보자. 1. 백준 문제 4문제 셋 2. Atcoder AGC 3. Codeforces 대회 있을 때마다 참가 4. 지금까지 공부한 모든 알고리즘을 자유롭게 구현할 수 있도록 한번씩 연습 5. 백준의 알고리즘 태그 골라서 높은 난이도 (다4 ~ )의 문제들 꾸준히 풀기 비재귀 세그먼트 트리 기본적인 플로우(포드 폴커슨, 에드먼드 카프, MCMF)