이 글에서는 구간 트리(segment tree), 펜윅 트리(fenwick tree), 느리게 갱신되는 구간 트리(segment tree with lazy propagation)들이 성립하는 조건을 알아볼 것이다. 다만, 이 글에는 한계가 존재한다. 구간 트리를 하나의 Black-Box(기능은 알지만 작동 원리를 이해할 수 없는 복잡한 기계 장치나 시스템, 물체)로 바라보기 때문에 직사각형들의 합집합의 넓이를 구하는 문제와 같이 구간 트리의 구조를 변형시키는 문제에는 이 글의 내용이 적용이 되지 않을 수 있다. 기본 질의응답의 대상인 배열은 $[a_1,a_2,\ldots,a_n]$이다. 배열 속 원소들을 포함하는 집합 $S$, 원소들 간의 이항 연산 $*$, 갱신 함수의 집합 $F$가 있다. 이때, 당연..

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 선발고사 문제 치고는 꽤 쉽다. 하지만 구현이 만만치 않다... 예제 속 그림을 보면 중요한 관찰이 눈에 쉽게 보인다. 바로 두 경로는 수직 구간 혹은 수평 구간을 정확히 하나 공유한다는 것이다. 이를 바탕으로 수평에 대해서 한 번 풀어주고, 수직에 대해서 같은 방식으로 한 번 풀어준다고 생각하고 한쪽만 고려해보자. 수직 구간을 공유한다면 수직 구간의 양 끝점을 기준으로 경로가 정확히 나뉜다. 이를 구간합 배열을 잘 이용하여 합쳐주면 된다. 솔직히 좋은 문제는 아니라고 생각한다... #include #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define siz(x) int((x).si..

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 한 자릿수 서브태스크 배점들을 보고 왜 이렇게 짜게 주나 했는데, 하나씩 풀다 보니까 기가 막힌 점수 배분인 것 같다. 부분 문제 1 ~ 4 풀이는 노드의 번호를 1-base 기준으로 작성했고, 부분 문제 5 풀이는 0-base 기준으로 작성했습니다. 궁금하신 점은 댓글로 남겨주시면 답변해 드리겠습니다! 문제 요약 "모든 $[i,j]$꼴의 정점 집합에 대해 만들어진 각 virtual tree의 가중치의 합을 구하라." 정도이다. 부분 문제 1 (5점) $N\le 300$이다. $O(N^3)$이 넉넉하게 돌아갈 수준이다. 모든 $[i,j]$를 직접 돌면서 dfs를 돌리면 된다. 웬만해서는 코드를 짜보려고 했는데, 점수 대비 구현량의 가성..

이 블로그의 "그래프에 관하여" 시리즈의 첫 번째 카테고리, ❮DFS 트리❯의 개요이다. DFS 트리는 DFS를 응용한 다양한 알고리즘들을 이해하기 위한 좋은 표현법이자 도구이다. 조금 어려운 감이 있지만 꼼꼼히 이해한다면 큰 도움이 될 것이라고 생각한다. DFS 트리/포레스트란? 어떤 연결 그래프에서 DFS 순회하는 과정을 그렸을 때 나타나는 유향 신장 트리(directed spanning tree)를 DFS 트리라고 한다. 당연히 여러 개가 존재할 수 있다. 연결 그래프가 아닐 경우에는 각 연결 컴포넌트마다 DFS 트리를 만들 수 있으니 DFS 포레스트로 확장해서 생각할 수 있다. 유향 그래프일 경우, DFS 트리의 간선들을 네 가지로 분류할 수 있다. 트리 간선(tree edge): DFS 트리에 ..

이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다. 이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다. Square-order tree DP? 사실 이건 그 자체로 뭔가 해야 하는 테크닉은 아니다. 트리 DP 점화식이 2차원으로 나오고, 전이 과정을 합쳐서 대충 보기에는 $O(n^3)$의 시간 복잡도를 가져야 할 것으로 보이는 후술 할 조건을 만족하는 알고리즘이 사실 $O(n^2)$이라는 더 좋은 시간 복잡도를 갖는다는 사실을 이용하는 테크닉이다. 만족해야 하는 조건은 구한 점화식 $\text{dp}(x,y)$에 대해, $x$가 각 노드를 뜻하..

