[실전 알고리즘] 0x0B강 - 수학_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x12강 - 수학에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

즐거운 수학시간입니다.

 

이 강의에서 어디까지 다뤄야하나 고민을 많이 했습니다. 아마 코딩테스트에서는 이 수준 안에서 나오겠지만, 더 나아가 대회를 나가볼 생각이 있는 분이 계시다면 이 강의에서 다루는 내용 이외에도 확장된 유클리드 호제법, 모듈로 역수, 중국인의 나머지 정리, 오일러 pi 함수, 페르마의 소정리, 오일러의 정리 등을 추가로 공부하셔야 합니다.

 

이번 강의에서 다루는 수학은 코딩테스트를 통과하기 위한 정도의 수학일 뿐이지 앞으로 프로그래밍을 할 때 이 정도만 알고 있으면 충분하다는 뜻이 절대 아닙니다.

 

컴퓨터 공학 학부 과정에서는 보통 이산수학, 선형대수학, 미적분학, 확률과 통계 정도는 배웁니다. 물론 어떤 분야에 일하느냐에 따라 수학이 쓰이는 정도가 다르겠지만 위의 네 과목 정도는 기본기로 가지고 있는 것이 좋습니다.

 

엄밀한 것을 좋아하는 분들을 위해 이번 강의에서는 각 알고리즘이 왜 성립하는지를 꽤 상세하게 다루고 있습니다. 단 증명이 너무 어려운 경우에는 증명을 생략했습니다. 수학적 증명에 익숙하지 않으면 잘 이해가 가지 않을 수도 있는데, 증명이 크게 중요한 것은 아니니 잘 이해가 가지 않으면 그냥 받아들이고 사용하셔도 아무 상관 없습니다.

 

 

학창시절 배웠던 수학의 기억을 되살려봅시다. 소수는 1과 자신으로만 나누어 떨어지는 수입니다.

 

$N$이 소수인지 판단하는 함수를 만들어봅시다. 가장 쉬운 방법은 2부터 $N-1$중에 $N$을 나누는 수가 있는지 판단하는 방법입니다. 지금까지의 과정을 잘 따라왔다면 굉장히 쉽게 구현할 수 있을 것입니다. 이 방법의 시간복잡도는 $O(N)$입니다.

 

 

그런데 수학적 관찰을 한 가지 하게 된다면 시간복잡도를 $O(\sqrt N )$ 으로 떨굴 수 있습니다.

 

이전에 작성했던 코드를 생각해보면 결국  1과 $N$을 제외한 $N$의 약수 중에서 제일 작은 $i$를 만날 때 바로 탈출합니다. 그런데 $i$가 $O(\sqrt N )$보다 클 수 있을까요? 그렇지 않음을 증명해봅시다.

 

 

 

"1과 $N$을 제외한 $N$의 약수가 존재할 때, 그 중에서 최솟값을 $a$라고 하자. 이 때 $a \leq O(\sqrt N )$이다." 라는 명제를 증명하면 됩니다.

 

귀류법을 이용해 명제를 증명합니다. $a > \sqrt N$이라고 가정하고 모순을 찾아봅시다. 우선 $b = N / a$ 가 $N$의 약수임은 자명합니다. 그리고 1과 $N$을 제외한 $N$의 약수 중에서 최솟값이 $a$이므로 $b$는 $a$보다 크거나 같아야합니다. 그런데 $a > \sqrt N$ 이므로 $b = N / a < \sqrt N$  이기에 모순입니다. 그러므로 $a \leq \sqrt N$  입니다.

 

 

앞에서 증명한 명제로부터 $i$를 2부터 $N-1$까지 돌릴 필요 없이 $i^2$ 가 $N$ 이하일 때 까지 돌리면 됨을 알 수 있습니다. 이를 통해 시간복잡도를 $O(\sqrt N)$ 으로 줄일 수 있습니다.

 

