728x90

섹션 2. 코딩테스트 - 07. 정수론

⬛ 07. 정수론

정수론 : 수의 성질 탐구하고 공부하는 이론 분야
실제 코테에서는 모든 정수론 분야가 나오는 것은 아니므로, 가장 많이 등장하는 ‘소수 부분’과 ‘호제법’ 부분을 집중적으로 다뤄보자.

⬛ 07-1. 소수 구하기

🟦 소수

1과 자기 자신 외에 약수가 존재하지 않는 수
소수 판별 방식을 묻는 ‘소수 구하기 문제’ 종종 출제

🟦 대표적인 소수 판별 방식 | ‘에라토스테네스의 체’

시간 복잡도 : O(N2) 이중 for문 사용하므로..

🟧 에라토스테네스의 체 방식

구하고자 하는 소수 범위만큼의 1차원 배열[] 생성
for(2~N) :

현재 i의 숫자 선택 → (첫 수 제외) 현재 선택된 i의 배수를 배열 끝까지 탐색하면서 모두 지움
그 다음 지워지지 않은 수 i 선택 → 그 수의 배수 모조리 지움
for(int j = i+i; j≤ N; j = j+i)
// i+i부터 i씩 증가하며 배수 삭제

배열 끝까지 이 과정 반복한 뒤 남아있는 모든 수 출력 == 소수

🟦 백준 1929번. 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

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

예를 들어, A X B = N 이라고 해보자.
A와 B 두 수 모두가 동시에 N의 제곱근보다 클 수는 없다.

문풀

아래의 코드에서 소수 탐색 시 ‘N의 제곱근까지만 탐색하는 이유’를 꼭 이해해야 한다.

import java.util.Scanner;

/*백준 1929번. 소수 구하기*/
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int M = kb.nextInt();
		int N = kb.nextInt();
		int[] arr = new int[N+1];
		
		for(int i=2; i<=N; i++) { //배열을 인덱스값으로 채움
			arr[i]=i;
		}
		//*** N의 제곱근까지만 탐색하는 이유 !!!
		for(int i=2; i<=Math.sqrt(N); i++) {
			if(arr[i]==0) continue;//건너뜀
			
			for(int j= i+i; j<=N; j=j+i) { //배수 지우기 
				arr[j] =0;
			}
		}
		
		//이제 0 제외 차례로 출력
		for(int i=M; i<=N; i++) {
			if(arr[i] != 0) {
				System.out.println(arr[i]);
			}
			
		}
	}
}

🟦 백준 1747번. 소수 팰린드롬

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

문풀

이 문제는 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수 구해놓은 뒤, 그 집합에서 N보다 크거나 같은 범위에서 ‘투 포인터’ 사용하여 팰린드롬 수 발견 즉시 출력 후 탈출하면 된다.

package to_0620_2;

import java.util.Scanner;

/* 1747번. 소수 팰린드롬 수 중에서 최솟값 찾기 */
public class Main {
	//수 판별 함수 
	static boolean isPalindrome(int target) { //투 포인터로 각 값 찍으면서 비교
		boolean answer = true;
		
		char[] tmp = String.valueOf(target).toCharArray();//문자형 배열로 변환시켜놓고
		int s=0, e=tmp.length-1;
		
		while(s < e) {
			if(tmp[s] != tmp[e]) { //양 끝에서 하나씩 찍어서 값 비교 시 하나라도 다르면 X
				answer = false;
			}
			s++;
			e--;
		}
		
		return answer;
	}
	
	//실행 메인
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
	
		int N = kb.nextInt();
		int[] A = new int[10000001];//범위까지 
		for(int i=2; i<A.length; i++) {
			A[i] = i;
		}
		
