TIL #5 알고리즘 기초 - 수학

노력하는 배짱이·2020년 8월 6일

1. 수학

1.1 나머지연산

위키백과에 따르면 나머지는 산술에서 두 정수의 나눗셈 이후, 온전한 정수 몫으로 표현할 수 없이 남은 양을 가리킨다. 라고 정의한다.

나머지 연산은 MDO 또는 mod 로 표기한다.
예를 들면 10 mod 3 = 1 로 표기하는 것이다.

어떤 문제를 해결할 때 정답이 너무 커질 수 있는 상황이 존재하는데, 정답을 구했는지 알기 위해 나머지를 구해라라는 문제로 나오기도 한다.
이때 정답을 다 구하고 나머지 연산을 하는 것이 아니라 정답을 갱신해 줄 때마다 나머지 연산을 수행해 줘야 한다.

1.2 나머지 연산 성질

$(A+B) mod M = ((A mod M) + (B mod M)) mod M$

$(A*B) mod M = ((A mod M) * (B mod M)) mod M$

나누기는 성립하지 않아 모듈러 역수(Modular Inverse)를 구해야 한다.

예)
(5 + 2) % 3 = 7 % 3 = 1
((5 % 3) + (2 % 3)) % 3 = (2+2) % 3 = 1
결과가 같음을 알 수 있다.

뺄셈의 경우 결과가 음수가 나올 수 있기 때문에 아래와 같이 해야한다.

$(A-B) mod M = ((A mod M) - (B mod M) ) mod M$

위와 같은 공식으로 했을 경우 문제가 존재한다.
(6-5)%3 = 1 % 3 = 1 이지만
(6%3 - 5%3) % 3 = (0 - 2) % 3 = -2 % 3 = ??
이런경우 언어마다 다른 결과를 출력하는데, 파이썬은 1을 출력하지만, 자바에 경우 -2를 출력한다.
그래서 이러한 것을 방지하기 위해서 아래 식처럼 나머지를 더한 후 연산을 수행한다.

$(A-B) mod M = ((A mod M) - (B mod M) + M) mod M$

위 성질에 대해 설명하자면, 나머지 c로 연산을 수행하면
$0 \leq a \ mod \ c < c$ 이고 $0 \leq b \ mod \ c < c$ 이기 때문에
$(a \ mod \ c - b \ mod \ c)$ 의 결과는
$-c < a \ mod \ c - b \ mod \ c < c$ 를 만족하게 된다.
여기에 c를 더해주면 $0<a \ mod \ c - b \ mod \ c<2c$ 가 되어 양수 범위에 존재하게 되며 c로 나눠주면 원하는 결과를 얻게 되는 것이다.

1.3 문제 백준 문제 : 나머지

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int a = sc.nextInt();
	int b = sc.nextInt();
	int c = sc.nextInt();
	System.out.println((a + b) % c);
	System.out.println(((a % c) + (b % c)) % c);
	System.out.println((a * b) % c);
	System.out.println(((a % c) * (b % c)) % c);
}

2. 최대공약수(Greatest Common Divisor)

최대공약수는 임의의 두 수 사이의 공통된 약수중 가장 큰 정수를 의미하며 GCD라고 표기한다.

최대공약수를 구하는 방법중 하나는 2부터 두 수의 제일 작은 구 까지 즉, 두 수가 A와 B이면 2부터 min(A,B)까지 모든 정수로 나누는 것이다.
int g = 1;
for (int i=2; i<min(a,b); i++){
	if (a % i == 0 && b % i == 0) {
    		g = i;
	}
}
max(a,b)가 N이라 했을 때, 시간복잡도는 $O(N)$ 이다.

또한 최대공약수가 1이면 두 수를 서로소라고 한다.

2.1 유클리드 호제법(Euclidean algorithm)

앞서 나온 방법보다 속도가 빠르다.

a를 b로 나눈 나머지를 r이라고 하면,
$GCD(a,b) = GCD(b,r)$ 과 같다.

r이 0이면 b가 최대공약수 이다.

예를 들면, GCD(24,16)이 주어지면
$GCD(24,16)=GCD(16,8)=GCD(8,0)=8$ 이다.