for문 안에서 탈출 조건을 i <= sqrt(n); 으로 쓰기 쉽습니다. sqrt 함수가 C언어에 존재하긴 하지만 해당 함수는 실수를 인자로 받는 함수이기 때문에 실수오차가 발생할 수 있습니다. 예를 들어 이전에 double이 $10^+1$을 저장할 때 그냥 $10^$로 저장하듯 sqrt($10^$)와 sqrt($10^+1$)이 같은 값을 반환합니다.(엄밀히 말해서 C++11 이후에는 정수 타입이 인자로 overloaded되었기 때문에 해당 문제가 발생하지 않습니다. 그러나 그냥 혼동을 방지하기 위해 sqrt 함수 사용을 피합시다.)

 

앞의 소수 판정법은 $N$이 소수인지를 판단하는 알고리즘입니다. $N$이하의 소수를 모두 찾는 알고리즘은 어떻게 만들 수 있을까요?

 

가장 간단한 방법은 이전의 소수 판정법을 1부터 $N$까지의 모든 수에 대해 다 해보는 것입니다. $N  = 5,000,000$일 때 BOJ 서버 기준으로 1.8초 정도 걸립니다.

 

그러므로 $N$이하의 소수를 모두 찾기 위해 그냥 소수 판정법을 $N$번 돌려도 아무 상관 없지만 에라토스테네스의 체라는, $N$이하의 소수를 모두 찾는 간단한 알고리즘을 소개해드리겠습니다. ($N  = 20,000,000$일 때 BOJ 서버 기준으로 0.13초가 걸렸기 때문에 앞의 방법과 속도는 거의 차이가 없으나 메모리를 13~40배 정도 절약할 수 있습니다.)

 

 

 

 

 

 

 

 

구현은 엄청 어렵지는 않습니다. 다만 처음 짜보면 좀 헷갈리긴 할거에요.

 

현재 구현한 이 에라토스테네스의 체는 아직 좀 느립니다. 그냥 소수 판정법을 $N$번 돌리는 방법보다 더 느려요. 그렇기에 최적화를 시켜봅시다.

 

첫 번째 최적화입니다. 현재 코드에서는 $i = k$일 때 $2k, 3k, 4k,$…를 모두 false로 둡니다. 그러나 $2k,3k,4k, … ,(k-1)k$ 는 각각 $2, 3, 4, …  , k-1$으로 나누어 떨어지기 때문에 이들은 $k$보다 더 작은 소인수가 존재합니다. 그러므로 이들은 현재 $i = k$ 에서 신경쓰지 않더라도 이전에 다른 $i$ 값에서 이미 false로 바뀌어 있음을 알 수 있습니다. 그러므로 $2k,3k,4k, … ,(k-1)k$ 에 대해서는 굳이 false로 바꿀 필요가 없는 것이고, $j$가 $2i$부터 시작할 필요 없이 $i^2$부터 시작하면 된다.

 

두 번째는 최적화 1에 따라 $i^2$이 $N$보다 커지면 더 이상 아무 값도 바꾸지 않으므로 $i^2$이 $N$이하일 때 까지만 반복문을 돌리면 된다는 점입니다.

 

마지막으로 state 배열은 어차피 true 혹은 false만 저장하므로 원소 하나당 4byte 공간이나 잡아먹는 int로 두지 말고 GCC 기준 원소 하나당 1 bit씩만 잡는 vector<bool>로 잡으면 됩니다. (단 bool 배열은 원소 하나당 1byte 공간을 차지합니다.)

 

마지막 최적화가 단순히 메모리만 절약하는 것 같지만, 공간을 적게 쓰면서 cache hit rate가 올라간다는 장점도 같이 있기 때문에 속도의 개선에도 큰 영향을 줍니다.

 

최적화 3가지를 모두 적용하고 나면 코드가 위와 같이 바뀝니다. 최적화를 끝내고 나면 $N = 20,000,000$일 때 BOJ 서버 기준에서 0.63초에서 0.13초로 줄일 수 있습니다.

 

정리를 해봅시다. $N$이하의 소수를 모두 찾고 싶을 때 에라토스테네스의 체를 사용하면 각각의 수를 소수인지 판정하는 것 보다 훨씬 빠르게 동작합니다. 그리고 에라토스테네스의 체를 사용할 경우, 앞에서 언급한 3가지 최적화를 하면 더욱 빠르게 동작하지만 최적화를 하지 않아도 시간 초과가 발생하지는 않을 것입니다.

 

