본문 바로가기

Computer Science

(25)
2021-09-10 Problem Solving 11385. 씽크스몰 단순히 다항식의 곱셈을 FFT로 수행하면 해결할 수 있어 보인다. 하지만, 입력되는 수의 범위를 살펴보면, long double을 써도 맞기 쉽지 않음을 알 수 있다. 나는 조금 더 안전 빵으로, 소수 두 개를 이용해 NTT를 두 번 한 후, CRT를 이용해 계수들을 복원하여 문제를 해결했다. 19265. Is it a p-drome? 모든 값을 0-based index로 생각하자. 어떤 문자열이 $p$-drome 이라면, $p$를 적용한 결과물과 해당 문자열의 라빈 핑거프린트 해시 값이 같을 것이다. 고로, $i$에서 시작하는 길이 $m$인 문자열을 본다고 할 때, 원래 문자열의 해시 값은 $\sum_{j=0}^{m-1} a_{i+j} x^j$ 이 될 것이고, $p$를 적용한 결과..
2021-08-27 Problem Solving 요즘도 꾸준히 1일 1문제는 해결하려고 노력 중이다. 지난 번에 글 쓰고 나서 풀었던 문제들 중 일부를 뽑아서 풀이를 올려본다. 17114. 하이퍼 토마토 간단한 BFS를 통해 문제를 해결할 수 있다...만, 11차원 입력을 효율적으로 처리하는 것이 중요한 문제다. 나는 11차원 배열을 선형으로 펴고, 적절한 사칙연산을 통해 11차원 벡터와 선형 배열 인덱스 사이의 변환을 해주는 방식으로 구현했다. 나의 구현 방식으로 문제를 해결하기에는 다소 빠듯한 면이 있어서, 빠른 입출력 등의 여러 최적화를 함께 사용하여 문제를 해결했다. 22967. 구름다리 성게 그래프를 출력하면, 답이 2 이하임이 보장된다. 이제, 답을 1로 만들 수 있는지를 확인해줘야 하는데, 이는 완전 그래프인 경우에만 가능하다. 따라서, ..
2021-08-21 Problem Solving 이번에도 문제를 비교적 꾸준하게 풀었던 것 같다. 특히, 이번 주 부터는 ho94949님, dennisstar님과 함께 하루에 랜덤 문제 5개를 뽑아서 하나 이상 푸는 챌린지를 하고 있어서 (나 말고 나머지 두 분은 웬만해서 거의 다 풀긴 하는듯) 더 자극이 되었던 것 같다. 20986. Group Photo 1번부터 $i$번까지만 생각해주는 방식으로 DP를 할 수 있다. 이 DP를 효율적으로 하는 방법에 대해서 생각해보면 되는데, $i$ 앞에 $j$가 오는지의 여부를 $N^2$개의 쌍에 대해 전부 이차원 배열에 구해둔 뒤, $x$축과 $y$축 두 방향 모두에 대해서 prefix sum 전처리를 해두고 활용할 수 있다. 15759. Talent Show 1000을 곱해주는 귀찮은 부분은 따로 빼두고 생각..
2021-08-08 Problem Solving 오랜만에 문제 해결을 좀 해봤다. 18227. 성대나라의 물탱크 DFS ordering을 이용하여 트리를 직선으로 펼 수 있다. 구체적으로는, DFS에서 정점 $u$를 처음 방문하는 시각을 $in[u]$, 빠져나오는 시각을 $out[u]$라 할 때, $u$의 서브트리의 방문 시각은 $[in[u], out[u]]$ 범위에 속함을 알 수 있다. 이를 이용하면, 트리를 선형으로 다룰 수 있고, Binary Indexed Tree 와 같은 자료구조를 함께 얹어서 문제를 해결할 수 있다. (왜냐하면, 어떤 정점에 물이 차는 횟수는, 해당 정점을 루트 노드로 하는 서브 트리에 물을 채우려 시도하는 횟수와 같기 때문이다.) 참고로, DFS ordering을 이용하여 트리를 직선으로 펴는 테크닉은 여러 분야에 응용의 ..
2021-08-01 Problem Solving 한 동안 정신 없는 일정 때문에 알고리즘 문제 해결을 별로 하지 못했으나, 최근에 여유가 생겨 SCPC 대비도 해볼 겸 다시 잡기 시작했다. 이번에 해결한 문제들을 정리해본다. 어찌 뒤로 갈수록 풀이를 대충 적은 것 같다... 21586. Another Substring Query Problem 쿼리가 하나만 주어진다면 어떨까? 문자열 $S$에 특정한 패턴 $P$가 $k$ 번째로 등장하는 지점을 찾는 문제가 된다. 이는 라빈 핑거프린트를 이용하여 문자열을 해싱해놓은 후, $|P|$ 길이의 부분 문자열을 살펴보며 쉽게 해결할 수 있다. 이 경우, 전체 과정이 약 $O(|S| + |P|)$ 정도의 시간에 이루어진다. 그런데, 이 과정을 모든 쿼리에 대해 반복하게 된다면, $O(Q(|S| + |P|))$​ 정..
Generalized Sorting with Predictions 이 글에서는 Pinyan Lu 외 3인의 논문 "Generalized Sorting with Predictions"에 대해 소개합니다. 구사과님이 호스트 하는 스터디 #project_tcs 에서도 발표를 한 번 했는데, 발표 자료는 다음 링크에 있습니다. 오타가 많음에 유의하세요. 1. Generalized Sorting Problem 1.1. 문제의 정의 어떤 object들을 정렬하는 것은 컴퓨터 과학에 있어 매우 중요한 문제입니다. 일반적으로 우리가 (comparison-based) 정렬을 한다고 할 때, 우리는 임의의 원소 간의 "비교"가 가능한 상황을 상정합니다. Generalized sorting problem에서는 이 상황을 보다 일반화하여 일부 원소들 사이에는 비교 연산을 이용할 수 없는, ..
제2회 UNIST 알고리즘 프로그래밍 경진대회 Uni-CODE 2020 이번에 UNIST 알고리즘 프로그래밍 경진대회에 3문제를 출제했다. 출제와 검수의 전 과정을 도울 수 있어서 기뻤고, 좋은 경험이었던 것 같다. 간단한 풀이는 아래와 같고, 문제 채점은 다음 링크에서 할 수 있다. https://acmicpc.net/category/detail/2353 A. 트리플 소트 출제: queued_q 문제에서 주어진 swap 연산으로는 기우성이 같은 인덱스 끼리만 바꿀 수 있음을 알 수 있다. 고로, 홀수 번째 인덱스와 짝수 번째 인덱스를 별개로 생각해볼 수 있다. 버블 소트를 생각해보면, 인접한 인덱스의 스왑 연산으로는 모든 배열을 정렬할 수 있음을 알 수 있다. 따라서, 홀수 번째 인덱스에는 홀수만, 짝수 번째 인덱스에는 짝수만 있는 것이 정렬 가능할 필요충분조건임을 알 수..
SCPC 2020 짧은 후기 1차 예선 SCPC 1차 예선은 무난하게 통과했던 것 같아서 별 기억이 없습니다. 100 / 150 / 150 / 39 / 0을 받았습니다. 2차 예선 SCPC 2차 예선은 건강검진 예약일과 겹쳐서 많은 시간을 투자하지는 못했습니다. C번 문제가 풀이 자체는 쉬우나, 상수가 큰 풀이는 통과하지 못하는 빡빡한 제한이라 해결하지 못했던 점이 아쉬웠습니다. 100 / 150 / 61 / 41 / 47을 받았습니다. 본선 본선에 갈 것이라고 생각하지 못했지만, 본선에 참가하게 되었습니다. 본선 문제를 보니 생각보다 어려워 보여서, 점수만 열심히 긁어도 상은 받을 수 있다고 생각했습니다. 1번 문제는 쉬워서 간단히 100점을 받았습니다. 2번 문제는 지문이 더러워서 뭐 하라는건지 한참을 고민했는데, 결국 SCC를..
ICPC 2020 Seoul Regional 후기 이채준, 신민철 님과 함께 참가한 대학생 프로그래밍 경시대회에서 8솔브 / 1303분으로 전체 10등을 했고, 학내에서는 2등을 했다. 좋았던 점과 아쉬운 점 모두 있지만, 팀원들에게 수고했다는 말을 해주고 싶고, 우리 팀에 미래가 있다는 사실을 확인했다는 점이 너무나 좋았다. 사실 우리 팀은 인터넷 예선을 앞두고 팀 연습 1번, 인터넷 예선 이후에 팀 연습을 아예 안 할 정도로 별 준비 없이 봤음에도 불구하고, 전체 팀들 가운데 10등을 차지한 것은 사실 꽤나 잘한 성과라고 생각한다. 하지만, 인터넷 예선에서 운 좋게 8등을 한 덕택에 (객관적 실력상 진출이 힘듬이 명백한) 세계 대회에 갈 수 있다는 행복 회로를 돌리던 것은 썩 좋게 작용하지만은 않은 것 같다. 아무튼, 별 준비 없이 전체 10등은 나..
Minimums on the Edges 풀이 최근에 푼 문제 중 가장 재미있는 것 같아서 풀이를 기록해둔다. Link: www.acmicpc.net/problem/18664 18664번: Minimums on the Edges Print n numbers a1, a2, . . . , an (0 ≤ ai ≤ s), where ai is the number of tokens you put on the i-th vertex. The sum of printed integers must be equal to s. The sum of capacities of all edges must be the maximum possible. If there are multiple optimal www.acmicpc.net $N$개의 정점이 있고, $M$개의 간선 $(u_..