재귀함수 사용
int gcd(int a, int b) {
	if (b == 0) {
    		return a;
        }else {
        	return gcd(b, a%b);
        }
}
while문으로 구현
int gcd(int a, int b) {
	while (b != 0) {
    		int r = a % b;
        	a = b;
        	b = r;
    	}
    	return a;
}
while문으로 구현하는 경우 시간복잡도는 $O(lgN)$ 이며, 특히, 나머지를 먼저 구하고 a와 b를 바꿔야한다.

3. 최소공배수(Least Common Multiple)

최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수를 의미하며 LCM이라고 표기한다.
최소공배수는 최대공약수를 이용하여 구할 수 있다.

두 수 A와 B의 최대공약수를 G라고 했을 때,
최소공배수 LCM = (A*B) / G이다.
$A \ * \ B= GCD \ * \ LCM$ 이고, 이는 $LCM = (A*B) \ / \ GCD$ 이다.

3.1 문제 백준 문제 : 최대공약수와 최소공배수

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int num1 = sc.nextInt();
	int num2 = sc.nextInt();
	int g = gcd(num1,num2); // 최대공약수
	int l = (num1 * num2) / g; // 최소공배수
	System.out.println(g);
	System.out.println(l);
}
public static int gcd(int num1, int num2) {
	if(num2 == 0) {
		return num1;
	}else {
		return gcd(num2, num1%num2);
	}
}

3.2 문제 백준 문제 : 최소공배수

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	while(n-- > 0) {
		int num1 = sc.nextInt();
		int num2 = sc.nextInt();
		System.out.println((num1 * num2) / gcd(num1,num2));
	}
}
public static int gcd(int num1, int num2) {
	if(num2 == 0) {
		return num1;
	}else {
		return gcd(num2, num1%num2);
	}
}

4. 소수

소수는 약수가 1과 자기 자신밖에 없는 수를 의미한다.
즉, 임의의 수 N이 소수이려면, 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

소수와 관련된 알고리즘이 두가지가 있다.
1. 임의의 수 N이 소수인지 아닌지 판별하는 것
2. 임의의 수 N보다 작거나 같은 모든 자연수 중에서 소수인 수를 찾아내는 것

4.1 소수와 관련된 알고리즘

임의의 수 N이 소수인지 아닌지 판별하는 코드 중 하나이며 아래 코드는 시간복잡도가 $O(N)$ 이다.
boolean prime(int n) {
	if (n < 2) {
    		return false;
    	}
	for(int i=2; i<n-1; i++) {
    		if (n%i==0) {
    			return false;
    		}
    	}
	return true;
}
위의 코드를 조금 더 개선해보자.

$N=a \ * \ B \ (a \leq b)$ 이라 했을 때, 소수가 되려면 $2$ 보다 크거나 같고 $N/2$ 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
$N=a \ * \ B \ (a \leq b)$ 식에서 a가 작을수록 b는 크게되고 a의 가장 작은 값은 2이기 때문에, b는 $N/2$ 보다 작거나 같다.
boolean prime(int n) {
	if (n < 2) {
    		return false;
    	}
	for(int i=2; i<=n/2; i++) {
    		if (n % i == 0) {
    			return false;
    		}
    	}
	return true;
}
이렇게 코드를 개선하여도 시간복잡도는 여전히 $O(N/2) = O(N)$ 이다.

위의 알고리즘을 좀 더 개선할 수 있다.

소수 N이 되려면 2보다 크거나 같고, $\sqrt{N}$ 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

해당 성질은 약수의 중심까지 범위를 좁히는 것으로부터 나왔다.
N이 소수가 아니라면 $N=a \ * \ B \ (a \leq b)$ 일 때, $a \leq \sqrt{N}$ 이고 $b \geq \sqrt{N}$ 일 수 밖에 없다.
이는 $a < \sqrt{N}$ , $b < \sqrt{N}$ 이면 $a* b < \sqrt{N}$ 이고 이는 $N=a \ * \ B$ 를 만족하지 않는다. 반대 또한 그러하다.

따라서 작은 쪽인 $a < \sqrt{N}$ 부분까지 약수가 존재하는지 구해보면 소수인지를 판별할 수 있다.
boolean prime(int n) {
	if (n < 2) {
    		return false;
	    }
	for(int i=2; i*i<=n; i++) {
	    	if (n % i == 0) {
	    		return false;
	    	}
	    }
	return true;
}
이와 같이 구현하면 시간복잡도는 $O(\sqrt{N})$ 가 된다.
for문에서 sqrt(n)을 쓰지 않은 것은 실수는 근사표현이기 때문에 피하기위해서 i*i<=n 형태로 구현한다.

4.1.1 문제 : 소수 찾기

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int cnt = 0; // 소수의 개수
	while (n-- > 0) {
		if (prime(sc.nextInt())) {
			cnt++;
		}
	}
	System.out.println(cnt);
}
public static boolean prime(int n) {
	if (n < 2) {
		return false;
	}
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

4.2 에라토스테네스의 체

임의의 수 N이 소수인지 판별하는데 걸리는 시간복잡도는 $O(\sqrt{N})$ 이다.
하지만 특정 범위내의 존재하는 소수를 구하는데 걸리는 시간은 어느정도일까?
N개가 존재한다치면 시간복잡도는 $O(N\sqrt{N})$ 될 것이다.
이는 너무 오랜 시간이 걸린다.

이때, 사용하는 것이 에라토스테네스의 체이다.

1부터 N까지의 범위 내에서 모든 소수를 구하는 예제를 보자

2부터 N까지 모든 수를 써놓는다.

소수가 아닌 것을 지워나갈 건데, 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

그 수는 소수이며 그 수의 배수를 모두 지운다.

이러한 과정을 거치게 되면 상당히 빠르게 소수를 찾을 수 있다.
int[] prime = new int[100]; // 소수 저장
int pn=0; // 소수의 개수
boolean[] check = new boolean[101]; // 지워지면 true 저장
int n = 100; // 100까지 소수
for(int i=2; i<=n; i++) {
	if(check[i] == false) {
		prime[pn++] = i;
		for(int j = i*i; j<=n; j+=i) {
			check[j] = true;
		}
	}
}
int j = i*i 부분을 i+i 또는 i*2로 바꾸는 것이 좋은데 그이유는 i*i를 하면 int 범위 즉, 정수 범위를 넘어가서 오버플로우가 발생할 수 도 있기 때문이다.

4.2.1 문제 : 소수 구하기

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int m = sc.nextInt();
	int n = sc.nextInt();
	boolean[] check = new boolean[n + 1];
	check[0] = check[1] = true;
	for (int i = 2; i * i <= n; i++) {
		for (int j = i + i; j <= n; j += i) {
			check[j] = true;
		}
	}
	for (int i = m; i <= n; i++) {
		if (check[i] == false) {
			System.out.println(i);
		}
	}
}
check 배열 크기를 n+1까지 한 이유는 인덱스 값으로 수를 동일시 하기 위함이다.

그래서 0번째 와 1번째 값을 true로 초기화 한다.

for문에서 i*i <= n부분은 제곱보다 작은 수는 이미 소수가 아니어서 지워졌음을 보장하기 때문에 제곱한 수가 n보다 크게되면 배열에 남은 수는 자연스럽게 소수가 된다.

4.2.2 문제 : 골드바흐의 추측

골드바흐의 추측이란

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다 라는 강한 골드바흐의 추측이다.

5보다 큰 모든 홀수는 세 소수의 합으로 표현이 가능하다 약한 골드바흐의 추측이다.

전자가 참이면 후자도 참이다.

하지만 이는 $10^{18}$ 이하에서는 참인 것이 증명되었을 뿐 아직 증명되지 않은 문제이다.

이 문제는 에라토스테네스의 체를 이용하면 빠르게 구할 수 있다.

설명

주어진 범위는 6이상 1,000,000이하이다. 따라서 배열의 크기를 1,000,001로 정한다.

에라토스테네스의 체 규칙에 따라 배열에 소수부분만 false로 남겨둔다.

이후 입력 n을 받을때마다 배열에서 1번 인덱스부터 값을 꺼내어 n-b번째 값이 false인지 판단한다.

1번 인덱스부터 하는 이유는 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다.라는 조건이 존재하는데, a가 제일 작을수록 저 조건을 만족하기 때문이다.

또한 n-b번째 값이 true이면 소수가 아니라는 것이다.
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	boolean[] check = new boolean[1000001];
	check[0] = check[1] = true;
	ArrayList<Integer> prime = new ArrayList<Integer>();
	for(int i=2; i*i<=1000000; i++) {
		if(check[i] == false) {
			prime.add(i);
			for(int j=i+i; j<=1000000; j+=i) {
				check[j] = true;
			}
		}
	}
	while(true) {
		int n = sc.nextInt();
		if(n == 0) {
			break;
		}
		for(int i=1; i<prime.size(); i++) {
			int p = prime.get(i);
			if(check[n-p] == false) {
				System.out.println(n + " = " + p + " + " + (n-p));
				break;
			}
		}
	}
}

