간단한 알고리즘 - 정수론

이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다.

 

 

코딩테스트에서 나오는 비주류 유형이 몇가지 있는데, 그중 하나인 정수론에 대해 적어보려고 합니다.
코딩테스트에 자주 나오진 않지만, 보통 많이들 가고싶어하시는 상위티어 기업들에서는 나름 빈출이기도 하니 한번쯤 익혀두시면 좋을것 같습니다!
심지어 코딩테스트에 나오는 수준의 정수론은 대부분 쉬워요.


1. 유클리드 호제법
이건 제가 1학년 2학기 c언어 실습 빨리 끝내고 기다리고 있을 때 교수님께서 한번 코딩해보라고 알려주셔서 그 때 처음 알게된 개념이에요. 1학년도 할 수 있는 알고보면 간단한 내용이니 수식 많다고 포기하지 마시고 한번 읽어보세요!

내용은 간단합니다. a와 b의 최대공약수를 gcd(a, b)라고 표현할게요. a > b라고 가정할 때 gcd(a, b) = gcd(a-b, b)가 됩니다. 풀어서 얘기하면 a와 b의 최대공약수는 a-b와 b의 최대공약수와 같다는 뜻입니다.


(1) 왜 이럴까?
(2) 그래서 이걸 어디에 쓸까?

두가지에 대해 설명드릴게요.

(1) 왜 이럴까?
생각보다 증명은 간단합니다. a와 b의 약수 k가 있다고 해볼게요. a = kx, b = ky로 나타낼 수 있을거에요. 그럼 a - b = k(x - y)가 되겠죠. a - b도 k의 배수가 되네요.
이걸 통해 a와 b의 공약수는 a-b의 약수라는 사실을 알아냈습니다. 공약수가 아닌 수는 a-b의 약수가 아니라는 사실도 증명해야 하지만... 굳이 꼭 해야 할까요

(2) 그래서 이걸 어디에 쓸까?
일반적으로 a와 b의 최대공약수를 구해야 한다면 아래처럼 구해야 합니다.

for(i = 1; i <= b; i++)
{
if(a % i == 0 && b % i == 0)
gcd = i;
}

시간복잡도는 O(b)쯤 되겠네요. b가 10억쯤 되면 구하기 어렵겠네요.

유클리드 호제법을 이용하면 아래처럼 구할 수 있습니다.

while(a % b != 0)
{
temp = a % b;
a = b;
b = temp;
}

gcd = b;


우선 gcd(a, b) = gcd(a-b, b)라는 식에서 gcd(a, b) = gcd(a-b, b) = gcd(a-2b, b) = gcd(a-3b, b).... = gcd(a % b, b)가 된다는 사실을 알 수 있습니다. 계속 빼는게 아니라 뺄 수 있는 만큼 한번에 빼는걸로 해석할 수 있어요.

a % b는 b보다 작습니다. 그럼 gcd(a % b, b) = gcd(b, a % b) = gcd(b % (a%b), a%b)가 되겠죠. 이런식으로 gcd(a, b)를 gcd(b, a % b)로 바꾼 뒤 유클리드 호제법을 적용시킬 수 있습니다.

언제 끝날까요? a가 b의 배수가 되면 끝나게 됩니다. 이건 20 12 같은걸로 한번 손으로 따라가보시면 알 수 있어요.

이해가 잘 안된다면 아래 케이스들을 직접 손으로 유클리드 호제법을 적용시켜봅시다.
20 12
30 24
10 7
5 3
100 40

유클리드 호제법을 이용해 최대공약수를 구하는건 약 O(log a)만큼의 시간이 걸립니다. 따라서 long long 범위 안쪽의 어떤 수가 들어와도 60번 정도의 연산만 하면 최대공약수를 구할 수 있어요. 짱빠르죠


2. n의 약수 구하기
자연수 n의 약수를 구하는건 아래처럼 할 수도 있어요.

for(i = 1; i <= n; i++)
{
if(n % i == 0) print(i);
}

하지만 이러면 O(n) 이죠. 이것도 많이 줄일 수 있습니다.

12의 약수를 적어볼게요.

1 2 3 4 6 12

사실 이 값들은 짝이 있습니다.

1 * 12 = 12
2 * 6 = 12
3 * 4 = 12

그럼 사실 왼쪽 값들(1,2,3)을 알면 오른쪽 값들(12,6,4)은 바로 구할 수 있겠죠.
왼쪽에 오는 값들은 루트12 보다 작거나 같은 값들입니다. 루트12보다 커지면 상대방보다 커지거든요.
따라서 아래처럼 구할 수 있습니다.

for(i=1; i * i <= n; i++)
{
if(n % i == 0)
{
print(i);
if(i * i != n) print(n / i);
}
}

중간에 i * i가 n이면 출력 안하는 부분은 n이 25처럼 제곱수일 때 5 * 5 = 25에서 5를 두번 출력할까봐 제외한거에요.

아무튼 이런식으로 루트n 시간에 모든 약수를 구할 수 있습니다.
추가로 n이 제곱수가 아니라면 약수의 개수는 짝수, 제곱수라면 홀수가 됩니다. 이건 위 내용을 제대로 이해하시면 직관적으로 알 수 있으니 설명은 넘어갈게요.