최적화를 한 에라토스테네스의 체는 50,000,000 이하의 소수를 대략 0.35초안에 찾고, 100,000,000 이하의 소수를 대략 0.72초 안에 찾습니다. (정확한 시간복잡도는 $O(NlglgN)$입니다. 시간복잡도에 대한 증명은 굉장히 복잡하기 때문에 생략하겠습니다.)

 

소인수분해의 유일성에 대해 들어본 적 있나요? 2이상의 모든 자연수는 소수의 곱으로 나타낼 수 있고 순서를 고려하지 않을 경우 나타내는 방법은 유일합니다. 이 정리를 산술의 기본 정리라고 합니다. 증명이 엄청 어렵지는 않으나 딱히 중요하지 않은 것 같아 생략합니다.

 

이제 소인수분해를 직접 해봅시다.(BOJ 11653번 : 소인수분해) $N$을 소인수분해하기 위해 $N$이하의 모든 소수를 구한 후 그 소수들로 $N$을 나눠보면 되지만 그닥 추천하고 싶은 방법은 아닙니다. 대신 괜찮은 알고리즘을 소개해드리겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

대충 예제를 보니 잘 돌아가는 것 같긴 한데 이 알고리즘이 올바른 소인수분해 결과를 준다는 것을 알 수 있을까요? 생각해보면 $i$로 $N$이 나눠지는지 확인할 때 $i$가 소수인지를 체크하지 않는데 과연 이 알고리즘은 올바르게 동작하는걸까요?

 

우선 알고리즘이 반드시 종료됨을 증명해야 하는데 아무리 늦어도 $i = N$이 되는 순간에는 알고리즘이 종료될 것이기에 이 부분은 명확합니다. 그리고 알고리즘의 구조 상 소인수 목록에 적힌 수들의 곱이 $N$임은 자명합니다.

 

산술의 기본 정리에 의해 소인수 목록에 적힌 수들이 모두 소수이기만 하면 이 알고리즘이 올바른 소인수분해 결과를 준다는 것이 보장됩니다. 그러므로 소인수 목록에 적힌 수들이 모두 소수임을 증명해야 합니다.

 

이것 또한 귀류법으로 증명할 수 있습니다. 명제를 뒤집어 소인수 목록에 합성수 $a$가 있다고 가정해봅시다. 그리고 $a$의 임의의 소인수 $p$를 생각해봅시다. 소인수 목록에 합성수 $a$가 있다는 것은 $i = a$일 때 당시 $N$이 $a$의 배수였다는 의미입니다. 그 말은 곧 $N$이 $p$의 배수라는 의미입니다.

 

그런데 $i = p$일 때 $N$에 있던 $p$의 소인수는 전부 제거가 되었습니다. 그러므로 $i = a$일 때 $N$은 $p$의 배수일 수 없기에 소인수 목록에 합성수 $a$가 있을 경우 모순이 발생합니다. 그러므로 명제가 증명되었습니다.

소인수분해의 구현은 에라토스테네스의 체보다도 훨씬 쉽습니다.

 

그런데 이 구현에도 최적화할 수 있는 여지가 있습니다. 최적화를 통해 최악의 경우 $O(N)$ 에서 $O( \sqrt N )$ 으로 줄일 수 있습니다.

 

이 알고리즘은 주어진 $N$의 소인수를 2부터 찾아나서는 방식입니다. 앞에서 소수 판정법의 시간복잡도를 줄이는 것과 같은 아이디어로 생각해보면  $i^2$ 가 $N$보다 커지면 그 즉시 $N$이 소수임을 알 수 있습니다. 이를 이용해 for문의 탈출 조건을 수정하면 $N$이 소수일 때 $i$를 2부터 $N-1$까지 돌리는 대신 $i^2$ 가 $N$이하일 때 까지 돌리면 $O( \sqrt N )$ 으로 줄일 수 있습니다.

 

실제 구현할 땐 $N = 1$이 되었을 때 1을 출력하지 않도록 주의해야 합니다. (예시 코드)

 

소수 파트는 끝이 났고 약수와 최대공약수를 살펴보겠습니다. 주어진 수 $N$의 약수 목록을 구해야 하는 문제를 생각해봅시다. (BOJ 2501번 : 약수 구하기)

 

