코딩테스트에서 자주 등장하는 알고리즘 문제 중 하나는 수학 관련 문제입니다. 그 중에서 오일러 피 함수(φ)는 중요하게 다뤄지는 주제입니다. 이 강좌에서는 오일러 피 함수를 정의하고, 문제를 해결하기 위한 알고리즘을 구현해보겠습니다.
오일러 피 함수란?
오일러 피 함수는 주어진 양의 정수 n에 대해 1 이상 n 이하의 정수 중에서 n과 서로소인 수의 개수를 셉니다. 예를 들어, n이 5일 때, 1, 2, 3, 4, 5 중 n과 서로소인 수는 1, 2, 3, 4이므로 φ(5) = 4입니다.
정의
오일러 피 함수는 다음과 같은 성질을 가지고 있습니다:
- φ(1) = 1
- 소수 p에 대하여, φ(p) = p – 1
- p가 서로소인 두 수 a, b에 대해서, φ(a*b) = φ(a) * φ(b)
문제 설명
이제 오일러 피 함수를 구현하는 알고리즘 문제를 살펴보겠습니다. 문제는 주어진 정수 n에 대해 φ(n)을 계산하는 프로그램을 작성하는 것입니다.
문제 예시
입력: 10
출력: 4
설명: 1, 3, 7, 9가 10과 서로소인 수입니다.
문제 해결 과정
문제를 해결하기 위해 몇 가지 단계를 밟겠습니다:
1단계: 알고리즘 이해하기
φ(n)을 계산할 때 n의 소인수를 이용하는 것이 빠릅니다. 만약 n이 소수라면 φ(n) = n – 1입니다. 소수를 찾는 방법으로는 에라토스테네스의 체를 사용할 수 있습니다.
2단계: 소인수 분해
n을 소인수로 나누어 가면서 φ(n)을 계산하겠습니다. 예를 들어, n이 60이라면:
소인수: 2, 3, 5
φ(60) = 60 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 16
3단계: C# 구현하기
이제 C#으로 알고리즘을 구현해 보겠습니다. 아래는 코드입니다:
using System;
class Program
{
public static int EulerPhi(int n)
{
int result = n; // 초기 결과는 n
for (int i = 2; i * i <= n; i++)
{
// i가 n의 소인수인지 확인
if (n % i == 0)
{
// n을 i로 나누면서 소인수 제거
while (n % i == 0)
{
n /= i;
}
// 결과에 (1 - 1/i) 곱하기
result -= result / i;
}
}
// 마지막 소인수 처리 (n이 소수일 경우)
if (n > 1)
{
result -= result / n;
}
return result;
}
static void Main()
{
Console.Write("정수 n을 입력하세요: ");
int n = int.Parse(Console.ReadLine());
int phi = EulerPhi(n);
Console.WriteLine($"φ({n}) = {phi}");
}
}
4단계: 테스트
코드를 실행해보며 다양한 입력 값을 테스트해보겠습니다. 예를 들어:
입력: 10
출력: φ(10) = 4
입력: 20
출력: φ(20) = 8
입력: 1
출력: φ(1) = 1
결론
이번 강좌에서는 오일러 피 함수에 대해 설명하고, 이를 C#으로 효율적으로 구현하는 방법을 살펴보았습니다. 앞서 설명한 과정을 통해 문제를 해결하는 데 필요한 알고리즘과 코딩 스킬을 연습할 수 있기를 바랍니다.
추가 학습 자료
오일러 피 함수의 성질에 대해 더 깊이 알고 싶다면 아래 자료를 참조해 보시기 바랍니다: