안녕하세요, 여러분! 오늘은 자바스크립트를 사용한 코딩테스트에서 중요한 알고리즘 중 하나인 확장 유클리드 호제법(Extended Euclidean Algorithm)에 대해 알아보겠습니다. 이 강좌에서는 확장 유클리드 호제법의 개념, 이를 이용한 문제풀이 과정, 그리고 실질적인 코드 예제를 제공합니다.
1. 문제 설명
문제를 다음과 같이 정의하겠습니다. 두 정수 A와 B가 주어지면, AX + BY = GCD(A, B)를 만족하는 정수 X와 Y를 구하는 문제입니다. 여기서 GCD는 최대공약수를 의미합니다.
예제
입력: A = 30, B = 21
출력: X = 1, Y = -1, GCD = 3
풀이: 30 * 1 + 21 * (-1) = 3
2. 개념 설명
확장 유클리드 호제법은 두 정수의 최대공약수(GCD)를 계산할 뿐만 아니라, 이로부터 특정 계수들을 찾는 방법입니다. 이는 주로 다음의 수식에서 사용됩니다:
AX + BY = GCD(A, B)
여기서 A와 B는 주어진 두 정수, X와 Y는 우리가 찾고자 하는 정수입니다. 만약 GCD가 1이라면, A와 B는 서로 소이므로 X와 Y는 모듈러 역수를 찾는 데에도 사용됩니다.
3. 접근 방법
우리는 GCD를 구하는 일반적인 유클리드 알고리즘을 기반으로 확장 유클리드 알고리즘을 구현할 것입니다. 알고리즘의 주요 아이디어는 다음과 같습니다:
- 두 정수 A와 B를 입력받습니다.
- If B는 0이면, GCD는 A이며, X는 1, Y는 0입니다.
- 그렇지 않으면, 유클리드 호제법을 사용하여 B와 A % B로 재귀 호출합니다.
- 재귀 호출의 결과를 이용해 X와 Y의 값을 계산합니다.
4. 알고리즘 구현
다음은 확장 유클리드 알고리즘을 자바스크립트로 구현한 예제입니다:
function extendedGCD(a, b) {
if (b === 0) { // Base case
return { gcd: a, x: 1, y: 0 };
}
// Recur with the new parameters b and a % b
const { gcd, x: x1, y: y1 } = extendedGCD(b, a % b);
const x = y1;
const y = x1 - Math.floor(a / b) * y1;
return { gcd, x, y };
}
// Test the function with example values
const a = 30;
const b = 21;
const { gcd, x, y } = extendedGCD(a, b);
console.log(`GCD: ${gcd}, X: ${x}, Y: ${y}`);
5. 코드 설명
위 코드에서 우리는 재귀적으로 GCD를 구하고 있습니다. 기본 조건에서는 B가 0일 때 GCD는 A가 되고, 이 때 X는 1, Y는 0이 됩니다. 그 후, 반환된 X와 Y 값을 이용해 새로운 X와 Y를 계산하여 최종적으로 우리가 원하는 결과를 얻습니다.
6. 테스트 케이스
이제 다양한 테스트 케이스를 통해 위의 함수를 검증해보겠습니다.
// Test cases
const testCases = [
{ a: 30, b: 21 },
{ a: 48, b: 18 },
{ a: 56, b: 15 },
{ a: 101, b: 10 },
];
testCases.forEach(({ a, b }) => {
const { gcd, x, y } = extendedGCD(a, b);
console.log(`A: ${a}, B: ${b} => GCD: ${gcd}, X: ${x}, Y: ${y}`);
});
7. 정리
오늘은 확장 유클리드 호제법에 대해 알아보았습니다. 이 알고리즘은 두 정수의 최대공약수를 구하고, 이에 대한 특정 계수를 찾는 데 매우 유용합니다. 특히 모듈러 연산이나 복잡한 알고리즘 문제에서 종종 활용되므로, 충분히 이해하고 연습하는 것이 중요합니다.
이 글에서 사용한 알고리즘이 여러분의 코딩 시험 준비에 도움이 되길 바랍니다. 추가 질문이 있다면 댓글로 남겨주세요!