가장 간단한 방법은 1부터 $N$까지 모든 수에 대해 $N$을 나누는지 확인하는 방법입니다.

 

그런데 약수 구하기 문제도 $O(N)$ 에서 $O( \sqrt N )$ 으로 줄일 수 있습니다. 바로 약수끼리 곱이 $N$이 되게끔 짝을 지을 수 있다는 성질을 이용하는 것입니다. 즉 $\sqrt N$이하의 약수만 구하고 나면 나머지 약수들은 $N$에서 그 약수들을 나눠 구할 수 있습니다. 단 $N$이 제곱수인 경우에 주의해야 합니다. 예를 들어 $N = 16$일 때 4를 약수 목록에 중복해서 적지 않도록 말이죠.

 

이 성질을 이용해 수정된 약수 목록을 반환하는 함수는 아래와 같습니다.

최대공약수(Greatest Common Divisor)는 두 자연수의 공통된 약수 중 가장 큰 것을 의미합니다. GCD라고 줄여 쓰기도 합니다.(예 : GCD(6,20) = 2)

 

최소공배수(Least Common Multiple)은 두 자연수의 공통된 배수 중 가장 작은 것을 의미합니다. LCM라고 줄여 쓰기도 합니다.(예 : LCM(6,20) = 60)

 

GCD를 구하기 위해 두 수 A, B의 약수 목록을 찾아 공통된 원소를 찾는 방법도 있지만 유클리드 호제법이라는 것을 사용하면 $O(lg(max(A, B)))$에 구할 수 있기에 더 효율적입니다.

 

유클리드 호제법은 두 수 A, B에 대해 A를 B로 나눈 나머지를 r이라고 한다면 GCD(A, B) = GCD(B, r) 이라는 것을 이용해 수를 계속 줄여나가 최대공약수를 구하는 알고리즘입니다. 예를 들어 56을 12로 나눈 나머지가 8이므로 GCD(56, 12) = GCD(12, 8)입니다. 계속 진행한다면 GCD(12, 8) = GCD(8, 4) = GCD(4, 0) = 4가 됩니다.

 

GCD를 재귀적으로 간단하게 구현할 수 있습니다. 그리고 GCC에는 __gcd라는 아주 훌륭한 함수가 있으니 가져다쓰면 됩니다.(VS 2017에는 없습니다.) 해당 함수의 내부 구현은 위와 거의 동일합니다. 단 위와 달리 재귀 대신 반복문으로 구현이 되어있습니다.

 

최대공약수와 관련한 몇 가지 성질을 안내드리겠습니다.

 

성질 1. 두 수 A, B의 공약수들은 GCD(A, B)의 모든 약수들이다.

성질 2. 두 수 A, B의 공배수들은 LCM(A, B)의 모든 배수들이다.

성질 3. A × B = GCD(A, B) × LCM(A, B) 

성질 4. GCD(n, n+1) = 1

 

성질 3을 이용해 LCM(A, B) 를 A × B ÷ GCD(A, B) 로 구할 수 있습니다. 성질 4는 보고 바로 까먹어도 아무 상관 없습니다.

 

합동식은 깊게 파고들어가면 굉장히 할 얘기가 많지만 이번 강의에서 다룰 부분은 단지 특정 수로 나눈 나머지를 어떻게 처리해야하는지에 대한 부분입니다.

 

$A ≡ B (mod m)$ 이라는 기호의 의미는 $A$와 $B$가 $M$으로 나눈 나머지가 같다는 의미입니다. $A ≡ B (mod m)$ 일 때

 

1.    $A + C ≡ B + C (mod m)$

2.    $A - C ≡ B - C (mod m)$

3.    $AC ≡ BC (mod m)$ 입니다.

4.    그러나 $A ÷ C ≡ B ÷ C (mod m)$은 성립하지 않습니다. ( $A=6, B=2, C=2, M=4$ )

 

