직장인의 개발 일기

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

https://www.acmicpc.net/problem/1761

[ 문제풀이 ]

문제 풀이 과정은 다음과 같습니다.

1. 각각의 노드들에 대해서 연결된 에지들을 list배열에 저장합니다.

2. 1번 노드를 루트 노드로 설정하고, 부모는 0, 깊이는 1로 설정합니다. 

3. 각 노드들의 부모, 깊이, 부모 노드까지의 거리를 각각 저장합니다.

4. 입력받은 노드들에 대해서 높이가 같아질 때까지 올라가고 그때까지의 거리를 저장합니다.

5. 노드들의 깊이가 같아졌을 때 같은 노드를 가리키고 있다면 break

6. 다른 노드를 가리키고 있다면 계속 올라가면서 5번을 반복합니다.

하지만 같은 깊이까지 한칸씩 올라가면 드는 시간이 최대 O(NM)이 걸리게 되므로 효율적이지 않습니다.

따라서, 깊이 정보를 $2^{i}$로 저장하게 된다면 O(MlogN)의 시간으로 단축할 수 있습니다.

첫 번째 코드는 같은 깊이까지 한 칸씩 올라가는 코드이고, 두 번째 코드는 $2^{i}$칸씩 올라가는 코드입니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/1708

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 읽어보고 오시길 추천드립니다!

https://rudalsd.tistory.com/66?category=1064608

간단하게 문제 풀이 순서에 대해서 알려드리겠습니다.

1. y값이 가장 작은 점을 기준점으로 선택합니다.

2. 기준점을 기준으로 반시계 방향으로 점들을 정렬합니다.

3. 1번 점과 2번 점보다 다음 점이 반시계 방향에 있다면 stack에 넣고, 그렇지 않다면 2번 점을 빼고 다시 3번의 과정을 반복합니다.

[ 소스 코드 ]

컨벡스 헐 알고리즘(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에 넣어줍니다.

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

https://www.acmicpc.net/problem/1086

[ 문제풀이 ]

모든 조합에 대해 문제를 푼다면 O(15!)이므로 2초 안에 풀 수 없습니다. 따라서 비트 마스킹을 통해 중복으로 쓰이는 순열들을 저장해서 씀으로써 시간을 줄일 수 있습니다.

또한 $123456$의 나머지를 구할 때는 (123*1000) + 456 이므로 ( ( 123 % K ) * ( 1000 % K ) ) % K + 456 % K로 구해주시면 됩니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/17371

[ 문제풀이 ]

생각을 조금만 해보면 쉽게 풀 수 있는 문제입니다.

점들 중 하나를 골라 다른 점들과 거리를 비교했을 때 가장 가까운 점은 거리가 0, 가장 먼 거리가 d일 때 평균 거리는 $ \frac{d}{2}$입니다. 따라서 이들 중 가장 짧은 거리를 구해주면 됩니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/14428

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 읽고 오시면 좋습니다!!

https://rudalsd.tistory.com/51?category=1073064 

이 문제는 가장 작은 수의 인덱스를 출력해야 하는 문제이기 때문에 node struct를 만들어서 숫자와 인덱스를 저장합니다. 나머지는 다른 세그먼트 트리와 같은 방식으로 풀어주면 됩니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/13977

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

https://rudalsd.tistory.com/61?category=1064608 

먼저 $\binom{N}{K}$는 다음과 같이 나타낼 수 있습니다.

$\binom{N}{K} = \frac{N!}{(N-K)!K!}$

그리고 페르마의 소정리를 이용하여 mod $m$에서 어떤 수를 $a$로 나눈다는 뜻은 $a$의 역원을 곱한다는 뜻과 같습니다. 따라서 $m$이 소수일 때, $a^{m-1}\equiv 1($mod $m)$이고, $a\times a^{m-2}\equiv 1($mod $m)$이므로 mod $m$에서 $a$에 대한 곱셈의 역원은 $a^{m-2}$입니다.

따라서, 

$\frac{N!}{(N-K)!K!} \equiv N!\times ((N-K)!K!)^{m-2}($mod $m)$

이 됩니다.

분모의 수로 나누는 방법 대신 $m-2$제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.

이 때 $m$의 값이 $1,000,000,007$로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.

[ 소스 코드 ]

https://www.acmicpc.net/problem/11689

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다!

https://rudalsd.tistory.com/59?category=1064608 

위의 공식을 이용하여 ans에 n을 대입한 후 n에 대하여 어떠한 수 i로 나누어지면 ans = ans - ans / i를 통해서 답을 구할 수 있습니다.

이때 i * i <= n까지 구하는 이유는 n의 제곱근은 i보다 작거나 같기때문입니다.

하지만 마지막에 n이 1이 아니라면 남은 n은 소수이므로 n이 1이 아닐 때 마지막으로 ans = ans - ans / n을 해주면 답을 구할 수 있습니다.

[ 소스 코드 ]

페르마의 소정리(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)$를 만족합니다.