직장인의 개발 일기

뤼카의 정리 (Lucas' theorem)는 다음과 같이 정리할 수 있습니다.

$_{n}\textrm{C}_{r}$을 $m$으로 나눈 나머지를 구하고자 할 때 사용할 수 있습니다.

$\binom{n}{r} = \prod_{i=1}^{k}\binom{n_{i}}{r_{i}}\; mod\; p$

1. $_{n}\textrm{C}_{r}$의 $n$과 $r$을 각각 $m$진수로 표현합니다.

2. $m$진수로 표현된 두 수를 각 자릿수에 맞춰 조합을 계산하고, 그 값들을 모두 곱해 $m$으로 나눈 나머지 값이 최종값입니다.

3. 이때, $n < r$이면 값은 0입니다.

1. 이분 매칭(Bipartite Matching)이란?

정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향이 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다.

2. 이분 매칭(Bipartite Matching)동작 원리

우선, 정점 A는 정점 1을 점유할 수 있습니다. (총 매칭 수 : 1)

그 다음 정점 B는 정점 1을 점유하려고 합니다. 그런데 정점 A가 이미 정점 1을 보유하고 있으므로 A는 다른 정점을 점유하러 경로를 다시 찾습니다. 정점 3이 비어있으므로 A는 정점 3을 점유합니다. (총 매칭 수 : 2)

정점 C는 정점 5를 점유합니다. (총 매칭 수 : 3)

정점 D는 정점 3을 점유하려고 합니다. 그런데 정점 A가 이미 정점 3을 점유하고 있으므로 A가 다른 경로를 찾아 정점 1의 점유를 시도합니다. 그런데 정점 1 역시 정점 B가 점유하고 있으므로 B는 다른 경로를 찾아 비어있던 정점 2를 점유합니다. (총 매칭 수 : 4)

정점 E가 정점 2를 점유하려고 합니다. 그러나 정점 E는 더이상 매칭할 수 없습니다. 2를 점유하면 B가 경로를 다시 찾을 것이고 또 A가 다시 경로를 찾게되며 또 D가 다시 경로를 찾고 계속해서 반복되기 때문에 매칭이 불가능합니다.

따라서 최종 매칭 수는 4가 됩니다.

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란?

어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 최장 증가 부분 수열(Longest Increasing Subsequence)이란 '증가하는 부분 수열' 중 가장 긴 수열을 의미합니다.

2. 최장 증가 부분 수열(Longest Increasing Subsequence)동작 원리

O(NlogN)의 시간복잡도가 걸리는 lower_bound를 활용하여 구할 수 있습니다.

위와 같은 수열을 예로 들어서 설명드리겠습니다.

수열의 첫 수를 LIS에 넣어줍니다.

LIS의 마지막 수보다 현재 숫자가 더 크다면 LIS에 넣어줍니다.

그렇지 않다면 lower_bound를 활용해 현재 수보다 크거나 같은 수가 있는 곳의 index의 값을 현재 수로 바꿔줍니다.

위와 같은 방식으로 LIS를 채워주면 다음과 같은 결과를 얻을 수 있습니다.

유의할 점은 위의 방식으로 LIS를 구하면 길이는 구할 수 있지만 부분수열 자체는 구할 수 없습니다.

1. 단절선(Articulation Bridge)이란?

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말합니다.

2. 단절선(Articulation Bridge)동작 원리?

단절선(Articulation Bridge)의 동작 원리는 단절점(Articulation Point)의 동작 원리와 비슷합니다.

https://rudalsd.tistory.com/113

단절점(Articulation Point)과의 차이점은 루트노드가 사라진 것과 부모 노드를 제외한 나머지 노드들이 우회 간선을 이용해서도 현재 노드에 도착하면 안되므로 등호가 빠진 것입니다.

1. 단절점(Articulation Point)이란?

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말합니다.

2. 단절점(Articulation Point)동작 원리?

dfs를 활용하여 O(V+E)의 시간복잡도로 문제를 해결할 수 있습니다.

위 그래프의 방문 순서에 따라 id값을 매깁니다. id값은 1부터 시작하여 1씩 증가합니다. 방문 순서는 1→3→4→5→2→6이 됩니다.

방문하지 않은 노드를 방문할 때마다 dfs를 수행하여 단절점을 확인해보겠습니다.

단절점의 발견 조건은 특정 i번 노드에서 자식 노드들이 노드 i를 거치지 않고 노드 i보다 낮은 id값을 가진 노드로 갈 수 없다면 단절점입니다. 또한 현재 노드가 루트 노드일 때 자식 노드가 2개 이상이라면 단절점입니다.

4번과 5번 노드는 3번 노드를 거치지 않으면 1번 노드로 가지 못합니다. 따라서 3번 노드는 단절점입니다.

위와 같은 방법으로 2번 노드와 6번 노드는 5번 노드를 거쳐야하고, 6번 노드는 2번 노드를 거쳐야하므로 2번 노드와 5번 노드 또한 단절점입니다.

1. 강한 연결 요소 추출 알고리즘(Strongly Connected Component)이란?

방향성이 존재하는 그래프에서 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우 즉, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말합니다.

2. 강한 연결 요소 추출 알고리즘(Strongly Connected Component)동작 원리?

dfs를 활용하여 O(V+E)의 시간복잡도로 문제를 해결할 수 있습니다. 코사라주 알고리즘과 타잔 알고리즘이 있지만 그 중 더 빠른 타잔 알고리즘을 통해 SCC를 찾겠습니다.

위 그래프의 방문 순서에 따라 id값을 매깁니다. id값은 0부터 시작하며 1씩 증가합니다. 방문 순서는 0→1→2→3→4→5→6→7이 되며 방문할 때마다 해당 정점을 스택에 집어 넣습니다.

각 정점에 대하여 dfs를 수행하여 SCC를 추출해보겠습니다. SCC의 발견 조건은 '자신의 자식 노드(id값이 상대적으로 높을 때)들이 본인의 부모 노드(id값이 상대적으로 낮을 때)로 갈 수 있는 경우의 수가 없는 경우' 이며 이때 스택에서 본인보다 위에 있는 모든 노드들을 빼주고 scc에 넣어주면 됩니다.

7번 노드는 돌아갈 수 있는 부모 노드가 없으므로 SCC 발견 조건을 만족합니다. 따라서 stack에서 본인이 나올 때까지 숫자를 뽑습니다. stack의 top이 현재 7이므로 7만 빼서 ans에 넣고 계속 진행합니다.

다시 6번 노드에서 4번 노드로 가면 4번 노드는 더 이상 부모 노드로 갈 수 없습니다. 따라서 stack에서 4가 나올 때까지 숫자를 뽑아줍니다.

마지막으로 3번 노드에서 0번 노드로 가고 0번 노드는 더이상 부모 노드가 없기 때문에 stack에서 0이 나올 때까지 숫자를 뽑아줍니다.

모든 SCC를 발견해서 스택이 비었고, 결과적으로 3개의 SCC가 나옵니다.

이 알고리즘을 이용하여 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/75

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란?

위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방문해야 현재 노드에 방문할 수 있습니다. 위상 정렬 알고리즘은 선행 노드가 무조건 수행되어야 하기 때문에 사이클이 발생하지 않습니다.

2. 위상 정렬 알고리즘(Topological Sort Algorithm) 동작 원리?

위상 정렬이란 선행 노드가 수행이 되었을 때, 즉 진입 차수가 0일 때 현재 노드를 방문할 수 있습니다.

위 그래프의 진입 차수는 다음과 같습니다.

이때 진입 차수가 0인 노드들을 queue에 넣어줍니다.

queue에서 숫자를 하나씩 빼주면서 연결되어 있는 노드의 진입 차수를 하나씩 빼주면서 진입 차수가 0이 되면 queue에 넣어줍니다.

위와 같은 방법으로 반복해줍니다.

위상 정렬을 이용하여 다음 문제들을 풀 수 있습니다.

https://rudalsd.tistory.com/73?category=1064612 

KMP 알고리즘은 문자열을 탐색하는 알고리즘입니다. 보통 ctrl + f를 이용하여 원하는 문자열을 찾을 때 많이 쓰는 방식입니다.

단순하게 길이가 N인 문자열의 처음부터 끝까지 문자열의 길이가 M인 문자열과 비교한다면 O(NM)의 시간이 걸립니다. 하지만 KMP알고리즘을 쓴다면 O(N + M)의 시간으로 문제를 풀 수 있습니다.

[ 동작 원리 ]

먼저 찾고자 하는 문자열 P에 전처리를 해주어야 합니다.

문자열 ABABABAC의 전처리를 예로 들어보겠습니다.

idx가 1일 때 겹치는 문자열의 최대 개수는 0개입니다.

idx가 2일 때 겹치는 문자열의 최대 개수는 1개입니다.

idx가 3일 때 겹치는 문자열의 최대 개수는 2개입니다.

위 방법을 계속 반복하면 위와 같은 결과가 나옵니다.

하지만 idx가 7일 때 문자열이 일치하지 않으므로 cur의 값을 당겨줄 필요가 있습니다. 

cur = Pi [cur-1]을 대입해서 Pi[ 5 - 1 ]은 3이므로 위와 같이 당겨줄 수 있습니다.

위와 같은 방법으로 계속 반복면 위와 같은 결과를 얻을 수 있습니다.

이렇게 Pi를 완성시켰습니다.

이제는 이 Pi를 활용해서 KMP를 구해주면 됩니다.

cur이 8일 때 문자열이 다릅니다. 이때 Pi[7] = 6이므로 cur에 6을 대입 후 반복해줍니다.

cur이 6일 때 문자열이 다릅니다. 이 때 Pi [5] = 4이므로 cur에 4를 대입 후 반복해줍니다.

위와 같이 반복하다 보면 일치하는 문자열을 발견할 수 있습니다. 이때 cur은 P.size()-1의 값을 가지고, Pi [cur]은 0이므로 다음 문자열부터 다시 검색을 시작해주면 됩니다.

위 알고리즘을 이용하여 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/70

컨벡스 헐 알고리즘(Convex Hull Algorithm)을 이용해서 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/67

1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란?

컨벡스 헐 알고리즘은 2차원 평면에 여러 개의 점이 있을 때 그 점들 중 일부를 사용하여 볼록 다각형을 만들고 그 안에 나머지 모든 점을 포함시키는 것을 의미합니다.

위의 그림을 컨벡스 헐 알고리즘을 통해 선을 그으면 다음과 같이 표시할 수 있습니다.

위를 볼록 껍질이라고 하고, 점 5개로 이루어져있습니다.

이를 알고리즘을 통해 구현할텐데 그 중에서도 O(NlogN)에 구현할 수 있는 그라함 스캔(Graham's Scan) 알고리즘을 알아보도록 하겠습니다.

2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리?

그라함 스캔(Graham's Scan)을 사용하기 전에 두가지 전처리가 필요합니다.

1. 우선 가장 아래에 있는 점들 중 가장 왼쪽에 있는 점을 기준점으로 잡습니다.

2. 이 기준점을 바탕으로 모든 점에 대해 반시계방향에 있는 순서대로 정렬을 합니다.

이 과정을 마친 후 다음과 같이 진행하면 됩니다.

먼저 스택에 1번과 2번 점을 넣습니다.

스택에서 2번 점과 1번 점을 뽑아낸 후 next 점과 ccw를 하여 반시계방향에 있는지(ccw > 0)체크한 후 반시계방향에 있다면 볼록껍질이 될 수 있다는 뜻이고, 뽑아낸 2번 점을 다시 넣고 next를 넣어줍니다.

같은 방법을 통해 next를 또 스택에 넣습니다.

이번에는 first - second 직선보다 first - next 직선이 오른쪽에 있으므로 ccw 값은 0보다 작게 나옵니다. 그렇다면 second 점은 볼록 껍질의 점이 될 수 없으므로 second는 다시 스택에 넣지 않고 위 과정을 반복합니다.

ccw값이 0보다 크므로 next를 stack에 넣어줍니다.

이러한 과정들을 모두 거치면 다음과 같은 결과를 얻을 수 있습니다.

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다.

$a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족하고,

만약 $p$가 소수이고, $a$와 $p$가 서로소이면 $a^{p-1}\equiv 1($mod $p)$를 만족한다.

수학적 귀납법을 이용하여 위의 식을 증명해보겠습니다.

먼저, $0\leq a\leq p-1$ 범위의 정수에서만 증명해도 충분합니다. 그 이유는 $a$를 $p$로 나눈 나머지는 항상 $0$보다 크거나 같고 $p-1$보다 작거나 같기 때문입니다.

1. $a = 0$일 때

$a$가 $0$인 경우에는 $0^{p} = 0\equiv 0(mod$ $p)$

2. $a = k$일 때 성립한다고 가정하고 $a = k+1$일 때

$a=k$일 때 성립한다고 가정했으므로, $k^{p}\equiv k(mod$ $p)$를 만족합니다.

이항 정리를 사용하여 $a = k + 1$일 때도 성립함을 증명합니다.

$(k+1)^{p}=\sum_{i=0}^{p}\binom{p}{i}k^{i}$

이때 이항 계수의 정의에 의해서

$\binom{p}{i} = \frac{p!}{(p-i)!i!}=\frac{p(p-1)\cdot \cdot \cdot(p-i+1)}{i(i-1)\cdot \cdot \cdot 1}$

이고, 위 식은 $1\leq i\leq p-1$일 때 $p$의 배수이므로 p로 나누면 없어지게 됩니다. 또한, $i$가 $0$ 또는 $p$이면 1입니다. 따라서,

$(k+1)^{p}\equiv \binom{p}{0}k^{0}+\binom{p}{p}k^{p} = k^{p}+1\equiv k+1($mod $p)$

$a=k+1$일 때도 성립함을 증명했습니다. 따라서,따라서, $a\geq 0$에 대하여 $a^{p}\equiv a($mod $p)$를 만족합니다.

$a$와 $p$가 서로소인 경우는 다음과 같이 유도할 수 있습니다.

$a^{p}\equiv a($mod $p)$이므로, $a^{p} - a = a(a^{p-1}-1)$은 $p$로 나누어 떨어집니다. 이때, $a$와 $p$가 서로소이므로 $a^{p-1}-1$은 $p$로 나누어 떨어집니다.

따라서, $a^{p - 1}\equiv 1($mod $p)$를 만족합니다.