분류 전체보기 (6) 썸네일형 리스트형 Codeforces Hello 2026 후기 몇달간 1600대 초반에만 머무르던 나를 바로 1700대 중반으로 보내준 Hello 2026에 대한 후기를 작성하겠다. A. Binary Array Game (00:00 ~ 00:05) 문제를 잘 관찰해보면, Alice가 이기기 위해서는 초기 배열에 0이 없거나, 한번의 시행 뒤에 배열에 0이 없어야 한다. 이를 위해서는 초기 배열에서 A[0] 혹은 A[-1] 값이 1이면 된다는 사실을 알 수 있다. B. Yet Another MEX Problem (00:05 ~ 00:14)문제가 좀 복잡한데, 어떤 길이 K의 버킷을 잡아 하나를 제거한다 해도, K-1개로 이루는 mex 값은 항상 유지시킬 수 있다는 사실을 통해 수열 자체의 mex 값과 K 중 최솟값을 출력하면 된다. C. War Strategy (0.. 2025년 회고록 보호되어 있는 글입니다. Educational Codeforces Round 184 (Rated for Div. 2) 후기 그동안 많은 일이 있었다. 학교에서 코포 2번을 쳤는데 무려 2솔과 1솔을 해내면서 민트로 회귀해버렸다... 다시 블루로 복귀하고자, 다시는 안 치기로 한 에듀 코포를 치기로 마음먹었다. 그래도 내 첫 코포가 에듀 코포였던만큼, 좋은 결과가 있기를 바랐다. A. Alice and Bob (00:00 ~ 00:09, +1)간단한 문제다. a보다 큰 값과 작은 값 중 그 개수가 많은 쪽으로 b를 설정하면 된다. 처음에 뻘짓하다가 중복 원소를 체크하지 못해서 1틀한 점이 아쉽다. B. Drifting Away (00:09 ~ 00:15)무한 루프가 도는 경우만 잘 체크해주고 나머지는 스위핑하면서 세주면 된다. 별로 할 말은 없다. C. Range Operation (00:15 ~ 00:26)재밌는 문제다. [.. BOJ 16041. Double Clique 문제 링크 옛날에 나코더 셋에 있었던 문제인데, 풀이가 인상 깊어서 한 번 블로그에 남겨보려고 한다. 1. 문제 설명무방향 그래프 $G$가 주어진다. 정점들의 집합을 $V$라고 하자. $G$의 여그래프 $G'$을 다음과 같이 정의하는데, 모든 $a, b \in V \ (a \neq b)$ 에 대해서 $G$ 에서 $a, b$를 잇는 간선이 있다면 $G'$에는 간선이 없고, $G$ 에서 $a, b$를 잇는 간선이 없다면 $G'$ 에는 간선이 있다. 클리크는 모든 노드 쌍이 연결된 정점 부분 집합을 의미하는데,노드의 부분 집합 $S$ (공집합 포함)가 다음을 만족하면 더블 클리크 (Double clique)라고 정의한다.1. $S$는 $G$에서 클리크이다.2. $V-S$ ($S$를 제외한 나머지 노드 집합) .. Heavy Light Decomposition (HLD) HLD (Heavy Light Decomposition)는 트리에서 구간 쿼리를 O(log^2 N) (N : 노드 수)에 수행하는 자료구조이다. 기본적으로 ETT (Euler Tour Technique)를 기반으로 하는데, 먼저 이에 대해 설명하겠다. 1. Euler Tour Technique 쉽게 말하자면, 노드에 방문 순서대로 번호를 매기는 것이다. 다음과 같은 트리를 생각해 보자. ETT에서는 각 정점에 두 개의 변수를 저장한다. 바로 in과 out인데, in은 정점을 방문한 순서, out은 정점의 하위 노드 중 가장 큰 방문 순서 즉, 가장 늦게 방문된 노드의 in 값을 저장한다. void dfs(int node) { in[node] = ++cur; for (int i:Edges[no.. Codeforces Round 1046 (Div.2) 후기 첫 블로그 글을 써본다.어제 무려 3시간동안 진행된 코포의 후기를 작성해보겠다. A. In the Dream (00:00 ~ 00:06)각 팀이 매 half 마다 얻은 점수를 구해서 가능한지 여부를 판단하면 된다. 조건 분기가 좀 있었다. B. Like the Bitset (00:06 ~ 00:13)조건에 맞게 순열을 구성해야 하는 문제이다. 길이가 k 이상인 순열의 연속 부분 수열을 임의로 선택할 때, 그 부분 수열의 최댓값의 위치에 해당하는 주어진 문자열의 값이 0이어야만 한다. 풀이는 꽤 간단하다. 주어진 문자열의 값이 0인 위치에 우선적으로 큰 값을 배치한다. 순열을 구성하는 것이기 때문에, idx를 N으로 설정한 후, 1씩 줄이면서 배치하면 된다. 이후, 문자열의 값이 1인 위치에 같은 방법으로.. 이전 1 다음