5. 팩토리얼(Factorial)

팩토리얼이란
임의의 수 N이 있으면 1부터 N까지 곱하는 것이다. N!로 표기한다.
예를 들면 $6!$ 은 $1*2*3*4*5*6=720$ 이다.

팩토리얼의 값은 엄청 커지기 때문에 자료형을 주의깊게 설정해야 한다.

5.1 문제 : 팩토리얼

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int result = 1;
	for(int i=1; i<=n;i++) {
		result *=i;
	}
	System.out.println(result);
}

5.2 문제 : 팩토리얼 0의 개수

N!의 결과 값에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제이다.

이 문제는 N을 소인수분해 하여 2와 5가 몇 개 나오는지 알아야 한다.

왜냐하면 뒤에 0이 붙으려면 10을 곱해야하기 때문에 2 X 5 형태를 찾아야하는 것이다.

하지만 5의 개수가 항상 2의 개수보다 적기 때문에 5의 개수만 세주면 된다.

예를들어 100!이라 하면, 5의 배수를 전부 선택한다. 즉, 100 / 5 = 20
20개가 존재하고 여기에 25, 50, 75, 100 과같이 5가 두개씩 들어가는 것이 있다. 이때는 100 / 25 = 4 하여 추가 4개를 구할 수 있다.
따라서 0의 개수는 24개가 된다.
public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int ans = 0;
	for (int i = 5; i <= n; i *= 5) {
		ans += n / i;
	}
	System.out.println(ans);
}
n을 5로 나눈 몫을 카운트하면 된다.

5의 제곱으로 증가하면서 추가로 5가 사용된 개수를 합하면 된다.

5.3 문제 : 조합 0의 개수

$nCm$ 의 0의 개수를 구하는 문제이다.

$nCm = n! / ((n-m)! * m!)$ 에서 각각의 0의 개수를 구해서 $n!$ 의 0의 개수에서 빼주면 된다.

팩토리얼은 5의 개수가 적기때문에, 5의 개수만 세워줬지만, 조합은 어떻게 될 지 모르기 때문에 2와 5 둘다 동시에 세워줘야한다.
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	long n = sc.nextLong();
	long m = sc.nextLong();
	long two = 0, five = 0;
	for (long i = 2; i <= n; i *= 2) {
		two += n / i;
	}
	for (long i = 2; i <= n - m; i *= 2) {
		two -= (n - m) / i;
	}
	for (long i = 2; i <= m; i *= 2) {
		two -= m / i;
	}
	for (long i = 5; i <= n; i *= 5) {
		five += n / i;
	}
	for (long i = 5; i <= n - m; i *= 5) {
		five -= (n - m) / i;
	}
	for (long i = 5; i <= m; i *= 5) {
		five -= m / i;
	}
	System.out.println(Math.min(two, five));
}
범위가 n, m(0≤m≤n≤2,000,000,000) 이기 때문에 long 타입을 사용하였다.

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.

노력하는 배짱이

이전 포스트

TIL #4 후위표기법, 문자열 문제

다음 포스트

TIL #5 알고리즘 기초 - 수학

1. 수학

1.1 나머지연산

1.2 나머지 연산 성질

1.3 문제 백준 문제 : 나머지

2. 최대공약수(Greatest Common Divisor)

2.1 유클리드 호제법(Euclidean algorithm)

3. 최소공배수(Least Common Multiple)

3.1 문제 백준 문제 : 최대공약수와 최소공배수

3.2 문제 백준 문제 : 최소공배수

4. 소수

4.1 소수와 관련된 알고리즘

4.1.1 문제 : 소수 찾기

4.2 에라토스테네스의 체

4.2.1 문제 : 소수 구하기

4.2.2 문제 : 골드바흐의 추측

5. 팩토리얼(Factorial)

5.1 문제 : 팩토리얼

5.2 문제 : 팩토리얼 0의 개수

5.3 문제 : 조합 0의 개수

참고

TIL #4 후위표기법, 문자열 문제

TIL #6 알고리즘 기초 - 수학 (문제)

0개의 댓글