10. 정수론
p. 215~253
< 정수론 : 수의 성질을 탐구하고 공부하는 분야 >
■ 정수론에서 가장 많이 등장하는 부분
1) 소수 구하기 *에라토스테네스의 체 활용
- 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수
- 1과 자기 자신 외에 약수가 존재하지 않는 수
✔ 에라토스테네스의 체 원리
1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성
2. 2부터 시작, 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를
배열에서 끝까지 탐색하면서 지웁니다. *선택된 숫자는 지우지 않습니다.
3. 배열의 끝까지 '2'를 반복한 후 배열에서 남아있는 모든 수를 출력합니다.
✔ 백준 1929번 - 소수 구하기
✔ 문제 분석
* M이상 N이하의 소수를 모두 출력 (1줄에 1개씩 증가하는 순서)
- 1번째 줄에 M과 N이 빈칸을 사이에 두고 주어지고 M이상 N이하의 소수가 1개이상 있는 입력만 주어짐
- 소수를 찾을 때는 2이상부터 자기 자신보다 작은 수로 나웠을 때 나머지가 0이 아닌 수를 찾는다.
✔ 문제 풀기
* 주의사항: 숫자 사이에 소수를 출력하는 것으로 N의 최대 범위가 너무 커서 일반적인 방식으로 하면 시간 초과 발생
에라토스테네스 방법 이용
- 크기가 N +1인 배열을 선언한 후 값을 각각의 인덱스 값으로 채우기
- 1은 소수가 아니므로 삭제
- 2~N의 제곱근까지 값을 탐색, 값이 인덱스 값이면 두고 그 값의 배수를 탐색해 0으로 변경
- 배열에 남아 있는 수 중 M이상 N이하의 수를 모두 출력
✔ 코드 작성
- 화면을 통해 받은 데이터 M, N에 받기
- A배열 생성하기
- 반복문으로 N의 제곱근까지 반복하고 배수 지우기
- 소수만 출력하기
2) 오일러의 피
- 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있기에 구현만 이해하기
✔ 오일러 피의 원리
1. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화
2. 2부터 시작, 현재 배열의 값과 인덱스가 값으면 (소수일 때)
현재 선택된 숫자의 배수에 해당한 수를 배열에 끝까지 탐색하며
P[i] = P[i] - P[i]/K 연산을 수행한다 * i는 K의 배수
3. 배열의 끝까지 '2'를 반복하여 오일러의 피 함수를 완성한다.
3) 유클리드 호제법
- 두 수의 최대공약수를 구하는 알고리즘
- MOD 연산의 활용 (10%4 = 2)
✔ MOD 연산으로 구현하는 유클리드 호재법
1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD연산을 수행한다.
3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택
✔ 백준 1850번 - 최대공약수
✔ 문제 분석
* A와 B의 최대공약수를 출력한다 *천만 자리를 넘지 않는다
- 1번째 줄에 자연수 A와 B를 이루는 1의 개수가 주어진다.
✔ 문제 풀기
* 주의사항: A가 3이면 111, B가 6이면 111111
- 유클리드 호제법으로 A와 B의 공약수를 구한다
- 공략수 길이만큼 1을 출력 * 시간초과가 되지 않도록 BufferedWriter을 사용
✔ 코드 작성
4) 확장된 유클리드 호제법
- 정확히 이해하기 위해선 수학 증명 과정을 공부해야 하기에 알고리즘만 이해하기
- 해를 구하고자 하는 방정식 ax + by = c(a, b, c, x, y는 정수)
✔ 확장된 유클리드 호제법 원리
* 5x + 9y =2 일 때 이식을 만족하는 정수 x, y를 구하기
1. 5x + 9y가 정수해를 갖게 하는 c의 최솟값이 gcd(5,9) 적용
gcd(5,9) = 1 이므로 5x + 9y =1로 식을 다시 정리
2. a, b로 반복실행하며 몫과 나머지를 저장
나머지가 0이 되면 중단
3, 4
- 유클리드로 구한 나머지와 몫을 이용해 역순으로 x = y`, y = x` - y` * q 를 계산
- 최종 x, y는 ax + by = gcd(a, b)를 만족
아......................... 현타온다
너무 어렵다