기호로 쓰니까 좀 낯설 수 있지만 사실 지금까지 문제를 풀 때 굉장히 자연스럽게 사용했던 성질들입니다. 문제에서 저런 식으로 특정 값을 나눈 나머지를 요구할 경우, int overflow를 회피하기 위해 연산 중간과정에서 계속 나머지만을 챙긴 경험이 있을 것입니다. 앞의 성질이 알려주는 것은 그런 식으로 나머지만을 챙겨도 답이 정상적으로 나온다는 점입니다.

 

C언어에서 특정 값으로 나눈 나머지를 출력하는 문제를 풀 때 int overflow 말고도 굉장히 조심해야 하는 부분은 음수의 나머지입니다. C언어에서는 몫이 음수일 경우 나머지 또한 음수가 됩니다.

 

예를 들어 $A$, $B$를 입력받아 $A-B$를 10으로 나눈 나머지를 출력하는 프로그램을 짰다고 해봅시다. 이 코드는 잘 동작하는 것 같아 보입니다.

 

그러나 $A-B$가 음수일 땐 잘못된 답을 출력합니다. 이를 방지하기 위해 아래와 같이 처리를 하는 것이 바람직합니다.

 

합동식을 알았으니 이제는 연립합동방정식을 풀어봅시다. 마침 BOJ 6064번 : 카잉 달력 문제가 연립합동방정식의 완전 정확한 예시입니다. 이 문제는 주어진 $M, N, x, y$에 대해 $A ≡ x (mod M), A ≡ y (mod N)$ 인 $A$ 를 찾는 문제입니다.

 

이런 연립합동방정식은 중국인의 나머지 정리(Chinese Remainder Theorem)을 사용하면 $O(log M +log N)$에 해결할 수 있습니다. 그러나 중국인의 나머지 정리를 이해하려면 모듈로 역수(Modular Inverse), 확장된 유클리드 호제법(Extended Euclidean Algorithm)을 먼저 알아야해서 중국인의 나머지 정리는 실전 알고리즘 강의에서 다루지 않을 예정입니다.

 

대신 시간복잡도는 조금 나쁘지만 이해하기 쉬운 풀이법을 설명드릴 예정입니다.

 

첫 번째로 $A$가 존재한다면 1 ~ $LCM(M,N)$ 사이에 유일하게 존재합니다. 이 성질은 귀류법을 통해 증명할 수 있습니다만 생략하겠습니다.

 

두 번째로 $A$가 존재할 필요충분조건은 $x ≡ y (mod GCD(M, N))$ 입니다. 이 성질 또한 귀류법으로 양방향을 다 보임으로서 증명할 수 있지만 생략하겠습니다. 그리고 사실 이 성질은 굳이 몰라도 상관이 없는게, 어차피 답을 구하는 과정에서 $A$가 존재하는지를 자연스럽게 알 수 있게 됩니다.

 

성질 1을 이용해서 $A$에 1부터 $LCM(M, N)$까지 차례대로 넣어봄으로서 답을 구할 수 있습니다. $LCM(M, N)$을 계산하기 싫으면 $LCM(M, N) \leq MN$ 이므로 그냥 1부터 $MN$까지 계산해도 결과는 동일하게 나옵니다. 만약 만족하는 $A$가 하나도 없으면 -1을 출력하면 됩니다.

 

 

그러나 이 방식은 $O(MN)$이기 때문에 $MN$이 최대 1,600,000,000인 이 문제에서는 시간 초과가 발생합니다. $O(MN)$ 대신 $O(N)$으로 개선하고 싶습니다.

 

i를 1부터 $MN$까지 하나하나 다 해보는 대신 조금 더 효율적인 방법이 있지 않을까요?

 

$A ≡ x (mod M)$이기 때문에 $A$가 존재한다면 $x, x+M, x+2M, x+3M, …$ 중에 하나입니다. 그렇기에 $i$를 $x, x+M, x+2M, x+3M, …$ 에 대해서만 해보면 되겠네요. 예시 코드를 참고하세요.

 

이제 식이 3개인 경우를 생각해봅시다. 이 문제를 푸는 시간복잡도를 $O(MNK)$에서 어디까지 떨굴 수 있을까요? 물론 중국인의 나머지 정리를 쓰면 log scale로 떨굴 수 있지만 앞의 문제와 같이 간단한 방법으로도 $O(M+N)$까지는 쉽게 만들 수 있습니다. 한 번 고민해보세요.

 

