코딩 테스트를 준비하는 많은 분들이 알고리즘 문제의 난이도와 복잡성으로 인해 어려움을 겪고 있습니다. 오늘은 “신기한 소수 찾기”라는 주제로 한 문제를 통해, 소수(premium number)를 찾는 다양한 알고리즘을 소개하고, 자바를 이용해서 어떻게 효율적으로 문제를 해결할 수 있는지를 알아보겠습니다.
문제 설명
숫자 N이 주어질 때, N 이하의 모든 소수를 구하는 함수를 작성하시오. 여기서 소수는 1과 자기 자신만을 약수로 가지는 자연수를 말합니다.
입력: 첫 번째 줄에 자연수 N이 주어진다. (2 ≤ N ≤ 1000)
출력: N 이하의 모든 소수를 한 줄에 출력한다. 소수는 공백으로 구분한다.
예제
입력: 10 출력: 2 3 5 7
문제 이해 및 분석
위 문제를 해결하기 위해 알아야 할 것은 소수의 정의와 소수를 찾기 위한 기본적인 방법론입니다. 소수는 1과 자기 자신 이외의 자연수로 나눠지지 않는 숫자이므로, 이를 효과적으로 찾기 위해서는 나눗셈 연산을 활용할 수 있습니다.
하지만, 단순히 모든 숫자를 1부터 N까지 나눠가며 확인하는 방식은 시간 복잡도가 O(N^2)로 비효율적일 수 있습니다. 따라서 더 효율적인 알고리즘이 필요합니다. 우리는 체 방법(에라토스테네스의 체)이라는 알고리즘을 사용하여 소수를 효율적으로 찾을 수 있습니다.
에라토스테네스의 체(Eratosthenes’ sieve)
이 알고리즘은 다음과 같이 작동합니다:
- 2부터 N까지의 모든 자연수의 리스트를 준비합니다.
- 리스트에서 첫 번째 수(2)를 선택하고, 그 수의 배수를 모두 제거합니다.
- 다음 남은 수(3)를 선택하고, 그 수의 배수를 제거합니다.
- 이 과정을 N 이하의 수가 모두 제거될 때까지 반복합니다. 남은 수들이 모두 소수입니다.
자바 코드 구현
이제 우리는 위의 알고리즘을 자바로 구현해 보겠습니다.
public class PrimeSieve {
public static void main(String[] args) {
int N = 10; // 사용할 숫자 N
boolean[] isPrime = new boolean[N + 1];
// 초기화
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// 에라토스테네스의 체
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// 결과 출력
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
}
설명
위의 코드는 다음과 같은 과정을 거칩니다:
- 먼저 N을 입력받고, 2부터 N까지에 대한 boolean 배열을 초기화합니다. 배열의 각 인덱스는 해당 숫자가 소수인지 여부를 나타냅니다.
- 이후 에라토스테네스의 체 알고리즘을 적용하여 소수가 아닌 숫자의 인덱스를 false로 마크합니다.
- 마지막으로, isPrime 배열을 순환하면서 true인 인덱스를 출력하여 소수를 나열합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(N log(log(N)))로, N이 크더라도 효율적으로 작동합니다. 이는 단순히 모든 숫자를 나눌 때보다 훨씬 효율적입니다.
결론
이번 강좌에서는 소수를 찾기 위한 에라토스테네스의 체 알고리즘을 자바로 구현해 보았습니다. 다양한 알고리즘 문제를 풀 때, 이러한 기본적인 알고리즘을 숙지하고 있다면 더 높은 점수를 받을 수 있을 것입니다. 더 나아가, 코딩 테스트에서는 알고리즘뿐만 아니라 코드의 가독성 및 최적화도 중요한 점수 요소이므로 이를 유념하여 코딩하는 것이 필요합니다.
앞으로도 여러 알고리즘 문제를 함께 풀어보며 실력을 키워 보도록 합시다!