PS 일지

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼?프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐www.acmicpc.net문제 요약건물을 정점으로 본 방향그래프가 주어진다. 각 건물은 건설하거나 파괴될 수 있다. (중복 건설도 가능하다.)건물들 사이의 관계를 나타내는 방향 간선이 주어진다. 간선 $X \rightarrow Y$는 건물 $X$가 건설된 상태여야 건물 $Y$가 건설될 수 있다는 의미이다.$K$개의 작업이 주어지며, 각 작업은 건물 $a$를 건설하거나 파괴하는 것이다.이 $K$개..

https://www.acmicpc.net/problem/25685 25685번: 좋은 노드 집합 찾기Alice와 Bob은 트리를 이용한 놀이를 즐겨한다. n개의 노드를 가진 트리 가 있고 노드는 편의상 번호가 1부터 n까지 붙어있다고 하자. i번 노드의 부모 노드는 p[i] 라 하고, 루트 노드의 경우 p[i] = 0www.acmicpc.net문제 요약정점에 $1$부터 $N$까지 번호가 부여된 루트 있는 트리에서, "좋은 노드 집합"은 이 트리의 노드의 부분집합 $S$이면서 아래 조건을 모두 만족하는 집합으로 정의한다.어떤 노드 $x$가 $S$에 속해있다면 $x$와 연결된 노드들은 $S$에 속하지 않는다.어떤 노드 $x$가 $S$에 속하지 않았다면 $x$의 자식 노드들 중 최소 하나의 노드는 $S$에 ..

12/1 ~ 12/10에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 12/1BOJ 1911 - 흙길 보수하기Gold 5 #sorting #greedy 웅덩이들을 $x$좌표 기준 오름차순으로 정렬해놓고, 변수 $t$를 (마지막 널빤지가 덮고있는 끝 지점 +1)로 유지하며 관리하자.어떤 웅덩이 $[S, E)$에 대해, 그 웅덩이를 모두 덮기 위해 필요한 널빤지 수는 다음과 같다. $\lfloor \dfrac{E - \max(t, S) - 1}{L} \rfloor + 1$ 단, 마지막 널빤지가 그 웅덩이 전체를 포함하는 경우는 예외다.BOJ 30037 - K-Words ProblemGold 3 #implementation #string 문장 하나를 getline으로 받아서 2번 규칙을 가..

11/21 ~ 11/30에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 11/22BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)Platinum 4 #dfs #sweeping 깊이를 기준으로 스위핑을 하면 된다.$0 \le i \le j \le \log_2{N}$인 $i, j$에 대해, 깊이 $i$ 이상 $j$ 이하의 모든 점을 탐색하며 최대 연속합을 구하자.이 스위핑+탐색이 문제에서 요구하는 직사각형을 그려보는 것에 해당한다.연속합은 트리를 inorder 순서로 펴서 구해도 되는데, 본인은 금광 테크닉으로 구했다.BOJ 16877 - 핌버Platinum 3 #sprague_grundy 스프라그-그런디 정리로 해결하면 된다.m..

11/11 ~ 11/20에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 11/11BOJ 10216 - Count Circle GroupsGold 4 #geometry #disjoint_set $O(N^2)$에 간선을 생성해주고, 컴포넌트 개수를 세주면 된다.11/12BOJ 30510 - 토마에 함수Gold 1 #Euler's_totient_function $1 + \sum \limits_{i=1}^{\lfloor \frac{Q}{P} \rfloor} \phi{(i)}$을 구해주면 된다.11/13BOJ 14451 - 안대 낀 스피드러너Platinum 5 #bfs 위를 보는 상태와 오른쪽을 보는 상태를 시작으로, 두 점을 동시에 움직이며 bfs하면 된다.상태 1의 $x, y$좌표 및 방향, ..

