본문 바로가기

Computer Science

(29)
2022-06-05 Problem Solving 최근에 여러 문제를 해결하였다. 최근에 해결해 본 문제들의 풀이를 간략하게 정리해보았다. 4230. 사랑과 전쟁 편의상 0번 남편을 위쪽에 앉히자. 남편과 아내가 같은 편에 앉을 수 없다는 조건과 각 불륜 쌍 중 최소 한 쪽은 아래 쪽에 앉아야 한다는 조건은 typical한 2-SAT 조건 식으로 만들어줄 수 있다. 2-SAT을 구하는 알고리즘을 돌려서 문제를 해결할 수 있다. 21065. Friendship Circles 문제에서 물어보는 것은 $p_0$ 에 대해 점들을 반전시켜 생각해보면 간단하다. $p_0$ 와 $p_i$ 만을 포함하는 원이 있는 것은 $p_i$를 반전 시킨 점을 지나는 직선이 존재해 나머지 점들을 한쪽 반평면에만 놓이게 할 수 있음과 동치이다. 따라서, $p_i$를 반전시킨 점을 ..
랜덤한 교란 순열을 생성하는 card-based 프로토콜 (1) 1. Introduction Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다. 이렇듯, 현실에는 각자 자신에게 배정된 수 외의 정보를 알 수 없는 상태에서 derangement를 랜덤하게 생성해야 하는 (암호학적인 ..
2-SAT 및 그의 응용 1. 2-SAT 문제란? 2-SAT 문제란 참/거짓의 값을 가지는 불리언 변수 $n$개 $x_1, x_2, \cdots, x_n$ 와 2-CNF가 있을 때, 2-CNF를 참으로 만들기 위해 $x_i$ 들에 적당한 값을 할당하는 문제이다. 2-CNF란 2개의 변수를 $\lor$ (or)한 식(절) 여러 개에 $\land$ 연산을 취해 만들어지는 식을 의미한다. 예를 들어, $(x_1 \lor x_2) \land (\bar x_3 \lor x_4)$ 는 2-CNF이다. 그리고, $x_1 = true$, $x_2 = false$, $x_3 = false$, $x_4 = false$ 는 이 식을 만족 시키는 하나의 방법이다. 반대로, $(x_1 \lor x_1) \land (\bar x_1 \lor \bar x..
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 연산으로는 기우성이 같은 인덱스 끼리만 바꿀 수 있음을 알 수 있다. 고로, 홀수 번째 인덱스와 짝수 번째 인덱스를 별개로 생각해볼 수 있다. 버블 소트를 생각해보면, 인접한 인덱스의 스왑 연산으로는 모든 배열을 정렬할 수 있음을 알 수 있다. 따라서, 홀수 번째 인덱스에는 홀수만, 짝수 번째 인덱스에는 짝수만 있는 것이 정렬 가능할 필요충분조건임을 알 수..