알고리즘은 컴퓨터 사이언스의 핵심 개념 중 하나로, 특히 프로그래밍 문제 해결에 있어 매우 중요합니다.
이번 강좌에서는 ‘소수를 구하는’ 문제를 다루고, 이를 해결하기 위한 알고리즘과 C++ 코드를 상세히 설명하겠습니다.
소수는 1과 자기 자신만으로 나누어 떨어지는 자연수를 의미하며, 기본적인 수학 개념 중 하나입니다.
하지만 이 문제를 해결하는 데 있어 다양한 접근 방법이 있으며, 각기 다른 시간 복잡도를 가질 수 있습니다.
문제 설명
주어진 정수 N이 있을 때, 1부터 N까지의 모든 소수를 구하는 프로그램을 작성하시오.
소수는 1보다 큰 자연수 중에서 1과 자기 자신 외에는 약수가 없는 수입니다.
입력
첫째 줄에 자연수 N (1 ≤ N ≤ 10^6)이 주어진다.
출력
1부터 N까지의 모든 소수를 한 줄에 하나씩 출력한다.
예제
입력:
10
출력:
2
3
5
7
알고리즘 접근 방법
소수를 구하는 여러 방법이 있지만, 여기서는 ‘에라토스테네스의 체’라는 고전적인 방법을 사용해 볼 것입니다.
이 방법은 효율적이고 비교적 간단하게 소수를 찾을 수 있습니다.
에라토스테네스의 체는 다음과 같은 절차로 동작합니다.
- 1부터
N까지의 모든 숫자를 나열합니다. - 2부터 시작하여, 그 수의 배수를 모두 지웁니다.
- 다음 남은 수에 대해 위의 과정을 반복합니다.
- 남은 수를 소수로 간주하고 출력합니다.
시간 복잡도
에라토스테네스의 체 알고리즘은 약 O(N log log N)의 시간 복잡도를 가집니다.
이는 N이 커질수록 효율적이며, N = 10^6인 경우에도 빠른 속도를 보장합니다.
C++ 코드
아래는 위의 알고리즘을 C++로 구현한 코드입니다.
각 단계에 주석을 달아 이해를 돕도록 하겠습니다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N; // 사용자로부터 입력을 받습니다.
// N+1 크기의 벡터를 생성하고, 모든 값을 true로 초기화합니다.
vector<bool> isPrime(N + 1, true);
isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아닙니다.
// 2부터 N의 제곱근까지 반복합니다.
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) { // i가 소수라면,
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false; // i의 배수는 소수가 아닙니다.
}
}
}
// 결과를 출력합니다.
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
cout << i << "\n"; // 소수인 경우 출력합니다.
}
}
return 0;
}
코드 설명
– #include <iostream> 및 #include <vector>:
C++의 입출력 및 벡터 라이브러리를 포함합니다.
– int N;: 사용자 입력을 받을 정수 변수를 선언합니다.
– vector<bool> isPrime(N + 1, true);:
N까지의 숫자에 대해 소수 여부를 저장할 벡터를 선언하며,
초기값은 모두 true로 설정합니다.
(0과 1은 소수가 아니므로 별도로 설정)
– for (int i = 2; i * i <= N; i++):
2부터 시작해 N의 제곱근까지 반복하며 소수를 찾습니다.
– 내부의 for (int j = i * i; j <= N; j += i) 루프는
i의 배수를 지우는 역할을 합니다.
– 마지막으로 isPrime[i]가 true인 모든 인덱스를 출력합니다.
결론
이번 강좌에서는 소수를 구하는 문제를 해결하기 위한 알고리즘을 소개하고
C++ 코드를 구현해보았습니다. 에라토스테네스의 체 알고리즘은 효율적으로 소수를 찾을 수 있는 방법이며,
코딩 테스트에서도 자주 출제되는 문제입니다.
알고리즘과 코드를 숙지하여 자신감 있게 코딩 테스트에 도전해 보시기 바랍니다!