PS 일지

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같은 연결 요소 내에서..

Codeforces Round 906 (Div. 2)CP를 연습하고 싶어 시간만 된다면 앞으로 많이 해볼 계획이다. A - Doremy's Paint 300:06 AC홀수 항과 짝수 항이 모두 같을 수 있는지 판별하면 된다. B - Qingshan Loves Strings00:15 AC$s$가 good이면 무조건 Yes이다. $s$와 $t$가 good이 아니면 무조건 No이다. 그렇지 않은 나머지 경우에 대해서만 생각하면, $t$는 항상 good이다.$s$가 good이 되지 못하도록 하는 모든 쌍에 대해, 그 쌍에 $t$를 넣었을 때 해당 쌍이 good에 기여할 수 있는지 판별하면 된다. C - Qingshan Loves Strings 200:48 AC$i = 1$부터 차례대로, $s_i \neq s_..

Codeforces Round 900 (Div. 3)생애 두 번째 코드포스 대회이다. 첫 번째는 글을 쓰기엔 몇 달 지나기도 했고, 너무 말아먹어서 passCP가 다 그렇듯, 알고리즘 분류와 난이도를 볼 수 없고 영어로 되어있어서 실력 향상에 많이 도움이 될 것 같아서 시작했다. 열심히 해서 힘이 닿는 데까지 점수를 올려보려 한다. A - How Much Does Daytona Cost?00:04 AC$k$가 등장했다면, 그 자체로 $k$가 most common element인 subsegment가 될 수 있다. B - Aleska and Stack00:23 AC$a_1 = 2, a_2 = 3$으로 놓고 $i>2$인 $i$에 대해 $a_i$를 $a_{i-1}$보다 크면서 $3(p-a_{i-1}) \mo..

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..

9/11 ~ 9/20에 푼 문제들입니다.문제의 풀이에 대한 스포일러가 포함되어있습니다.9/11BOJ 2263 - 트리의 순회Gold 1더보기 #divide_and_conquerpostorder로 방문한 마지막 정점이 트리의 루트임을 이용해서 루트 기준으로 왼쪽 서브트리, 오른쪽 서브트리에 대해 각각 루트를 구해주는 방식으로 해결할 수 있다. BOJ 1774 - 우주신과의 교감Gold 3더보기 #mstmst에서 이미 연결된 간선들이 주어지는 것 이외에는 기본 mst 문제와 같다. BOJ 6497 - 전력난Gold 4더보기 #mst mst의 가장 기본적인 문제이다. BOJ 17299 - 오등큰수 Gold 3더보기#stack{각 수가 등장한 횟수, 인덱스} 쌍으로 stack에 차례대로 넣으면서 오등큰수를 찾..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.www.acmicpc.net 문제 요약주어진 행렬 $A$와 자연수 $B$에 대하여, $A^B$의 각 원소를 1000으로 나눈 나머지를 출력하는 문제이다. 해결 전략어떠한 정수 $A$를 B제곱하는 것은 분할 정복을 이용하여 계산하는 것이 잘 알려져있다.$A^B = A^{B/2} * A^{B/2}$이고, $A^{B/2} = A^{B/4} * A^{B/4}$이고,...이렇게 계속해서 B를 절반으로 쪼개어 생각하면 $O(log{B})$에 $A^B$를..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로www.acmicpc.net 문제 요약높이가 $N$인 하노이 탑을 푸는 데 걸리는 최소 이동 횟수와 이동 경로를 출력하는 문제이다. 해결 전략높이가 $N$인 하노이 탑을 1번에서 3번으로 이동하는 것이 문제의 목표이다. 단순하게 생각해보자.$N = 3$인 하노이 탑이 있고, 이를 3번 판 위로 모두 옮겨야 한다.가장 밑 발판을 제외한 $N = 2$의 하노이 탑을 2번 판으로 옮긴다.(이것은 한 번의 이동으로는 할 수..