PS 일지

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$좌표 및 방향, ..

제1회 스타보우컵에 참가했다. 누워서 뒹굴거리다가 시간을 보고 뒤늦게 참가했다. Red - 이 별은 무슨 색일까 00:31 AC if-else를 쓸 줄 아는가? 라는 문제다. Orange - 반짝반짝 빛나는 별가루 00:38 AC 시뮬레이션(?)같은 단순 계산 문제다. 요소가 많아서 생각보다 푸는 데 오래 걸렸다. Yellow - 별 가두기 00:45 AC 진짜 시뮬레이션 문제다. 별을 직접 움직여보고 같은 칸에 같은 방향을 가지고 있을 때가 있다면, 가두기에 성공한 것이다. Green - 별 안에 별 안에 별 찍기 01:02 AC 문제를 보자마자 한숨을 쉬었다. 3125 * 3125 크기의 공간을 미리 잡아두고, 재귀로 칸들을 채워줬다. Blue - 별자리 만들기 01:19 AC 처음에 주어지는 트리는..

Codeforces Round 909 (Div. 3)이번 라운드는 여러모로 아쉬운 게 많은 대회였다... 못 푼 문제들이 다 뭔가 아쉽게 놓친 듯한 느낌이 들어서였다.못 한 만큼 더 열심히 공부해야겠다. B - 250 Thousand Tons of TNT00:08 AC $N$이 $K$로 나누어떨어지는 모든 경우에 대해 확인해보면 된다. 누적 합을 곁들이면 어떤 $K$에 대해 $O(\frac{N}{K})$의 시간이 걸린다. A - Game with Integers00:02 WA 00:09 AC $N$이 3의 배수이면, 반드시 선공이 진다. 선공이 3의 배수에 +1 혹은 -1을 해도 후공이 다시 3의 배수로 만들어버리면 선공은 영원히 3의 배수를 만들지 못하기 때문이다.반대로 $N$이 3의 배수가 ..

2023 Sogang Programming Contest Open (Master)에 참가했다. 전날에 열렸던 Arena #11을 놓쳐서 이번에는 꼭 해야지 생각하며 등록을 하고 잔 것 같았는데, 일어나보니 등록이 안되어있었다. 아레나는 언제쯤 참가할 수 있을까.. A - Knob00:06 AC 직전의 $L, R$ 값을 갖고 있으면서 매번 확인해주면 된다. B - donstructive00:10 AC $1, N, 2, N-1, \cdots$ 순으로 배치하면 된다. C - 내 집 마련하기00:23 AC $L, R$에 해당하는 인덱스를 정렬시켜 $L$부터 $R$까지 사람에 대해 재배치하면 된다. D - 서로소 싫어00:39 WA 00:39 WA 00:40 AC $x$를 $xy$로, $xy$를 $y..

2023 IGRUS Newbie Programming Contest Open에 참가했다. Arena #11이 끝나고 바로 열려서 1솔만 하고 가신 분들이 많은 것 같다. A - 아이그루스와 화장실00:21 AC $K-1, K, K+1$중 적절한 곳으로 보내주면 된다. B - 트릭 플라워00:28 AC R의 제한이 작아서 직접 시뮬레이션하면 된다. C - 인형 전시00:33 WA 00:38 WA 00:38 AC 높이가 작은 것부터 한 열에 하나씩 채워주면 된다. 배치했을 때 가려지는 것이라면, 채우지 말고 건너뛰어야 한다.첫 WA는 구현 실수, 두 번째 WA는 코드 한 줄을 실수로 지우고 내버려서 떴다. D - 회문 끝말잇기02:00 WA 02:02 AC 게임 특성상, 시작 알파벳과 끝 알..

SASA Programming Contest 2023 Open Contest Div. 1에 참가했다. 아레나에 참가하고 싶었는데, 시간이 늦어서 등록을 못 했다. A - 방형구 탐색00:36 AC 쿼리를 naive하게 $O(N)$으로 구현하면 총 시간복잡도 $O(NQ)$로 통과한다. B - 미역은 식물 아닌데요00:40 AC 어떤 식물 $i$에 대해,$P == 1$이면서 $M == 0$인 것은 항상 식물이다.$P == 0$이거나 $M == 1$인 것은 항상 식물이 아니다.그 외의 것들은 식물이 될 수도 있고, 되지 않을 수도 있다. C - 가위 가위 가위00:47 WA 00:48 AC $1 \le i \le 100$에 대해, $i$번째에만 주먹을 내고 나머지는 모두 가위를 내서 대결을 총 100번..

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