코딩 테스트는 현대 소프트웨어 공학에서 매우 중요한 부분입니다. 많은 기업들이 기술 면접에 코딩 문제를 포함시켜, 지원자의 알고리즘 및 문제 해결 능력을 평가합니다. 이번 강좌에서는 수학적 개념인 오일러 피(Euler’s Totient Function)에 대해 알아보겠습니다.
문제 설명
오일러 피 함수는 정수 n의 양의 정수 m의 개수를 반환합니다. m은 1 이상 n 이하의 정수이며, m과 n이 서로 소인 정수입니다. 즉, gcd(m, n) = 1을 만족하는 m의 개수를 구하는 것이 목표입니다.
문제: 주어진 정수 n에 대해 오일러 피 함수를 계산하시오.
입력 형식
- 1 ≤ n ≤ 106
출력 형식
- n의 오일러 피 값
예제
입력:
6출력:
2이론적 배경
오일러 피 함수는 다음과 같이 정의됩니다:
- n이 소수일 경우: ϕ(n) = n – 1
- n이 소수가 아닐 경우, n의 소인수 p를 이용하여: ϕ(n) = n × (1 – 1/p1) × (1 – 1/p2) × … × (1 – 1/pk)
이를 통해, n의 소인수를 찾아 그에 맞게 ϕ(n)를 계산할 수 있습니다.
C# 구현
이제 오일러 피 함수를 C#을 사용하여 구현해보겠습니다. 이 알고리즘의 시간 복잡도는 O(√n)으로, n의 소인수를 찾아내는데 효율적입니다.
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
Console.WriteLine(EulerPhi(n));
}
static int EulerPhi(int n)
{
int result = n; // 초기값을 n으로 설정
for (int p = 2; p * p <= n; p++)
{
// p가 n의 소인수인지 확인
if (n % p == 0)
{
// p로 n을 나눠서 소인수를 제거
while (n % p == 0)
{
n /= p;
}
result -= result / p; // 오일러 피 공식 적용
}
}
// 남은 n이 소수인 경우
if (n > 1)
{
result -= result / n;
}
return result; // 최종 결과 반환
}
}
코드 설명
위의 코드는 오일러 피 함수를 계산하기 위한 것으로, 다음과 같은 단계로 구성됩니다:
- 입력값 읽기: 사용자로부터 정수 n을 입력받습니다.
- 초기값 설정: 결과값 result를 입력받은 n으로 초기화합니다.
- 소인수 찾기: 2부터 n의 제곱근까지 반복하면서 n이 p로 나누어 떨어지는지 체크합니다.
- 소인수 제거: 소인수 p로 n을 나누어가며 n 자체에서 소인수를 제거합니다.
- 오일러 피 공식 적용: 현재 소인수인 p에 대해 ϕ(n) 공식을 적용하여 result 값을 업데이트합니다.
- 남은 소수 확인: 모든 소인수를 제하고 남은 n 값이 1보다 클 경우, p는 소수임으로 result에서 n을 제외합니다.
- 결과 반환: 최종 결과값을 반환합니다.
성능 최적화
이 알고리즘은 주어진 범위 내에서 매우 빠르게 동작합니다. 하지만 다양한 입력에 대해 빠른 계산을 위해, 미리 소수를 구해둘 수도 있습니다. 에라토스테네스의 체를 통해 소수를 구하고 해당 소수를 이용하여 오일러 피 값을 계산할 수 있습니다.
소수들을 저장하는 배열을 이용하여 함수를 조금 더 개선할 수 있습니다. 이 방법은 다른 수들과의 비교를 통해 속도가 올라가고, 메모리 사용도 최적화될 수 있습니다.
결론
오일러 피 함수는 메니지드 언어인 C#에서도 간단히 구현할 수 있으며, 이론과 코드의 결합을 통해 알고리즘 문제를 보다 효율적으로 해결할 수 있습니다. 이번 강좌를 통해 C#의 기초적인 함수, 유클리드 호제법을 이용한 최대공약수 구하기 등 다양한 기술을 활용하여 오일러 피를 구하는 방법을 학습하셨습니다.
앞으로의 코딩 테스트에서 더 많은 알고리즘 문제를 해결하기 위해 꾸준히 연습하시길 바랍니다!