[백준 26113] Two Choreographies

1. 문제 요약 \(N\)개의 정점과 \(2N-3\)개의 간선이 주어진다. 길이가 같고 길이가 \(3\)이상인 사이클을 \(2\)개 찾아서 출력한다. 2. 풀이 BFS를 통해 트리를 만들어 보자. 그렇다면 \(2N-3\)개의 간선 중, \(N-1\)개는 트리에 포함된 간선이고, 나머지 \(N-2\)개는 포함되지 않는 간선이다. 트리에 포함되지 않는 간선들의 집합을 \(S\)라고 하자. \(S\)에 속한 간선 \(u, v\)를 생각해보자. 정점 \(u, v\)에 대해 트리 위의 단순 경로를 찾아보자. \(S\)에 포함되지 않는 간선으로 이루어진 \(u\) \(v\)를 잇는 경로가 존재할 것이다. 또한 \(S\)에 속한 간선은 \(u - v\)가 직접적으로 연결되어 있으므로 간선 \(u - v\)를 포함하는..

→2022.11.22

[백준 5979] 납땜하기

1. \(O(N^2)\) 풀이 먼저 \(O(N^2)\) 풀이를 생각해보자. \(dp[u][k]\) = 정점 \(u\)의 \(k\)번째 자식을 제외하고, 나머지 자식들이 새로운 전선을 시작하여 합한 최솟값이라고 정의해보자. \(dp[u][-1]\)은 어떤 자식도 제외하지 않은 값이다. 어떤 정점 \(u\)에서 시작해서 \(v\)에서 전선이 끝날 수 있는 조건은 \(v\)의 자식이 존재하지 않거나 (case 1), \(v\)의 자식 \(2\)개를 선택하여 전선 사이에서 끝나는 것 (case 2)이다. 아래 그림은 각 케이스를 나타내고 있다. \(u\)는 \(u\)의 서브트리에서 어떤 한 자식을 골라 쭉 전선을 만들어 가야하고, 전선중 한 자식을 선택한 번호를 \(k\)라고 할 때, \(dp[u][k]\)를 ..

→2022.09.22

[백준 25491] Mexor tree

1. 풀이 먼저 쿼리를 처리하는 방법을 생각해보자. 만약 온라인이였다면 HLD를 만들고 lazy xor seg를 통해 \(O(log^2N)\)에 쉽게 처리할 수 있다. 이 문제에서는 쿼리가 한번에 들어오므로 다른 효율적인 방법을 생각해보자. \(u, v\)에 대한 단순 경로는, \(t = LCA(u, v)\)라고 정의할 때, \(u - t - v\)의 직선 경로 \(2\)개로 생각할 수 있다. 그러므로 트리에서 구간합을 생성하는 것과 비슷하게 해주면 빠르게 처리할 수 있다. 직선 경로 \(a - b\)에 모두 xor을 하려면, \(a\)에 xor한 후 \(b\)에 도달할 때까지 전이를 해주고, \(b\) 이후에는 다시 똑같은 수를 xor하여 이후 노드에는 영향을 주지 않게 해주면 된다. 즉 특정 구간에 ..

→2022.09.14

[백준 25500] 무자비한 최단 경로

1. 풀이 간단한 풀이로는 \(O(N^2)\)개의 간선을 모두 생성한 그래프에서 다익스트라를 실행하는 것이다. \(O(N^2logN)\)에 실행될 것이며, 시간 복잡도를 줄일 방법을 고민해야 된다. 첫번째로 문제에서 주어진 \(x, y\)에 대한 거리 공식에 대해 잘 관찰해보자. 백준 2887 행성 터널을 해결했다면, 쉽게 관찰할 수 있는 사실은 각 좌표마다 제일 가까운 것만 간선을 생성해도 괜찮다는 것이다. 구체적으로 설명하자면 어떤 점 \((x, y)\)와 이어야 되는 것은 \(x\)와 가까운 점 2개, \(y\)와 가까운 점 2개를 연결한다는 것이며, 손으로 여러번 그리다 보면 이 간선만으로도 충분히 괜찮다는 믿음이 강하게 생긴다. 두번째로 \(z\)에 한 조건을 잘 살펴보자. \(z\)가 상당히 ..