		for(int i =2; i< Math.sqrt(A.length); i++) { //배수 지우기 
			if(A[i] == 0) continue;
			for(int j=i+i; j<A.length; j= j+i) {
				A[j] = 0;
			}
		}
		//팰린드롬 수 판별 
		int i = N; //N보다 크거나 같은 숫자들 중에서 
		while(true) {
			if(A[i] != 0) {//즉, 소수인 수들 중에서 
				int target = A[i];
				if(isPalindrome(target)) {//팰린드롬 숫자인 경우 
					System.out.println(target);
					break;
				}
			}
			i++;// 하나씩 증가시키면서 ㄴ
		}
	}
}

⬛ 07-2. 오일러 피

🟦 오일러 피 함수 : P[N]

1부터 N까지 범위 내에서 N과 서로소인 자연수의 개수
- 서로소 : 두 수 간의 공약수가 1 뿐인 수

🟧 오일러 피의 핵심 원리

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

⬛ 07-3. 유클리드 호제법

⬛ 유클리드 호제법

유클리드 호제법 : 두 수의 최대 공약수를 구하는 알고리즘
기본적으로 최대 공약수 구하는 방법은 소인수분해를 이용한 공통 소수들의 곱으로 표현할 수 있다.
유클리드 호제법은 더 간단한 방법을 제시한다.

1) 기본적으로 ‘최대공약수’ 를 유클리드 호제법 활용하여 구할 수 있다.

2) 부가적으로 ‘최소공배수’는 a * b / 최대공약수 연산으로 구할 수 있으므로 이 역시 유클리드 호제법을 활용하여 구할 수 있게 된다.

⬛ 유클리드 호제법의 핵심 이론 | MOD 연산

큰 수를 작은 수로 나누는 MOD 연산 수행
앞 단계의 작은 수와 MOD 연산결과의 나머지값으로 다시 MOD 연산 수행
나머지가 0이 되는 순간의 ‘작은 수’가 최대 공약수가 된다.

public static int gcd(int a, int b){
	int r = a % b;
	if(r == 0) return b; //직전 연산의 b 를 리턴
	else return gcd(b, r); //아니면 b, r로 재연산
}

🟦 백준 1934번. 최소공배수

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

풀이

import java.util.*;
/* 1934번. 최소공배수 
 * */
public class Main {
	//gcd() 함수 
	static int gcd(int a, int b) { //큰수, 작은수 (작은수==0) 이 되면 그때의 a 리턴 후 종료)
		if(b==0) return a;
		else {
			return gcd(b, a%b);//재귀함수 형태
		}
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int T = kb.nextInt();
		ArrayList<Integer> arr =  new ArrayList<>();
		
		for(int t=0; t<T; t++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			
			int result = (a * b) / gcd(a, b);
			arr.add(result);
		}
		
		for(int x :  arr) {
			System.out.println(x);
		}
	}
}

⬛ 07-4. 확장된 유클리드 호제법

🟦 확장된 유클리드 호제법

목적 : 방정식의 해를 구하는 것이다.

🟧 확장된 유클리드 호제법 핵심

해를 구하고자 하는 방식 
ax + by = c ( a, b, c, x, y 는 모두 정수이다.)

위의 식에서 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 갖는다.
즉, ax + by = c가 정수해를 갖게 하는 c의 최솟값은 gcd(a,b) 라는 것을 의미한다.
재귀함수를 사용하여 구핸해야 한다.

🟧 확장된 유클리드 호제법의 원리

예를 들어, 5x + 9y = 2 일 때를 생각해보자.

1) 5x+9y 가 정수해를 갖게 하는 c의 최솟값이 gcd(5,9)라는 것을 적용하여 gcd(5,9) = 1이므로 5x+9y=1 로 식을 다시 놓는다.

2) a,b로 유클리드 호제법 반복 실행하며, 몫.나머지를 저장하고, 반복은 나머지가 0이 되면 중단한다.

*3) 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가면서 계산할 건데 x = y’ . y = x’-y’q 를 계산한다.

4) 재귀방식으로 알아낸 최종 x,y가 ax + by = gcd(a,b)를 만족한다.