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)를 만족

---

아......................... 현타온다 

너무 어렵다