전체 글
[백준 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\)를 포함하는..
n sqrt n에 특수한 조건의 배낭 문제 해결하기
이 글에서 다룰 문제는 아래와 같다. 1. \(N\)개의 물건의 가치 \(v_1, v_2, ..., v_n\)이 주어진다. \(W=\sum_{i=1}^N v_i\)로 정의한다. 2. 각 물건을 선택한 여부를 \(x_1, x_2, ..., x_n\)으로 정의한다. 3. \(\sum_{i=1}^N {v_ix_i} \sim O(N)\)을 만족한다. 4. \((\sum_{i=1}^N {v_ix_i})(W - \sum_{i=1}^N {v_ix_i})\)를 최대화 해야 된다. 문제를 다시 말하자면 각 물건을 두 그룹으로 나누고, 두 그룹의 속한 물건의 합의 곱을 최대화하는 문제이다. 이 문제의 naive한 풀이는 배낭 문제처럼 \(O(NW)\)에 해결할 수 있다. 한 그룹의 합이 \(X\)가 될 수 있는 여부를 알..
![[백준 5979] 납땜하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FANiNP%2FbtrMIdTPQhb%2FnLWirLYQ2Udpd7G4N9egk0%2Fimg.png)
[백준 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]\)를 ..
[백준 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하여 이후 노드에는 영향을 주지 않게 해주면 된다. 즉 특정 구간에 ..
[백준 25500] 무자비한 최단 경로
1. 풀이 간단한 풀이로는 \(O(N^2)\)개의 간선을 모두 생성한 그래프에서 다익스트라를 실행하는 것이다. \(O(N^2logN)\)에 실행될 것이며, 시간 복잡도를 줄일 방법을 고민해야 된다. 첫번째로 문제에서 주어진 \(x, y\)에 대한 거리 공식에 대해 잘 관찰해보자. 백준 2887 행성 터널을 해결했다면, 쉽게 관찰할 수 있는 사실은 각 좌표마다 제일 가까운 것만 간선을 생성해도 괜찮다는 것이다. 구체적으로 설명하자면 어떤 점 \((x, y)\)와 이어야 되는 것은 \(x\)와 가까운 점 2개, \(y\)와 가까운 점 2개를 연결한다는 것이며, 손으로 여러번 그리다 보면 이 간선만으로도 충분히 괜찮다는 믿음이 강하게 생긴다. 두번째로 \(z\)에 한 조건을 잘 살펴보자. \(z\)가 상당히 ..
AtCoder Beginner Contest 254
A - Last Two Digits 단순 문자열 문제입니다. B - Practical Computing 문제에서 주어진 대로 구현하면 됩니다. C - K Swap 관찰하면 인덱스 \(i\)가 \(k\)로 나눈 나머지 끼리의 위치끼를 서로 swap을 해줄 수 있습니다. 그러므로 같은 나머지끼리 묶인 그룹들은 무조건 오름차순으로 정렬할 수 있습니다. 나눈 그룹들을 전체로 합친 다음 오름차순의 결과와 같은 지 확인해주면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ..
AtCoder Beginner Contest 243
A - Shampoo \(V\)를 \((a+b+c)\)의 합으로 나뉘어주고, 시뮬레이션을 해주면 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC opt..