알고리즘 공부방

문제 https://oj.uz/problem/view/JOI19_ho_t5 문제 보기 - Unique Cities (JOI19_ho_t5) :: oj.uz 문제 보기 - Unique Cities (JOI19_ho_t5) oj.uz 트리가 주어지고, 각 정점에 색이 칠해져 있을 때, 정점 $x$에 대한 unique한 정점 $y$를 다음과 같이 정의한다. $x$와 $y$의 거리가 $d$일 때 $x$에서 거리가 $d$인 $y$가 아닌 다른 정점 $z$가 존재하지 않는다. 각 정점에 대해, unique한 정점들의 서로 다른 색들의 개수를 구해야 한다. $M=dep-H[now]) cnt[V.back().second]--, V.pop_back(); if(chk[now]) ans[now]=V.size(); } els..

문제 https://oj.uz/problem/view/IOI19_split 문제 보기 - Split the Attractions (IOI19_split) :: oj.uz 문제 보기 - Split the Attractions (IOI19_split) oj.uz 연결된 무방향 그래프가 하나 주어졌을 때 정점들을 $A$, $B$, $C$ 세 개의 집합으로 분리해야 한다. 조건은 $A$, $B$, $C$의 각 집합의 크기는 이미 정해져 있고, 세 집합들 중 적어도 두개는 하나의 커넥티드 컴포넌트를 이루어야 한다. ($N

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..

SCC란, 방향 그래프에서 정의되는 개념으로, 한 SCC 내부에서 임의의 정점 u, v를 잡았을 때, u에서 v가 도달 가능한 컴포넌트를 의미한다. 한 그래프에는 여러개의 SCC가 존재할 수 있고, 이러한 SCC들을 분리해 내고 그 SCC들을 하나의 정점처럼 합쳐 주면 압축된 새로운 그래프를 얻을 수 있다. 이 그래프는 무조건 DAG 이고, 이를 이용하여 많은 문제들을 풀수 있다. ( 압축된 정점 들 간의 사이클이 존재하면 임의의 한 압축정점에서 다른 정점으로 양방향경로가 존재하니, 그 압축정점들 또한 하나의 SCC로 뭉쳐져야 한다. ) SCC는 $O(N+M)$ 안에 추출할 수 있고, Tarjan과 Kosaraju 두 방법이 있다. 1. Tarjan's Algorithm 타잔의 알고리즘은 기본적으로 그래..

위상정렬은 주어진 유향 그래프를 일정한 순서로 배치하였을때, 모든 간선이 오른쪽으로만 향하도록 하는 배치를 의미한다. 위상정렬을 하기 위해선 주어진 그래프에 사이클이 없음, 즉 DAG 여야 함이 보장되어야 한다. 위상정렬을 하는 방법은 크게 2가지 방법이 있다. SOL 1) 위상정렬에서 가장 먼저 오는 점은 indegree의 값이 무조건 0이라는 관찰을 해주면 된다. 각 정점에서의 indegree 값을 갖고 있고, indegree가 0인 정점을 큐에 넣어준 후, 그 정점과 연결된 간선들을 삭제해주는 과정을 반복하면 된다. 간선을 삭제하는 방법은 단순히 도착 정점의 indegree 를 감소시키면 된다. 만약 큐에 값이 2개 이상 들어가는 시간이 있으면, 위상정렬의 결과가 2개이상 가능한 것이고, 큐에 값이..

DFS를 돌면서 그래프의 간선을 4개의 종류로 분류할 수 있다. 1. 트리 간선 (Tree Edge) 트리 간선은, dfs 스패닝 트리 자체에 포함되는 간선을 의미한다. 간선의 확인은 u->v 에서 v가 아직 발견되지 않았다면 이 간선은 트리 간선에 포함된다. 2. 역방향 간선 (Back Edge) dfs 스패닝 트리에서 이미 자손에서 조상으로 향하는 간선을 의미한다. 위 그림에서 자손 D에서 조상 A로 향하는 간선을 보면, 아직 A를 종료하지 않은 상태에서 D가 A로 가려고 한다. 간선의 확인은 u->v 에서 v가 아직 종료되지 않았으면 이 간선은 역방향 간선에 포함된다. 역방향 간선의 존재는 사이클의 존재와 동치이다. 3. 순방향 간선 (Forward Edge) dfs 스패닝 트리에서 조상에서 자손으..

트리에서의 지름이란, 트리에서 가장 멀리 떨어진 두 점 사이의 거리를 구하는 문제이다. 2가지 솔루션이 있고, 2개 모두 알아두도록 하자. SOL 1) 전체적인 알고리즘은, 1. 임의의 한 점으로부터 제일 멀리 떨어진 점을 잡고, (A) 2. 그 점으로부터 제일 멀리 떨어진 점을 잡는다. (B) 이때 A, B는 지름을 구성하는 요소이다. => dfs 2번으로 답을 구한다. 더보기 만약 A가 지름을 구성하는 두 점중 하나가 맞다면 2는 자명하다. 따라서 A가 지름을 구성하는 점임을 보여 보자. (귀류법) 임의의 정점에서 제일 멀리 떨어진 점 X를 잡았는데, 그 점이 지름 A, B 모두 아니라 하자. 위 그림에서 루트 R과 제일 멀리 떨어진 점 X를 골랐다 하자. (X!=A, X!=B) 1. 지름이 루트를 ..