[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 7장 정수론

교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 : https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

---

 

7.1 소수 구하기

- 에라토스테네스의 체

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
2. 2부터 시작하고, 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 수는 지우지 않는다
3. 배열의 끝까지 2번을 반복하고 배열에 남은 모든 수를 출력한다.

- 시간 복잡도 : O(Nlog(logN))

• 이중 for문을 사용하지만 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생

- 코드로 구현하기

for (int i=2; i<sqrt(n); i++){
    if (a[i] == 0) continue;
    for (int j=i+i; j<=n; j+=i) a[j] = 0;
}

- 탐색 시 N의 제곱근까지만 탐색하는 이유

• N의 제곱근이 n일 때 N = a * b를 만족하는 a와 b가 모두 n보다 클 수 없다.
• N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가진다.

 
 

7.2 오일러 피

- 정의

오일러 피 함수 P[N] 은 1부터 N까지 범위에서 N과 서로소인 자연수의 개수

- 원리

1. 구하고자 하는 오일러 피의 범위만큼 자기 자신의 인덱스값으로 초기화한다.
2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열의 끝까지 탐색하며 P[i] = P[i]-P[i]/K 연산을 수행한다. (i는 K의 배수)
3. 배열의 끝까지 2번을 반복하며 오일러 피 함수를 완성한다.

 
 

7.3 유클리드 호제법 (euclidean-algorithm)

- 두 수의 최대 공약수를 구하는 알고리즘
- MOD 연산 : 두 값을 나눈 나머지를 구하는 연산
- MOD 연산으로 구현하는 유클리드 호제법

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD 연산을 수행한다.
3. 2번을 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

 

7.4 확장된 유클리드 호제법

- 목적 : 방정식의 해 구하기
- 핵심 이론

• 구하고자 하는 방정식 : ax + by = c (a, b, c, x, y는 정수)
• c % gcd(a, b) = 0인 경우에만 정수해를 가진다. 
• c가 a와 b의 최대공약수의 배수인 경우에만 정수해를 가진다.
• ax + by = c가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)이다.

ex) 5x + 9y = 2
① gcd(5, 9) = 1이므로 식을 5x + 9y = 1로 놓는다.
② a, b로 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장하고, 나머지가 0이 되면 중단한다.

유클리드 호제법	나머지	몫
5 % 9 = 5	5	0
9 % 5  = 4	4	1
5 % 4 = 1	1	1
4 % 1 = 0	0	4

③ 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y = x'-y'*q를 계산한다.
(x'는 이전 x, y'는 이전 y, q는 현재 보고 있는 몫, 처음 시작하는 x, y는 이전의 x,y가 없으므로 1, 0으로 지정함.)

나머지	몫	x = y', y = x'-y'*q 역순 계산
5	0	x = 2, y = -1 - (2*0) = -1
4	1	x = -1, y = 1 - (-1*1) = 2
1	1	x = 1, y = 0 - (1*1) = -1
0	4	x = 0, y = 1 - (0 * 4) = 1

④ 최종 x, y는 ax + by = gcd(a, b)를 만족한다. 그리고 c / gcd(a, b) = K를 가정하면 최초 방정식의 해는 Kx, Ky로 구할 수 있다.

• K = 2 / 1 = 2
• x = 2 * 2 = 4
• y = 2 * (-1) 

최초 방정식의 해는 (4, -2)이다.
 
- 오른쪽 변의 값이 gcd(a, b)의 배수가 아니라면 이 경우를 만족하는 x, y 값은 정수 범위에서 존재하지 않는다.