알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다.
자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다.
내용이 이상하다면 지적해주시면 감사하겠습니다. 👍
벌써 알고리즘 특강 4일차 입니다.
정수론에 대해서 배웠는데
소수와 최대공약수와 관련된 알고리즘 이었습니다.
유클리드 호제법
유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 알고리즘 입니다.
두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면
a와 b의 최대공약수는 b와 r의 최대공약수와 같다 성질을 이용합니다.
이제부터 자연수 a, b의 최대공약수를 gcd(a, b)라고 하겠습니다. (단, a > b)
그렇다면 gcd(a ,b)는 어떤 식으로 찾아지는 걸까요?
(a % b) = ?
60 % 15 = 0;
15 % 0
b의 자리가 0이 될 때의 a의 값이 최대공약수가 됩니다.
다른 예시를 또 들자면
96 % 28 = 12;
28 % 12 = 4;
12 % 4 = 0;
4 % 0
96과 28의 최대 공약수는 4입니다.
이러한 성질을 이용해서 최대공약수를 구하는 메서드를 작성하면 아래와 같습니다.
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
베주 항등식
베주 항등식을 이용해 알고리즘 문제를 푸는데 중요한 역할을 하곤합니다.
베주 항등식이 무엇이냐 ?
바로 다음과 같습니다.
정수 a, b의 최대공약수를 gcd(a, b)로 나타날 때,
확장 유클리드 호제법을 이용하여 ax + by = gcd(a, b)의 해가 되는 정수 a, b 짝을 찾아낼 수 있습니다.
(보통 a, b 중 하나는 음수가 나옵니다.)
이러한 식을 베주의 항등식이라고 합니다
좀 더 내용이 있다고 하면 gcd(a, b) = 1 일 경우
즉 a, b가 서로 서로소인 경우에 유용합니다.
확장 유클리드 호제법
ax + by = c 형태의 방정식이 주어질 때
이 방정식을 만족 시키는 정수 (x, y)를 각각 (s, t)라고 정의하고,
우변의 상수값에 유클리드 호제법 (r2 - qr1 = r)을 이용하여
반복적으로 구하는 값들을 r이라고 하면 방정식을 만족시키는 정수 해 s와t가 반드시 존재한다.
9x + 5y = 1 라는 방정식이 있을 때 x, y를 구하는 법은 다음과 같다.
s. t. r. q.
1. 0. 9.
0. 1. 5.
1. -1. 4. 1.
-1. 2. 1. 1.
즉, 9 * (1) + 5 * (2) = 1; 으로 성립한다.
ax + by = c 라는 방정식에
확정 유클리드 호제법을 이용하여 방정식을 푸는 방식으로 문제 풀어야 하는 경우가 많습니다.
에라토스테네스의 체
에라토스테네스의 체는 소수를 구하는 방법입니다.
먼저 2를 시작합니다.
2의 숫자가 없어지지 않았으니 2는 소수로 판단됩니다.
이제 2를 제외한 2의 배수를 없애고
3의 숫자도 없어지지 않았으니 3은 소수로 판단됩니다.
3을 제외한 3의 배수를 없앱니다.
4의 배수를 없애줍니다.
다음의 숫자가 5인데 아직 지워지지 않은 숫자이기에 5도 소수로 판단됩니다.
5를 제외한 5의 배수를 없앱니다.
이런 식으로 계속해서 나아가면서 소수를 구할 수 있습니다.
코드로 구현하면 아래와 같습니다.
boolean[] isNotPrime = new int[10000] // 10000까지의 숫자를 확인하겠습니다.
for (int i = 2; i <= 10000; i++) {
for (int j = i * 2; j <= 10000; j += i) {
isNotPrime[j] = true;
}
}
특정 소수를 구하는데 팁은
N이라는 숫자가 소수인지 판별하기 위해서는 2 ~ Math.sqrt(N) 의 숫자 중에 하나로 나누어 떨어지는지만 확인하면 됩니다.
boolean isPrime = true;
int value = 29;
for (int i = 2; i <= Math.sqrt(value); i++) {
if (value % 2 == 0) {
isPrime = false;
break;
}
}
댓글