https://youtu.be/S2N8VTdL0og 환경 운영체제: Mac OS 사용 에디터: Visual Studio Code 터미널: zshrc 동기 tasks.json을 편집하는 것이 개인적으로 어렵다고 느껴짐... 간단한 터미널 명령어들을 이용해 손쉽게 컴파일/실행/테스트 해보자! 사용한 터미널 명령어 compile(){ g++-12 -Wall -O2 -std=c++17 -o base cpp/base.cpp cpp/grader.cpp } g++-12: 컴파일러 종류 -Wall: 컴파일 경고 옵션 -O2: 최적화 옵션 -std=c++17: 사용 언어 -o base: 실행 파일을 base라는 이름으로 설정 cpp/base.cpp cpp/grader.cpp: 컴파일에 사용되는 파일들 run(){ com..

이 블로그의 "그래프에 관하여" 시리즈의 첫 번째 카테고리, ❮DFS 트리❯에서 다루는 첫 번째 주제이다. 편의를 위해 다음 표현을 정의하자. 정점 $v$의 방문 시작 시각: $s(v)$ 정점 $v$의 방문 종료 시각: $f(v)$ SCC란? 어떤 방향 그래프가 모든 정점에 대해, 다른 모든 정점으로 갈 수 있다면 강하게 결합(strongly connected)되었다고 한다. 모든 방향 그래프는 SCC(strongly connected component; 강결합 컴포넌트)로 나눌 수 있다. SCC란 모든 정점에서 다른 모든 정점으로 갈 수 있는 최대 크기의 정점 집합을 의미한다. 각 SCC를 새로운 정점으로 하고, 그 안의 모든 정점들에서 나가는 간선을 새로운 정점의 간선으로 갖게 하여 컴포넌트 그래프(..

배열과 gcd 문제 링크 난이도가 P3보다 높아져야 하는 문제라고 생각한다. 풀이 더보기 $\mathrm{let\ }b_i=C_{i-1},\ G_i=C_i,\ b_i=B_i\times G_i.$ $\mathrm{let\ }x_i=X_i\times G_i.$ 만약 $G_i\nmid b_i$였다면 $0$을 출력하고 프로그램을 종료한다. 그러면 문제는 각 $i(\ge 2)$에 대해 $\left [1,\lfloor \frac {num} {G_i}\rfloor \right ]$ 속의 $B_i$와 서로소인 $X_i$의 개수를 구해서 전부 곱하는 문제로 바뀐다. (가능한 모든 $X_i$에 대해 $x_i$는 $a_i$로 가능한 모든 값들이다.) euler totient 함수를 변형해보겠다는 생각도 해볼 수 있지만 힘들..

링크 Cow Curling FJ의 농장에서 컬링 대회가 열렸다. 이 컬링 대회의 규칙은 일반 대회와는 조금 다르다. 겨루는 두 팀에게는 각각 $N$개의 돌이 주어진다. 만약, 한 팀의 세 개의 돌이 이루는 삼각형 내부에 상대 팀의 돌이 들어있다면, 이 돌은 포획되었다고 한다. (선분 위에 올라간 경우도 포함한다.) 각 팀의 점수는 상대 팀의 포획된 돌의 수로 계산된다. 두 팀의 돌의 배치가 2차원 평면 상의 좌표로 주어질 때, 각 팀의 점수를 계산하여라. 풀이 더보기 아이디어는 굉장히 쉽다. 그냥 각 팀의 convex hull을 각각 만들고, 상대 팀의 돌이 몇 개 들어가는지를 계산하면 된다. 이때, 볼록다각형의 내/외부점 판별 알고리즘을 이용하면 된다. 이 문제의 경우, 각 점에 대해서 따로따로 판별할..