11/1 ~ 11/10에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요.11/1BOJ 16132 - 그룹 나누기 (Subset)Gold 4 #knapsack 각 부분집합의 합은 $\frac{N(N+1)}{4}$가 되어야 한다. 이 값이 정수가 아니면 답은 $0$이다. 그렇지 않으면, $1, 2, \cdots, N$으로 $\frac{N(N+1)}{4}$를 만드는 경우의 수를 knapsack dp로 세어주자.BOJ 11657 - 타임머신Gold 4 #bellman_ford 음수 가중치가 있는 그래프에서 최단 경로를 구해야 하므로 벨만-포드를 써주자. 벨만-포드 알고리즘의 기초 문제이다.BOJ 11404 - 플로이드Gold 4 #floyd-warshall 모든 정점 사이의 최단 경로를 구하는 플로이드..

10/21 ~ 10/31에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.10/21BOJ 9741 - Interior Lattice PointsGold 3더보기#pick's_theorem #polygon_area픽의 정리란? 2차원 격자 위의 단순 다각형에 대하여, 다각형의 넓이를 $a$, 다각형의 변 위에 존재하는 정수 좌표 점의 수를 $b$, 다각형의 내부(경계 미포함)에 존재하는 정수 좌표 점의 수를 $i$라고 하면 $A = i + \dfrac{b}{2} - 1$가 성립한다. 이 식을 $i$에 대해 정리해서 풀자. 세 점이 일직선상에 있는 경우를 조심하자.10/22BOJ 25187 - 고인물이 싫어요Gold 4더보기#dfs같은 연결 요소 내에서..

10/11 ~ 10/20에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.10/11BOJ 10436 - 무한 유리수 트리Gold 4더보기#math #tree$pq$인 경우는 $p BOJ 23734 - Miswritten DFSPlatinum 5더보기#dp_tree #dfs #recursion정점 $n$의 왼쪽 자식과 오른쪽 자식을 각각 $l, r$이라고 하자. $n$을 루트로 갖는 dfs를 실행할 경우 $n$의 서브트리의 정점 수만큼의 탐색이 진행된다. 이 때, $l$을 루트로 하는 dfs는 두 번 수행되므로 서브트리의 수 $sub[n] = 2sub[l] + sub[r] + 1$로 정의하자. 이는 한 번의 dfs로 쉽게 구할 수 있다. 이제 ..

10/1 ~ 10/10에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.10/2BOJ 30284 - KarjerasGold 5더보기#prefix_sumimos법으로 알려져있는 걸로 알고 있다. 구간의 변화를 시작점과 끝점에 각각 +1, -1을 취하는 방법인데, 이 문제에선 반대로 -1, +1을 해주면 된다. BOJ 30276 - TraukinysGold 4더보기#greedy만약 $a_{i}$가 $K$보다 작다면, 무조건 가까운 곳에서 끌어오는 것이 이득이다. 끌어오는 쪽의 $a_{i}$가 $K$보다 작아도 무조건 끌고 오는 것이 포인트이다. 아이디어는 금방 떠올랐지만 개인적으로 구현이 힘들었다.10/3BOJ 6611 - Simon the SpiderPl..

9/21 ~ 9/30에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어 있습니다.잘못된 풀이가 있다면 지적해주세요.9/21BOJ 30092 - 슥삭슥삭 나무자르기Platinum 1더보기#tree #lca경로 $a$-$b$와 $c$-$d$가 두 점 이상을 공유하는 지 판별하자. 여러 lca를 구해서 경우를 따져보면 된다. BOJ 30155 - Crazy Malvika discovers Crazy Fibonacci functionSilver 3더보기#math주어진 수열은 첫 6개의 항이 계속 반복되는 형태이다. 9/23백준에 올라온 ZOAC 대회 문제들을 풀었다. 처음으로 대회 문제 출제진으로 참여했다. 문제 만들기도 어려웠지만, 다른 사람들이 만든 문제를 풀고 검수하는 게 훨씬 힘들었다. BOJ..