-
junis3's profile image
junis3
September 23, 2023
트리 압축의 다른 접근
문제 상황 아래의 문제 상황은 BOJ 16216번 문제에서 만나볼 수 있다. 정점이 가중치가 없는 트리 $T$가 주어진다. $T$는 $N$개의 정점과 $N-1$개의 간선을 가지고 있다. 정점들 가운데, 출발 정점 $v$와, 방문하고 싶은 $K$개의 정점들 $u_1, \cdots, u_K$이 주어진다. 정점 $v$에서 출발해서, $u_1, \cdots, u_K$ 중 1개, 2개, …, K개를 방문하는 가장 짧은 경로의 길이를 각각 구하여라. 아래부터 이 문제에 대한 풀이로 개념에 대한 설명을 시작하려 하니, 아직 이 문제에 대해 고민해보지 않았다면 (스포일러를 피하고 싶다면) 스크롤을...
-
junis3's profile image
junis3
June 24, 2023
Choice Coordination Problem
개요 문제 상황 $n$개의 프로세서가 존재한다. 각 프로세서는 $m$개의 선택지 중 하나를 선택해야 한다. 그런데, 프로세서들이 완전히 비동기적으로 작동한다. 프로세서가 공유하는 일관적인 시계 (global clock)이 존재하지도 않을 뿐더러, 프로세서의 응답 속도에 대한 가정을 할 수도 없다. 이러한 상황에서 모든 프로세서가 동일한 선택으로 합의하도록 하는 알고리즘이 필요하다. 인격을 부여해 이러한 비유 상황을 만들어낼 수 있다: $n$명의 관광객이 존재한다. 그들이 머무는 여행지는 $m$개의 방으로 이루어져 있다. 이 때 관광객 모두가 방 하나에 모일 수 있도록 행동 규약을...
-
junis3's profile image
junis3
May 21, 2023
완전 매칭을 찾는 병렬 알고리즘
PRAM Model PRAM (Parallel Random Access Machine) 모델은 병렬 처리를 이론적으로 표현한 모델이다. $P$개의 프로세서와 크기 $M$의 공통 메모리로 이루어져 있다. PRAM 모델에서 한 번의 (병렬) 연산은 다음과 같은 과정을 통해 이루어진다: 공통 메모리의 어떤 위치에 있는 값을 읽는다. 간단한 (unit-step) 연산을 실행한다. 공통 메모리의 어떤 위치에 값을 쓴다. 여러 개의 프로세서가 동시에 연산을 수행할 때 총돌할 가능성을 배제하기 위해, 다음과 같은 가정을 한다. 먼저, 모든 프로세서가 값 읽기 (1.)를 끝낸 다음에 연산 실행과 값...
-
junis3's profile image
junis3
April 23, 2023
Randomized Algorithm의 시간 복잡도 분석
Introduction 우리가 PS에 대해 배우면서 학습하는 대부분의 알고리즘은, 확률에 의존하지 않는다. 해당 알고리즘의 로직을 올바르게 구현했을 때에는 항상 정해진 시간 복잡도로 정답을 낸다. 현대 연구되는 많은 알고리즘은 그렇지 않다. 알고리즘은 확률적으로 오답을 낼 수도 있고, 정답과 적절히 가까운 근삿값만을 계산할 수도 있다. 또는 알고리즘의 수행 시간이 확률적으로 들쑥날쑥할 수 있다. 이러한 알고리즘의 가장 간단한 예시로는 피벗을 무작위로 잡는 퀵 소트 알고리즘이 있다. 무작위 알고리즘 (Randomized algorithm) 가운데, 항상 정답을 내는 것이 보장된 알고리즘을 Las Vegas...
-
junis3's profile image
junis3
August 22, 2022
PBFT Consensus Algorithm
합의 알고리즘 합의 알고리즘이란, 즉 몇 개의 노드로 이루어진 네트워크가 있을 때, 이들을 합의에 이르게 할 수 있는 알고리즘을 말한다. 이는 블록체인이 세상에 등장하기 전부터도 분산 컴퓨팅 시스템에 대해 연구되었던 주제이지만, 블록체인이라는 개념의 등장과 함께 새로운 국면을 맞이하기 시작한다. 실제로 블록체인 또한 잘 정의된 연산을 실행한 결과가 무엇인지에 대한 의견을 모으는 과정의 반복이다. 의견을 제출하는 모든 컴퓨터(노드)가 충분히 빠른 시간 안에 올바른 결과를 내는 것이 이상적이지만, 현실에서는 그렇지 않기 때문에 합의 프로토콜이 필요하다. 프로토콜을 평가하는...
-
junis3's profile image
junis3
June 19, 2022
Euler Tour 테크닉
문제 상황 다음과 같은 문제를 생각해 보자. (루트가 있는) 트리 $T$가 있다. 모든 정점은 초기에 $0$의 가중치를 가지고 있다. 이 때, 다음 두 종류의 질의를 처리해보자. 정점 $v$와 새로운 가중치 $x$가 입력으로 주어질 때, 정점 $v$의 가중치를 $x$로 바꾼다. 정점 $x$와 $x$의 모든 후손들(즉, 정점 $x$를 루트로 한 부트리의 정점들)의 가중치의 합을 구한다. 생각할 수 있는 가장 쉬운 풀이들은 $arr[x]$를, 정점 $x$의 가중치로 정의한다. 1번 질의는 상수 시간에 처리할 수 있다. 2번 질의에서 일일히 정점...
-
junis3's profile image
junis3
February 18, 2022
세그먼트 트리의 응용
세그먼트 트리 세그먼트 트리는 수열에 다양한 구간 질의를 빠르게 온라인으로 처리할 수 있게 하는 자료구조이다. 만약 세그먼트 트리에 대해 접해본 적이 전혀 없다면, 네 편의 강의 #1, #2, #3, #4를 참조하라. 세그먼트 트리를 설명할 때에 가장 흔하게 쓰이는 연습문제는 다음과 같다. 문제 1 수열 $A[0], \cdots, A[N -1]$ 이 있다. 이 수열에 질의를 고속으로 처리해야 한다. 질의의 종류는 아래와 같다. 두 수 $i, k$ 가 입력으로 주어진다. 이 때, $A[i]$ 를 $k$만큼 증가시켜라. 두 수...
-
junis3's profile image
junis3
January 16, 2022
XOR MST
XOR MST 다음과 같은 완전 그래프를 생각해 보자. 그래프의 정점은 $V$개이다. 각 정점에는 0 이상의 정수 가중치가 붙어 있다. 간선의 가중치는 간선이 잇고 있는 두 정점의 가중치의 XOR 값이다. # 는 이 그래프의 MST를 구하는 문제이다. 이 문제는 cs71107님의 XOR 관련 문제를 푸는 접근법들에도 나왔듯 자릿수가 큰 비트부터 내려가면서 일종의 그리디 알고리즘을 사용하게 된다. 가중치의 범위가 $2^{30}$이므로, 30번째 비트부터 생각해 보자. 어떤 정점의 가중치는 $2^{30}$ 미만일 것이고, 어떤 정점의 가중치는 $2^{30}$ 이상일 것이다. 가중치가 $2^{30}$...
-
junis3's profile image
junis3
April 19, 2021
Union Find의 시간 복잡도 증명
Union Find Union Find 또는 Disjoint Set이라고 불리는 자료구조는 여러 개의 원소를 포함하고 있는 집합들을 다루는 자료구조이다. 초기에, $N$개의 원소들과 $N$개의 집합들이 만들어져 있고, 각각의 집합은 서로 다른 원소 하나씩을 가지고 있다. 이 위에 다음과 같은 두 개의 연산을 할 수 있다. Union(x, y) : 원소 x가 속한 집합과, 원소 y가 속한 집합을 합친다. Find(x) : 원소 x가 어떤 집합에 속해있는지 반환한다. 보통 x가 속해있는 집합의 대표 원소 하나를 반환한다. struct dsu { dsu() {...
-
junis3's profile image
junis3
March 21, 2021
Ray Casting Algorithm의 이분 탐색을 이용한 응용
Ray Casting Algorithm (단순) 다각형과 점이 주어졌을 때, 점이 다각형 안에 있는지 판정하는 문제는 계산 기하학뿐 아니라 컴퓨터 그래픽스에서도 중요한 문제이다. 이를 해결하는 대표적인 알고리즘이 Ray casting algorithm이다. 가장 간단한 버전의 ray casting algorithm은 다음과 같은 문제를 푸는 데 사용된다. “2차원 좌표평면 위에 단순 다각형 $(x_0, y_0), \cdots, (x_N, y_N)$이 있다. 마찬가지로 2차원 좌표평면 위에 점 $P=(x, y)$가 주어질 때, 이 점이 다각형 안에 있는지 밖에 있는지 판정하라.” Ray casting algorithm은 이를 다음과 같은 아이디어로...
-
junis3's profile image
junis3
January 25, 2021
KMP 알고리즘과 Aho-Corasick 알고리즘
본 글에서는 대표적인 문자열 검색 알고리즘인 KMP 알고리즘과 Aho-Corasick 알고리즘에 대해 다루려 한다. 두 알고리즘이 알고리즘계에서 잘 알려진 이유는 둘 모두 평균 시간 복잡도뿐 아니라 최악의 경우 시간 복잡도가 극적으로 개선되었기 때문이다. 두 알고리즘 모두 실제로는 다이나믹 프로그래밍의 한 예시일 뿐임에도 실제로는 어려운 알고리즘으로 생각되고 있었다. (내가 그랬다..) 풀고 싶은 문제 우리가 두 알고리즘을 이용해 풀고 싶은 문제는 아래와 같다. 1) 아주 긴 문자열 $S$ 와 짧은 문자열 $T$ 가 주어진다. $S$ 의 길이는 $N$,...
-
junis3's profile image
junis3
March 21, 2020
k번째 최소 컷 찾기
간선에 가중치가 있는 방향 그래프 $G=(V, E)$를 생각해 봅시다. 시작점 $s \in V$와 끝점 $t \in V$가 주어질 때, $s$와 $t$가 서로 다른 컴포넌트에 있게 되도록 몇 개의 간선을 지울 때, 지우는 간선의 가중치의 합을 최소화하는 문제를 우리는 최소 컷(minimum cut) 문제라고 부릅니다. 이 문제는 최대 유량 최소 컷 정리에 의해 최대 유량 문제로 변형되고, Dinic 알고리즘을 사용한다면 $O(V^2 E)$의 시간 복잡도에 해결할 수 있습니다. 또한, 최대 유량 알고리즘을 수행한 후 시작점 $s$에서 유량이 남아...
-
junis3's profile image
junis3
February 19, 2020
De Bruijn 수열
De Bruijn 수열 당신은, 친구에게 $1$에서 $K$까지의 수들을 나열한 원형 수열(끝 글자와 첫 글자가 이어지는 수열)을 선물로 받았다. 그런데 이 수열은 신기한 성질을 가지고 있다. 이 수열에서 길이 $N$인 연속한 부분수열들을 모두 나열한다. 물론 원형 수열이기 때문에 그런 수열의 개수는 수열의 길이와 같다. 이 때, 이렇게 모은 부분수열의 모음이 그러면 $1$에서 $K$까지의 수들로 만든 모든 길이 $N$의 수열의 모음과 같았다! 그런 수열을 de Bruijn(‘jin’이 아니라 ‘ijn’임에 유의하자. 드 브루인이라고 읽는다.) 수열이라 한다. 예를 들어 $K...
-
junis3's profile image
junis3
October 20, 2019
Wavelet Tree
Wavelet Tree란? Wavelet tree란, 문자열을 저장하는 자료구조입니다. 이진 트리 형태로, 문자열의 길이 $L$에 대해 $L + o(L)$의 메모리를 사용하여(이런 특성이 있는 자료구조를 간결한 자료구조(succinct data structure)라고 합니다) 아래 두 연산을 지원합니다. $\mathbf{rank}_c(x)$: 문자열의 첫 인덱스부터 $x$번째 인덱스까지 문자 $c$가 등장하는 횟수를 반환합니다. $\mathbf{select}_c(x)$: 문자 $c$가 $x$번째로 등장하는 인덱스를 반환합니다. Wavelet이라는 이름은 신호를 재귀적으로 저주파수와 고주파수로 나누어 분해하는 wavelet transform의 이름에서 가져왔습니다. Wavelet tree의 구조 이 문단에서는 일반적인 wavelet tree의 개략적인 구조만을 다룹니다. 구조를 이해하셨다면 다음...