3. 모듈러 연산의 특징
수업시간에 몇번 나온것 같은데 잘 잊어버리는 개념이니 짧게 설명할게요.
(a + b) % c = (a % c + b % c) % c
이런 식이 성립합니다.
예를들어 9999 + 7721을 10으로 나눈 나머지가 궁금하다면 우선 둘을 각각 10으로 나눈 나머지를 구합니다. 9랑 1이 나오겠네요. 이 둘을 더해서 10을 얻은 뒤 다시 10으로 나눈 나머지를 구하면 실제로 9999+7721을 구한 뒤 10으로 나눈 나머지를 구하는 것과 같은 결과가 나오게 됩니다.

쓸데없이 연산을 왜 더 할까요?
문제를 풀다 보면(특히 dp) 자료형에서 오버플로우가 나오는 경우가 상당히 많습니다.
피보나치 수열의 100000번째 값을 99997로 나눈 나머지를 구하라는 문제가 있다고 해봅시다. 100000번째 값은 long long같은 일반적인 자료형으로 담기엔 너무 큰 수가 됩니다. 큰 수 연산을 지원하는 언어를 사용하더라도 수가 커지면 시간복잡도도 같이 커져서 크게 의미 없을 수 있습니다.
100000번째 값을 정확히 구한 뒤 99997로 나눈 나머지를 구할 수는 없습니다. 하지만 중간 과정에서 99997로 나누면서 구하는 것도 같은 결과가 나오기 때문에 아래처럼 구하는 중에 계속 나눠줘도 됩니다.

fibo[0] = 0;
fibo[1] = 1;
for(i = 2; i <= 100000; i++)
{
fibo[i] = fibo[i - 1] + fibo[i - 2];
fibo[i] %= 99997;
}

이런식으로요.

이건 곱셈에도 적용되니 어떤 값으로 나눈 나머지를 구해야 한다면 중간 과정에서도 계속 모듈러 연산을 해줘도 됩니다.
(단, 프로그래밍 언어에서는 나누기 결과를 몫만 가져오기 때문에 나누기 연산에 대해서는 이런 방식이 적용되지 않습니다. 나누기에 대해 적용하려면 페르마 소정리를 공부하셔야 합니다.)


추가로 공부할만한 정수론 개념들
1. 에라토스테네스의 체
어떤 수가 소수인지 아닌지 판별을 여러번 해야 하는 경우 유용합니다.
2. 소인수분해
약수 구하기와 유사한 방식으로 빠르게 구할 수 있습니다.
추가로, 모든 수는 소인수를 log개 이하로 갖고 있습니다. 가장 작은 소수가 2라서 당연한 얘기겠죠. 이걸 이용하는 문제가 나올 수도 있습니다.
3. 빠른 거듭제곱
분할정복을 이용해 a의 b제곱을 log b 시간에 구할 수 있습니다. 분할정복이라고 하니 어려워 보이는데 의외로 쉽고 유용합니다.


맨 위에서 말씀드렸지만 정수론 문제는 코딩테스트에서 비주류라서 어지간한 기업에서는 크게 필요 없는 개념들입니다. 하지만 n사, k사 등 코딩테스트가 어렵게 나오는 기업들을 지원하실 예정이라면 꼭 익히셔야 하고, 심지어 막상 공부해보면 난이도도 낮은 편이니 꼭 익혀서 가시면 좋겠습니다!

문제도 올려드려야 하는데 조만간 찾아서 추가해두겠습니다!






+ 올릴만한 주제가 크게 두가지 있는데
1. 구현 스킬
2. 알고리즘 개념

어떤게 더 도움이 될까요?

코딩 스킬이라면 10진수 각 자리 편하게 쪼개는 법이나 예전에 올렸던 xor연산을 이용한 코딩스킬같은 내용입니다. 배열을 이용한 코딩 스킬도 여기 속하는 내용입니다.

알고리즘 개념은 지난번 완전탐색이나 이번 글처럼 실제 문제 풀이를 어떤식으로 해야하는지에 대한 내용입니다. 백트래킹 문제가 나오면 어떻게 접근해야 하고, dp는 어떤 유형들이 나오고, 그런 내용들이요.


제가 약 2년반을 혼자 공부하다보니 알고리즘 공부를 혼자 하는게 얼마나 막막한지 누구보다 잘 알고 있고, 그런만큼 최대한 코딩테스트를 보실 분들한테 실전적인 도움을 드리고 싶은 마음이 큰데 어떤 식으로 도움을 드려야 할지 아직 잘 모르겠네요 ㅠㅠ
오늘 정수론에 대해 적은건 조만간 네이버? nhn? 에서 코딩테스트를 본다는걸 얼핏 들어서 적은건데, 앞으로는 최대한 많은 분들에게 도움이 될 수 있는 글을 적으려고 합니다. 다들 코딩테스트는 가뿐히 통과하실 수 있게 최대한 도와드릴게요. 제가 더 효율적으로 도와드릴 수 있게 좋은 아이디어 있으시면 언제든 말씀해주세요.


그리고 혹시

배열을 이용한 코딩 스킬
완전탐색

글을 안보셨으면 이 둘만큼은 보시는걸 추천드립니다. 개인적으로 알고리즘 처음 공부할 때 정말 중요하다고 생각하는 것들입니다!


뒤에 짧게 적는다는게 주절주절 길어졌네요. 이만 줄이겠습니다. 항상 많이들 읽어주셔서 감사합니다.