동아리 내에서 진행되는 알고리즘 스터디 정리본입니다. delena0702 codingstarfish님과 함께 진행하였습니다.

이전 스터디...

어쩌다 보니 2, 3차에 대한 내용을 건너뛰게 되었습니다.
대략적으로 스터디 내용을 짚고 넘어가도록 하겠습니다.

2차

SCC(Strongly Connected Component), Network Flow - Edmonds-Karp, MCMF(Minimum Cost Maximum Flow), SPFA(Shortest Path Faster Algorithm)

A 26146번 즉흥 여행 (Easy)

시작점을 어떻게 골라도 모든 나라를 방문할 수 있는 경로가 있다는 소리는 전체 그래프가 하나의 사이클을 이루고 있다는 소리와 같다. 즉, 하나의 SCC로 이루어져 있는 것이다. SCC의 Property를 묻는 문제였다.

SCC를 구해주고, SCC의 개수가 1개인 경우에 Yes, 아닌 경우에 No를 출력해주었다.

B 4305번 성격 진단 테스트

모든 활동들을 분할하되, 각 그룹에는 어느 두 쌍을 골라도 두 활동 사이에 모순이 존재하도록 해야된다고 한다. 어느 두 쌍을 골라도 두 활동 사이에 모순이 생기기 위해서는 A보다 B가 좋고, B보다 C가 좋고, C보다 A가 좋은 경우여야 할 것이다. 즉 SCC에 속한 두 정점을 뽑는 경우라고 볼 수 있다.

두 A, B, C, D, E 중 A를 선택했다면, A→B, A→C, A→D, A→E 로 가는 간선을 그릴 수 있을 것이다. 이처럼 각 질문들에 따라 그래프를 구성하고 SCC를 찾아주면 된다. 또한 각 SCC별로 출력을 해주면 된다.

C 16902번 mex

기본 배열의 크기와 쿼리의 개수가 꽤 컸다. 쿼리를 빠르게 처리하기 위해 어떤 테크닉을 써야할까 고민하다가 다른 xor문제에서의 경험을 떠올려 Trie를 써보면 꽤 빠르게 처리할 수 있을 것 같았다. 따라서, 1과 0으로 이루어진 이진수를 나타내는 형태로 Trie를 구성해주었다.

전체 xor은 head에서 변수 하나 두고 거기에 계속 xor시키면 O(1)에 xor이 가능하다.

mex(A) 함수는 head에 여태까지의 xor해놓은 값에 해당하는 값과 같은 이진수를 따라 들어가는 것이 0을 따라가는 것과 같다. !!

D 11409번 열혈강호 6

열혈강호5와 같은 방식으로 아래와 같이 그래프를 모델링해주었다.

S - 직원 - 일 - T

최소 비용이 아닌 최대 비용이므로 비용과 역비용을 설정할 때 부호를 반대로 해주었다.

E 8992번 집기 게임

우선 선분의 개수가 적으므로 선분 교차 여부를 모두 판단하기로 했다. 만약 교차가 이루어진다면 두 선분을 노드로 놓았을 때, 연결되었다고 할 수 있을 것이다. 이에 따라 그래프를 아래와 같이 모델링해주었다. (조건에 의해 가로줄과 세로줄간에만 교차가 일어난다)

S - 세로줄 - 가로줄 - T (세로줄과 가로줄 사이는 교차 관계임)

비용은 교차가 이루어진 두 선분의 weight 곱으로 설정해주면 된다. 또한, 비용과 역비용을 설정할 때, 우리는 최대 비용을 구해야하므로 기존과 부호를 반대로 설정해주면 된다.

Comment

스터디 이후가 시험기간이라 작성하지 못했다는 핑계를 살짝 대봅니다.

3차

DP Optimization

• Divide & Conquer Optimization delena0702
• Slope Trick dldyou
  • 25019번 날다람쥐
    17점에서 틀려서... 글을 못 쓰고 있는 이유 중 가장 큰... 맞춘 이후에 이 문제에 대해 따로 올리도록 하겠습니다.

DP최적화에 대해 서로 설명 이후 팀 연습을 진행했습니다.

실제 팀 대회처럼 하나의 PC로만 코드를 작성하도록 하였습니다. D번이 처음에 진짜 만만해보였는데 생각하면 생각할수록 어렵더라구요...

Comment

X

4차

HLD(Heavy-Light Decomposition)

dldyou

Preceding Algorithm

ETT(Euler Tour Technique) Segment Tree

Purpose of HLD

트리의 경로에 대한 쿼리를 빠르게 처리하기 위해 -> 세그먼트 트리를 사용할 수 있는 형태로 만들기 위해(트리는 비선형 자료구조이므로 그 자체로는 세그먼트 트리를 사용할 수 없다)

결국 만들려는 형태는 ETT에서와 같이 구간으로 나타나는 형태이다.

Heavy Edge & Light Edge

HLD는 트리의 간선들을 Heavy Edge 와 Light Edge로 분리한다. 무거운 간선 / 가벼운 간선 인데 그러면 뭐가 무겁다는 것일까?

부모 정점에서 자식으로 가는 간선 중에서 자식들 중 서브트리의 크기가 가장 큰 정점을 있는 간선은 Heavy Edge가 된다. 나머지는 Light Edge이다. 여기서 인접하는 Heavy Edge는 하나의 체인으로 묶고, 각각의 Light Edge도 하나의 체인으로 생각한다.

