1. 서론
코딩 테스트를 대비하기 위한 여러 알고리즘 문제들이 존재합니다. 그중에서도 수학적인 사고가 중요한 문제들이 많습니다. 오늘은 Euler’s Totient Function, 즉 오일러 피 함수에 대해 알아보겠습니다. 오일러 피 함수는 정수 n에 대해 1부터 n까지의 정수 중에서 n과 서로소인 정수의 개수를 반환합니다. 이 함수는 수론에서 매우 중요한 역할을 하며, 특히 암호학적 알고리즘에서 자주 사용됩니다.
2. 오일러 피 함수 이해하기
오일러 피 함수 φ(n)은 다음과 같은 성질을 가집니다:
- φ(1) = 1
- p가 소수일 때, φ(p) = p – 1
- p가 소수이고 k가 자연수일 때, φ(p^k) = p^k – p^(k-1)
- 두 수가 서로소일 때, φ(m * n) = φ(m) * φ(n)
오일러 피 함수를 구하는 가장 일반적인 방법은 소수를 이용한 약수 분해입니다. 주어진 정수 n의 소인수 분해를 통해 해당 값을 구할 수 있습니다. 예를 들어, n = 12일 경우, 소인수 분해는 2^2 * 3^1로 표현할 수 있으며, 이 때 φ(12)의 값을 구하기 위해 다음 공식을 사용할 수 있습니다.
φ(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk)
여기서 p1, p2, …, pk는 n의 소인수입니다. 따라서 12의 경우 φ(12)는 다음과 같이 계산됩니다:
φ(12) = 12 * (1 – 1/2) * (1 – 1/3) = 12 * 1/2 * 2/3 = 4
3. 문제 정의
주어진 정수 n에 대해 φ(n)의 값을 반한하는 코틀린 함수를 구현하는 문제입니다. 이 문제는 단순히 φ(n)의 값을 구하는 것뿐만 아니라, 알고리즘의 효율성을 고려하여 구현해야 합니다.
**문제**: 자연수 n이 주어질 때, 오일러 피 함수 φ(n)의 값을 반환하는 함수를 코틀린으로 구현하시오.
4. 문제 풀이 과정
4.1 알고리즘 설계
오일러 피 함수를 계산하는 데 있어 효율적인 방법은 소인수 분해를 이용하는 것입니다. 알고리즘은 다음과 같은 단계로 구성됩니다:
- 입력받은 자연수 n에 대해 초기값으로 result를 n으로 설정합니다.
- 2부터 n의 제곱근까지의 모든 정수 p에 대해:
- 만약 p가 n의 소인수라면, result = result * (1 – 1/p) 하고 n을 p로 나눈다.
- 최종적으로 n이 1보다 크다면, n은 소수이므로 result = result * (1 – 1/n)으로 처리한다.
- result를 반환한다.
4.2 코딩
fun eulerTotient(n: Int): Int {
var result = n
var p: Int = 2
var tempN = n
while (p * p <= tempN) {
if (tempN % p == 0) {
// p가 소인수일 경우
while (tempN % p == 0) {
tempN /= p
}
result *= (p - 1)
result /= p
}
p++
}
// 남은 소수
if (tempN > 1) {
result *= (tempN - 1)
result /= tempN
}
return result
}
4.3 코드 설명
위의 코드는 다음과 같은 과정을 통해 오일러 피 함수를 구현합니다:
- 변수 result를 n으로 초기화하여 n에 대한 φ(n)의 값을 보관합니다.
- p는 2부터 시작하여 n의 제곱근까지 모든 정수를 순회합니다.
- 만약 n이 p로 나누어 떨어지면, p는 n의 소인수입니다.
- n을 p로 완전히 나누고 result를 업데이트합니다.
- 모든 소인수를 처리한 후, 만약 n이 1보다 크다면, n은 유일한 소수로 결과에 반영합니다.
5. 성능 분석
위의 알고리즘은 O(√n)의 시간 복잡도를 가지므로 매우 효율적입니다. 대량의 데이터에서도 빠르게 φ(n)을 계산할 수 있습니다. 1,000,000과 같은 큰 수에 대해 실행해도 성능은 문제가 없습니다.
6. 예제
다음은 함수의 사용 예시입니다:
fun main() {
println("φ(1) = " + eulerTotient(1)) // 1
println("φ(12) = " + eulerTotient(12)) // 4
println("φ(13) = " + eulerTotient(13)) // 12
println("φ(30) = " + eulerTotient(30)) // 8
println("φ(100) = " + eulerTotient(100)) // 40
}
7. 결론
오늘은 Euler’s Totient Function을 이해하고 이를 코틀린으로 구현하는 방법을 알아보았습니다. 이 문제는 코테에서 자주 등장하는 내용 중 하나이며, 수학적인 사고와 알고리즘적 접근 방식이 모두 요구되므로 연습이 필요합니다. 다양한 테스트 케이스를 통해 구현한 함수를 검증하고, 더 나아가 확장된 문제도 시도해보시기 바랍니다.
이와 같은 알고리즘 문제 풀이 강좌를 통해 좀 더 많은 사람들과 지식을 공유하고, 함께 성장할 수 있기를 바랍니다.
8. 참고 문헌
- Concrete Mathematics: A Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
- Introduction to Algorithms by Thomas H. Cormen et al.
- Number Theory: A Modern Introduction by Andrew P. Erdos