알고리즘 공부방

문제 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)

www.secmem.org/blog/2019/10/19/handy-function-about-bit/ 1. 비트마스크 S의 가장 마지막 켜져있는 비트 (LSB) 펜윅 트리에 구현에 자주 이용되는 테크닉이다. int lsb=mask&-mask; 2. 비트마스크 S의 부분집합(submask) 모두 순회 $O(2^N)$에 현재 주어진 비트마스크의 모든 부분집합들을 정확히 한번씩만 순회할 수 있다. for(int i=mask; ; i=mask&(i-1)) { if(i==0) break; } 3. 모든 가능한 비트마스크 S에 대해, S의 부분집합(submask) 모두 순회 모든 $O(2^N)$개의 비트마스크를 모두 순회하며, 각 비트마스크에 대해 부분집합을 모두 순회하는데 드는 시간은 $O(3^N)$이다. S에 ..

1. 로그 자료구조의 속도 비교 BIT (Fenwick Tree) < PQ < Set / Map (STL BBST) < Segment Tree < Lazy Segment Tree < Persistent Segment Tree 단, Set/Map은 삽입되는 자료의 양이 커질 때 급격히 느려진다. 2. Locality 다차원 배열의 인덱싱 순서는 반복문 순회 순서와 같게 하는 것이 제일 빠르다. 실제로 실행 시간의 대부분을 차지하는 것은 덧셈, 곱셈 등의 연산이 아니라, 메모리에 접근하고 값을 저장하는 연산이다. 메모리 접근 연산을 할 때에는 최대한 접근하는 위치들이 서로 인접해 있는 것이 좋다. stackoverflow.com/questions/16699247/what-is-a-cache-friendly-..

문제 oj.uz/problem/view/JOI17_sparklers 문제 보기 - Sparklers (JOI17_sparklers) :: oj.uz 문제 보기 - Sparklers (JOI17_sparklers) oj.uz 수직선 위에 N명의 사람들이 폭죽을 하나씩 들고 서 있다. 처음에는 K번째 사람의 폭죽에만 불이 붙어 있으며, 폭죽에 불이 처음 붙은 후로부터 T초 동안만 불꽃이 유지된다. 불꽃이 꺼지기 전에 어떤 다른 사람과 같은 위치에 있게 되면 그 사람에게 불꽃을 옮길 수 있다. 또한, 각 사람이 1초동안 움직일 수 있는 최대 거리인 속도 X가 정해져 있을 때, 모든 사람의 폭죽에 불이 한번씩 붙을 수 있기 위한 최소의 정수 속도 X를 구해야 한다. $N$[1, N]$은$[K, K]$ -> ..

많은 Tree DP 문제들의 경우, 각 노드에서 특정 시간 복잡도로 노드들을 합치는 작업을 한다. 일반성을 잃지 않고, 노드의 자식이 3개 이상이라면, 더미 노드를 부모 쪽으로 계속 만들어 주며, 모든 트리를 이진 트리 형태로 변형시킬 수 있다. 따라서, 이진 트리에서 자식 노드 두개의 값만을 합쳐주는 문제로 생각한다. 1. $A$, $B$를 합치기 위해서 $sz(A) \cdot sz(B)$의 시간이 필요할 때, 전체 시간복잡도 $O(N^2)$에 합칠 수 있다. (KOI18 검은 돌) $sz(A) \cdot sz(B)$의 값은 왼쪽 자식의 서브트리의 모든 노드와 오른쪽 자식의 모든 서브트리의 노드를 연결했을 때 간선의 수와 같다. 이 때 어떠한 두 정점 $u$, $v$가 합쳐지는 위치는 바로 그 노드의 ..