이때, 트리의 정점이 $N$개라면 임의의 노드 2개를 골랐을 때의 경로는 $O(logN)$개의 체인만을 이용해 나타낼 수 있다. 따라서 트리의 경로를 $O(logN)$개의 체인을 이용해 나타낼 수 있게 되었으니 $O(logN)$의 구간 쿼리로 바꿀 수 있다는 말과 같다. 세그먼트 트리를 이용하면 $O(log^2N)$에 처리할 수 있게 된 것이다.

Problems

추가 예정입니다

Reference
https://justicehui.github.io/hard-algorithm/2020/01/24/hld/
https://justicehui.github.io/hard-algorithm/2019/03/30/HLD-it-can-be-easy/
https://anz1217.tistory.com/135

FFT(Fast Fourier Transform)

delena0702 님이 작성한 문서와 발표에 기반하여 작성하였습니다.

Euler's Formula

$e^{ix}=cos(x)+isin(x)(x\in \R, i=\sqrt-1)$

DFT(Discrete Fourier Transform)

DFT는 이산적인 값들에 대해 푸리에 변환을 하는 것을 의미한다. FT는 $\int$을 이용하지만, DFT는 이 부분이 $\sum$이기에 컴퓨터의 행렬 연산으로 계산이 가능하다. 정의와 유사한 방식의 알고리즘 구현시 $O(N^2)$의 시간이 걸린다.

$X_k=\displaystyle\sum_{n=0}^{N-1}{x_ne^{-i(\frac{2\pi k}{N})n}}$
$e$의 지수부분은 오일러 공식을 통해 바꿔볼 수 있다.

결국 $e$부분의 의미는 복소평면에서의 회전이고, $N$개의 샘플링은 해당 회전이 $N$등분 된다는 말이다. 그리고 $mod$를 취할 수 있게 된다.

DFT의 결과를 표현해보자.
$a_0, a_1, ..., a_{n-1}$을 변환한 결과를 $b_0, b_1, ..., b_{n-1}$라고 한다면 아래와 같이 행렬식으로 나타낼 수 있다.

$x_k=w^k=e^{\frac{2\pi k}{n}}$

$\begin{cases} b_0=a_0(x_0)^0+a_1(x_0)^1+...+a_{n-1}(x_0)^{n-1} \\b_1=a_0(x_1)^0+a_1(x_1)^1+...+a_{n-1}(x_1)^{n-1} \\\vdots \\b_{n-1}=a_0(x_{n-1})^0+a_1(x_{n-1})^1+...+a_{n-1}(x_{n-1})^{n-1} \end{cases}$

$\begin{bmatrix}b_0\\b_1\\\vdots\\b_{n-1} \end{bmatrix} = \begin{bmatrix}w^0&w^0&\dots&w^0 \\w^0&w^1&\dots&w^{n-1} \\\vdots&\vdots&\ddots&\vdots \\w^0&w^{n-1}&\dots&w^1 \end{bmatrix} \begin{bmatrix}a_0\\a_1\\\vdots\\a_{n-1} \end{bmatrix}$

우리는 이 DFT를 이용해 다항식의 곱셈을 구할 것이다.

단순히 다항식의 곱을 구할 때에는 두 다항식의 최대 차수가 모두 $N$이라 가정하면 $O(N^2)$이 걸린다. 우리는 이보다 더 빠른 방법이 필요하다.

다항식의 곱을 구하는 새로운 방법에 대해 생각해보자. 1차 다항식을 생각해보면 그래프 위의 두 점만 알면 구할 수 있었다. $N$차 다항식도 마찬가지로 $N+1$개의 함수값만 알면 된다.

즉, 우리는 아래와 같이 다항식의 곱을 구할 수 있다.
1. 정해진 $x$값에 대해 $f(x)$를 구한다.
2. 구한 모든 $f(x)$를 곱한다. ($O(N)$)
3. 함수 값들을 이용해 다항식을 계산한다.

1의 과정은 DFT이고 3의 과정은 IDFT(Inverse DFT)이다. 즉, DFT와 IDFT를 $O(NlogN)$시간 내에 해결할 수 있다면, 다항식의 곱을 $O(NlogN)$에 해결할 수 있게 된다. 그 과정이 FFT이다.

FFT(Fast Fourier Transfrom)

FFT는 DFT를 Devide and Conquer을 이용해 $O(N^2)$에서 $O(NlogN)$으로 최적화한 알고리즘이다.

위의 DFT에서 홀수차항과 짝수차항으로 분리하여 식을 나타내어 보면 재귀적으로 DFT를 수행할 수 있게 된다. IDFT의 과정은 DFT를 하고 그 내적에서 역행렬을 곱해주는 과정이다. 역행렬의 경우 이미 계산과 normalization이 되어 있으므로 결과값을 곱해주기만 하면 된다.

주의사항

• FFT는 기본적으로 정수로 계산하는 알고리즘이 아니다. round 함수를 통해 정수 값으로 바꾸자.
• FFT 알고리즘의 입력 vector 크기는 $2^n$꼴이어야 한다.

Problems

10531 Golf Bot
Counting 개수를 FFT로 구하는 문제
15576 큰 수 곱셈 (2)
큰 수의 곱을 구하는 문제

Comment

PS에서 대부분이 이해하지 않고 그냥 쓴다는 FFT..

동아리 내에서 진행되는 알고리즘 스터디 정리본입니다. delena0702 codingstarfish님과 함께 진행하였습니다.