자바스크립트 코딩테스트 강좌, 오일러 피 함수 구현하기

안녕하세요, 여러분! 오늘은 자바스크립트로 오일러 피 함수(𝜙(n))를 구현하는 방법에 대해 자세히 설명드리겠습니다. 오일러 피 함수는 주어진 정수 n보다 작거나 같은 정수 중 n과 서로 소인 정수의 개수를 나타냅니다. 이 문제는 수론 관련 알고리즘 문제에서 매우 자주 등장하며, 다양한 코딩 테스트에서 유용하게 활용될 수 있습니다.

오일러 피 함수란?

오일러 피 함수 𝜙(n)은 n과 서로 소인 1부터 n까지의 양의 정수의 개수를 반환합니다. 다시 말하면, 두 수 a와 b가 서로 소라는 것은 두 수의 최대공약수(GCD)가 1일 때를 의미합니다.

예를 들어:

𝜙(1) = 1 (1과 서로 소인 수는 1 하나뿐)
𝜙(2) = 1 (2보다 작고 2와 서로 소인 수는 1)
𝜙(3) = 2 (3보다 작고 3과 서로 소인 수는 1, 2)
𝜙(4) = 2 (4보다 작고 4와 서로 소인 수는 1, 3)
𝜙(5) = 4 (5보다 작고 5와 서로 소인 수는 1, 2, 3, 4)

문제 정의

이제 코딩 테스트 문제를 정의해보겠습니다.

문제: 주어진 정수 n에 대해 오일러 피 함수를 계산하는 함수를 작성하라.
입력: 정수 n (1 ≤ n ≤ 10⁶)
출력: 오일러 피 함수 𝜙(n)의 값

문제 해결 접근법

오일러 피 함수를 계산하는 방법에는 여러 가지가 있습니다. 가장 효율적인 방법은 에라토스테네스의 체를 변형하여 𝜙(n) 값을 한 번에 구하는 것입니다. 이 방법의 시간 복잡도는 O(n log log n)입니다.

오일러 피 함수의 성질

𝜙(n)을 계산하기 위해 필요한 중요한 성질은 다음과 같습니다:

𝜙(p) = p – 1, 여기서 p는 소수
𝜙(p₁ * p₂ * … * p_k) = p₁ * p₂ * … * p_k * (1 – 1/p₁) * (1 – 1/p₂) * … * (1 – 1/p_k)
𝜙(n) = n * (1 – 1/p₁) * (1 – 1/p₂) * … * (1 – 1/p_k), 여기서 p_i는 n의 소인수들입니다.

자바스크립트 코드 구현

위의 성질을 바탕으로 오일러 피 함수를 구현하는 코드를 작성해보겠습니다.


function eulerPhi(n) {
    // 배열 선언 및 초기화
    const phi = Array.from({ length: n + 1 }, (_, i) => i);
    
    // 에라토스테네스의 체를 사용한 소수 찾기
    for (let p = 2; p <= n; p++) {
        if (phi[p] === p) { // p가 소수인 경우
            for (let k = p; k <= n; k += p) {
                // 𝜙(k) 값 업데이트
                phi[k] = Math.floor(phi[k] * (1 - 1 / p));
            }
        }
    }
    
    // n에 대한 phi(n) 반환
    return phi[n];
}

// 테스트 케이스
console.log(eulerPhi(1));  // 1
console.log(eulerPhi(2));  // 1
console.log(eulerPhi(3));  // 2
console.log(eulerPhi(4));  // 2
console.log(eulerPhi(5));  // 4

코드 설명

코드는 다음과 같이 작동합니다:

우선 n + 1 크기의 배열 phi를 생성하고, 각 요소를 그 자체로 초기화합니다. phi[i]는 i를 초기값으로 가집니다.
2부터 n까지 반복하면서, 각 수 p가 소수인지 검사합니다. 이를 위해, phi[p]가 p와 같은 경우 소수로 간주합니다.
p가 소수일 경우, p의 배수를 찾아 phi[k] 값을 업데이트합니다. 업데이트는 𝜙(k) = 𝜙(k) * (1 – 1/p)로 수행합니다.
최종적으로, phi[n] 값을 반환하여 n에 대한 오일러 피 함수의 값을 계산합니다.

복잡도 분석

위 코드의 시간 복잡도는 O(n log log n)입니다. 이는 에라토스테네스의 체를 사용하는 방법 때문입니다. 공간 복잡도는 O(n)입니다, 배열 phi를 저장하기 위해 n의 크기만큼의 공간이 필요합니다.

결론

지금까지 자바스크립트로 오일러 피 함수를 구현하는 방법에 대해 알아보았습니다. 이 방법은 알고리즘 테스트 및 수론에 매우 유용하며, 효율적으로 오일러 피 값을 계산할 수 있습니다. 이 코드를 활용하여 다양한 문제를 해결해 보시기 바랍니다.

더 나아가기

비슷한 문제를 풀어보고 싶다면, 최대공약수나 최소공배수를 사용하는 문제를 해결해보는 것 또한 좋은 연습이 될 것입니다. 또한 수론의 다른 개념인 소수 판별, 소수 생성기 등을 연구해보는 것도 추천드립니다. 수학적 사고를 통해 알고리즘에 대한 이해도를 높여보세요!