PS (4) 썸네일형 리스트형 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.. 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 다음
