코딩 테스트 준비 중 수학과 알고리즘 문제에 대한 이해는 매우 중요합니다. 오늘은 오일러 피 함수에 대해 논의하고 이를 C++로 구현하는 방법을 알아보겠습니다. 오일러 피 함수는 주어진 정수 n
보다 작거나 같은 양의 정수와 서로소인 정수의 개수를 반환하는 함수입니다. 이는 수론에 많은 응용이 있으며, 수학적 문제를 해결하는 데 유용합니다.
1. 오일러 피 함수 소개
오일러 피 함수는 다음과 같이 정의됩니다:
- 주어진 n에 대해서, φ(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk),
여기서 p1, p2, … pk는 n의 서로소인 모든 소수입니다. 예를 들어, φ(6)은 다음과 같이 계산됩니다:
- n = 6, 소수 p = 2, 3
- φ(6) = 6 * (1 – 1/2) * (1 – 1/3) = 6 * 1/2 * 2/3 = 2
1.1 오일러 피 함수의 성질
- φ(1) = 1
- 만약 p가 소수이고 k가 양의 정수일 때, φ(p^k) = p^k * (1 – 1/p)
- n의 두 수 a, b가 서로소일 때, φ(ab) = φ(a) * φ(b)
2. 문제 설명
문제: 주어진 정수 n
에 대해 오일러 피 함수를 계산하는 C++ 프로그램을 작성하시오.
입력: 정수 n
(1 ≤ n ≤ 106)
출력: 정수 φ(n)
3. 알고리즘 설계
오일러 피 함수를 직접 계산하는 방법은 비효율적일 수 있습니다. 소수를 미리 구한 후 위에서 정의한 식을 이용하여 φ(n)을 계산할 수 있습니다. 이를 위해 다음과 같은 단계로 알고리즘을 설계합니다.
- 먼저, 에라토스테네스의 체를 사용하여 n 이하의 모든 소수를 구합니다.
- 구한 소수를 이용해 φ(n)을 계산합니다.
3.1 에라토스테네스의 체
에라토스테네스의 체는 소수를 신속하게 찾기 위한 고전적인 알고리즘입니다. 이 알고리즘은 시간 복잡도가 O(n log log n)으로 매우 효율적입니다.
4. C++ 코드 구현
이제 전체 알고리즘을 C++ 코드로 구현해 보겠습니다. 다음은 오일러 피 함수를 계산하는 C++ 코드입니다.
#include <iostream>
#include <vector>
using namespace std;
// 오일러 피 함수 계산
int eulerPhi(int n) {
int result = n; // 초기값은 n
for (int i = 2; i * i <= n; i++) {
// 만약 i가 n의 약수라면
if (n % i == 0) {
// 소수를 곱해서 결과를 조정합니다
while (n % i == 0) {
n /= i;
}
result -= result / i; // 결과 계산
}
}
// 마지막에 남은 n이 소수일 경우
if (n > 1) {
result -= result / n; // 소수에 대한 결과 처리
}
return result;
}
int main() {
int n;
cout << "정수를 입력하세요: ";
cin >> n;
cout << "φ(" << n << ") = " << eulerPhi(n) << endl;
return 0;
}
5. 코드 설명
위 코드는 다음과 같은 단계로 작동합니다:
eulerPhi(int n)
함수는 주어진 정수 n에 대해 오일러 피 함수를 계산하고 반환합니다.- 변수
result
는 초기값으로 n을 가지며, 소수가 발견될 때마다 이 값을 업데이트합니다. - 소수
i
가 n의 약수일 경우, n을 i로 나누어가며 i의 배수를 제거합니다. 이 과정에서 소수에 따라 결과를 조정합니다. - 모든 소수를 검사한 후, 만약 n이 1보다 큰 경우 (즉, n이 소수인 경우) 추가로 처리합니다.
6. 코드 테스트
코드를 완료한 후, 다양한 테스트 케이스로 함수를 검증해 볼 수 있습니다. 예를 들면:
- n = 1일 때, φ(1) = 1
- n = 6일 때, φ(6) = 2
- n = 9일 때, φ(9) = 6
7. 성능 분석
위 알고리즘은 O(√n)의 시간복잡도를 가지고 있으며, n이 최대 106일 때도 상대적으로 빠르게 작동합니다. 공간 복잡도는 O(1)로 추가적인 메모리 사용이 거의 없습니다. 이러한 이유로 대규모 데이터에서도 효율적으로 사용될 수 있습니다.
8. 결론
오늘의 포스트에서는 오일러 피 함수의 개념과 이를 C++로 구현하는 방법을 배웠습니다. 오일러 피 함수는 다양한 수학적 문제의 해결에 유용하게 사용될 수 있으며, 컴퓨터 프로그래밍에서 큰 역할을 합니다. 이러한 문제를 풀어보는 것은 코딩 테스트 준비에 큰 도움이 될 것입니다.
코드에 대한 질문이나 피드백이 있다면 댓글로 남겨 주세요! 다음 포스트에서는 또 다른 알고리즘 문제를 다룰 예정입니다. 감사합니다!