소개
알고리즘 문제 해결은 프로그래밍의 기본이며, 코딩 면접에서도 중요한 역할을 합니다. 본 강좌에서는 오일러 피 함수(Euler’s Totient Function)를 스위프트로 구현해보겠습니다. 오일러 피 함수는 주어진 양의 정수 n에 대해 n과 서로소인 정수의 개수를 반환합니다. 즉, 1부터 n까지의 정수 중에서 n과 최대공약수가 1인 정수를 세는 함수입니다.
알고리즘 문제 설명
문제: 정수 n(1 ≤ n ≤ 106)이 주어질 때, 오일러 피 함수를 계산하여 반환하시오.
예를 들어, n이 6일 경우, 1, 2, 3, 4, 5, 6 중에서 1과 서로소인 수는 1, 5이며, 2와 서로소인 수는 1, 3, 5이므로 최종적으로 2가 됩니다. 따라서 φ(6) = 2입니다.
문제 접근 방법
오일러 피 함수는 주어진 수의 소인수를 활용하여 효율적으로 계산할 수 있습니다. 이 함수는 다음의 성질을 통해 구할 수 있습니다:
- φ(p) = p – 1 (p는 소수)
- φ(pk) = pk – pk-1 (p는 소수, k는 양의 정수)
- φ(mn) = φ(m) * φ(n) (m과 n은 서로소)
따라서, 오일러 피 함수는 소인수 분해를 통해 계산할 수 있습니다. 문제를 해결하기 위해 다음과 같은 단계로 진행할 것입니다:
- 사용자로부터 정수 n을 입력받습니다.
- n의 소인수를 찾고, 이를 이용해 오일러 피 함수를 계산합니다.
- 계산 결과를 출력합니다.
스위프트 코드 구현
이제 스위프트를 사용하여 오일러 피 함수를 구현해보겠습니다. 코드는 다음과 같습니다:
Euler’s Totient Function in Swift
func eulerTotient(n: Int) -> Int {
var result = n
var i = 2
while i * i <= n {
if n % i == 0 {
while n % i == 0 {
n /= i
}
result -= result / i
}
i += 1
}
if n > 1 {
result -= result / n
}
return result
}
// 예시 사용
let n = 6
print("φ(\(n)) = \(eulerTotient(n: n))") // Output: φ(6) = 2
코드 설명
위 코드는 오일러 피 함수를 계산하는 메소드를 정의하고 있습니다. 각 단계는 다음과 같이 이루어집니다:
- 초기화: 입력받은 n 값을 result에 저장합니다. result는 최종 결과를 저장할 변수입니다.
- 소인수 분해: n의 소인수를 찾기 위해 2부터 시작하여 i를 증가시키며 반복합니다. i의 제곱이 n보다 작거나 같을 때까지 진행합니다.
- 조건 확인: n이 i로 나누어 떨어지면, while 문을 통해 n을 i로 나누어줍니다. 이 과정은 n에서 i로 나누어질 수 있는 만큼 반복됩니다.
- 결과 업데이트: 현재 소인수 i에 대해 result를 업데이트합니다. n은 phi 함수의 성질을 바탕으로 업데이트 됩니다.
- 남은 소인수 처리: 반복이 끝난 후, 만약 n이 1보다 큰 경우(소수를 찾은 경우)에는 result를 최종적으로 업데이트합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 O(√n)입니다. 이는 n의 소인수를 찾기 위해 이중 루프 구조를 가졌기 때문입니다. 최악의 경우 소인수는 n의 제곱근까지 검사해야 하며, 이 과정에서 n을 계속 나누어가는 연산이 있기 때문에, 전체적으로 굉장히 효율적인 알고리즘입니다.
결론
이 강좌에서는 오일러 피 함수를 구현하여 서로소의 개수를 계산하는 방법을 배웠습니다. 이 문제는 다양한 알고리즘 시험에서 흔히 출제되는 주제이며, 소인수 분해를 활용하여 효율적으로 해결할 수 있습니다. 스위프트를 통해 구현함으로써 프로그래밍 스킬을 향상시키고, 알고리즘에 대한 깊은 이해를 돕기 위한 좋은 연습이 되었기를 바랍니다.