→2022.09.14

[백준 15506] 정원사

1. 풀이 세그먼트 트리에 pq를 넣는 다는 신박한 아이디어다. \(2, 3\)번 쿼리를 보면 세그먼트 트리로 관리해야 겠다는 생각이 든다. 또한 \(1\)번 쿼리의 어떤 정원에 존재하는 값은 모두 관리해주어야 된다. 세그먼트 트리의 리프 노드에 pq를 넣자. 그렇다면 \(1\)번 쿼리는 세그먼트 트리의 리프 노드의 pq에 값을 넣는 것으로 처리할 수 있다. \(2\)번 쿼리를 생각해보자. 각 구간의 정원에서 가장 큰 값 가지는 정원의 인덱스를 가져오는 쿼리를 할 수 있다면 쉽게 해결할 수 있다. 그리고 인덱스에 있는 리프 노드의 pq에서 값을 하나 빼주면 된다. 기껏해봐야 M번 반복 될 것이다. 각 정점에 {pq에서 가장 큰 값, 인덱스}를 관리해주면 쉽게 해결해줄 수 있다. \(3\)번 쿼리는 단순히..

→2021.12.21

[백준 20052] 괄호 문자열 ?

1. 풀이 \(( = 1, ) = -1\) 으로 치환하고 구간합을 만들어 보자. 그러면 어떤 구간 \([l, r]\)이 올바른 괄호문자열인 충분 조건은 아래와 같다. 1. \(psum_l = psum_r + 1\) 2. \(psum_r \le min(psum_{[l,r]})\) min은 세그먼트 트리로 쉽게 구해줄 수 있다. \(O(QlogN)\)에 문제를 해결할 수 있다. 추가로 구간 합 아이디어와 스택을 활용하면 쿼리를 O(1)에 해결할 수도 있다. 2. 소스코드 #include using namespace std; struct Segment { int n; vector seg; void Init(int _n) { n = _n; seg.resize(4*n, 1e9); } int update(int n..

→2021.12.21

[백준 17704] Matryoshka

1. 풀이 각 쿼리마다 조건을 만족하는 점들 중에서 \((a, b) (c, d) a d\)를 만족하는 LIS길이가 쿼리의 답이 된다. Dilworth's theorem과 관련이 있다. 그러므로 쿼리를 오프라인으로 잘 스위핑 하면서 LIS는 세그먼트 트리로 잘 구해줄 수 있다. \( O(NlogN)\)에 문제를 해결할 수 있다. 2. 소스코드 #include using namespace std; typedef pair pi; #define R first #define H second stru..

→2021.12.21

[백준 7994] The Islands

1. 풀이 도형 \(A\)가 도형 \(B\)에 포함 되어 있다는 것은 \(sy_B\) \(ey_B\) 사이에 도형 \(A\)가 포함된다는 것이다. 문제에서 교차하는 도형이 없다고 주어졌기 때문에 이렇게만 고려해주어도 괜찮다. 위의 아이디어를 기반으로 어떤 도형이 주어졌을 때 +\(1\), -\(1\)을 가진 \(y\)가 있고, \(x\)축의 구간으로 분리하자. 문제의 예제 중 도형 하나를 구간으로 분리한 것이다. 이 도형을 분리하는 방법은 lazy seg로 할 수 있다. 1. \(x\)축에 있는 모든 값을 \(0\)으로 초기화한다. 2. 도형에서 \(x\)축에 평행한 구간만 확인한다. 구간의 값이 \(0\)인 경우 +\(1\) 구간이 되고, \(1\)인 경우 -\(1\) 구간이 된다. 모든 도형을 \(x..

→2021.12.13