마지막 장은 이항계수와 팩토리얼입니다. 이 장에서 색깔이 다른 공 $n$개 중에 $r$개를 순서가 존재하게 뽑는 경우는 순열이고 순서를 무시하고 뽑는 경우는 조합이라는 것과 같은 내용은 이미 알고 있다고 가정할 것입니다. 그러므로 순열과 조합 부분이 약하시면 고등학교 수학 수준의 순열과 조합 지식을 공부하고 오시는걸 추천드립니다.

 

$n C k$를 구하는 문제를 생각해봅시다. 첫 번째는 n과 k가 10 이하인 문제입니다. (BOJ 11050번 : 이항 계수 1)

 

이 문제에서는 $n C k = n! / (n-k)!k!$ 이라는 식을 통해 쉽게 답을 얻을 수 있습니다.(예시 코드)

 

두 번째는 $n$과 $k$가 1000이하인 문제입니다.(BOJ 11051번 : 이항 계수 2)

 

$n C k = n! / (n-k)!k!$ 이라는 식을 이용하고 싶지만, 최대 $1000!$ 을 int나 long long에 담을 수 없음은 자명합니다. double에 담더라도 실수오차로 인해 정확한 값이 담길 리가 없습니다.

 

물론 $n!, (n-k)!, k!$ 을 10,007로 나눈 나머지는 알 수 있습니다. 그러나 우리는 현재 합동식 안에서 덧셈, 뺄셈, 곱셈은 수행할 수 있지만 나눗셈을 수행하는 법을 모릅니다.(나중에 modular inverse를 배우고 나면 $n!, (n-k)!, k!$ 을 10,007로 나눈 나머지를 가지고 빠르게 계산할 수 있습니다. 이렇게 되면 $n$과 $k$가 최대 1,000,000이어도 계산이 가능합니다.)

 

이 문제는 $n C k = n-1 C k + n-1 C k-1$ 이라는 식을 통해 다이나믹 프로그래밍으로 해결해야 합니다. int overflow에 주의하세요.(예시 코드)

 

 

마지막으로 BOJ 1676번 : 팩토리얼 0의 갯수 문제를 풀어봅시다. 

 

$N$의 뒤에서부터 처음 0이 아닌 숫자가 $k$개 나온다는 것은 곧 $N$이 $10^k$ 의 배수이면서 $10^$ 의 배수가 아니라는 의미입니다. 그렇기에 $N!$을 소인수분해 했을 때 $N! = 2^a × 5^b × etc$ 라면 $N!$의 뒤에서부터 처음 0이 아닌 숫자가 나올 때 까지 0이 $min(a, b)$개 나옵니다.

 

상식적으로 생각해서 $N!$ 에 2보다 5가 적을테니 5가 몇 개인지만 세면 됩니다. $N$이 최대 500이므로 1~$N$ 에서 5의 배수의 갯수, 25의 배수의 갯수, 125의 배수의 갯수를 더하면 됩니다. (예시 코드)

 

참고로 이 문제는 초/중학교 학생들을 대상으로 하는 경시대회에 단골로 나오는 문제입니다. 초딩도 배우는 내용이니 우리들은 당연히 할 수 있습니다!

 

이 또 다른 정답 코드가 어떤 원리로 성립하는 것일지 한 번 고민해보세요.

 

이번 시간에 소수 판정법, 에라토스테네스의 체, 소인수분해, 약수를 구하는 방법, 유클리드 호제법, GCD와 LCM에 관련된 몇 개의 성질, 합동식의 성질, 나머지를 구할 때 주의사항, 연립합동방정식을 푸는 방법, 이항계수를 구하는 방법, 팩토리얼과 관련한 문제를 모두 다뤘습니다.

 

수학적 베이스가 탄탄하거나 이러한 유형을 공부해본 사람이면 다른 강에 비해 이번 강이 쉽게 느껴지셨을 텐데 이 모든 내용을 처음 접하셨다면 좀 어려울 수도 있습니다. 모든 정리를 외우려고 하는 것 보다는 관련된 문제들을 직접 구현해보면서 자연스럽게 익힐 수 있도록 노력해보세요.