코틀린 코딩테스트 강좌, 소수 구하기

코잡코딩 능력을 강화하는 데 필요한 여러 가지 문제를 공부하며 소수를 구하는 알고리즘에 대해 알아보겠습니다. 소수(prime number)는 1과 자기 자신으로만 나누어 떨어지는 자연수를 의미합니다. 소수는 수학에서 중요한 역할을 하며, 다양한 알고리즘 문제에서 자주 출제됩니다. 이러한 문제를 해결하기 위한 효율적인 알고리즘을 배우는 것은 코딩 면접에 대비하는 데 큰 도움이 됩니다.

문제 설명

주어진 자연수 N 이하의 모든 소수를 구하는 알고리즘을 작성하세요.

입력

  • 자연수 N (2 ≤ N ≤ 100,000)

출력

  • N 이하의 모든 소수를 한 줄에 공백으로 구분해 출력합니다.

문제 접근 방식

소수를 구하는 방법에는 여러 가지가 있지만, 여기서는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용할 것입니다. 이 알고리즘은 주어진 범위 내의 모든 소수를 효율적으로 찾는 방법 중 하나입니다. 특히, 시간 복잡도가 O(n log log n)로 매우 효율적이기 때문에 큰 수의 소수를 구하는 데 적합합니다.

에라토스테네스의 체란?

에라토스테네스의 체는 다음과 같은 단계로 진행됩니다:

  1. 2부터 N까지의 모든 자연수를 나열합니다.
  2. 2는 소수이므로 그 배수(4, 6, 8, …)를 모두 제거합니다.
  3. 다음으로 남아있는 수 중 가장 작은 수(3)를 소수로 간주하고, 그 배수(6, 9, …)를 모두 제거합니다.
  4. 이 과정을 N의 제곱근까지 반복하며, 남아있는 모든 수는 소수입니다.

코드 구현

코틀린 코드


fun sieveOfEratosthenes(n: Int): List {
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false // 0은 소수가 아님
    isPrime[1] = false // 1은 소수가 아님

    for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..n step i) {
                isPrime[j] = false // i의 배수는 소수가 아님
            }
        }
    }

    return (2..n).filter { isPrime[it] } // 소수 목록 반환
}

fun main() {
    val n = readLine()!!.toInt()
    val primes = sieveOfEratosthenes(n)
    println(primes.joinToString(" ")) // 소수 출력
}

코드 설명

위 코드는 코틀린을 사용하여 에라토스테네스의 체 알고리즘을 구현한 것입니다. 이제 각 부분을 살펴보겠습니다:

  • BooleanArray(n + 1) { true }: N까지의 모든 숫자를 소수로 가정하여 초기화합니다.
  • isPrime[0] = false 및 isPrime[1] = false: 0과 1은 소수가 아니므로 false로 설정합니다.
  • Math.sqrt(n.toDouble()).toInt(): N의 제곱근까지 반복하여 소수 체크를 수행합니다.
  • for (j in i * i..n step i): 소수 i의 배수를 false로 설정하는 반복문입니다.
  • (2..n).filter { isPrime[it] }: 최종적으로 소수 리스트를 반환합니다.

알고리즘 분석

이 알고리즘의 시간 복잡도는 O(n log log n)입니다. 이는 소수를 찾는 문제에서 매우 효율적입니다. 공간 복잡도는 O(n)입니다. 이 알고리즘을 사용하면 10만 이하의 소수를 매우 빠르게 찾을 수 있습니다.

테스트 케이스

이제 알고리즘이 제대로 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 살펴보겠습니다.

테스트 케이스 1

  • 입력: 10
  • 출력: 2 3 5 7

테스트 케이스 2

  • 입력: 30
  • 출력: 2 3 5 7 11 13 17 19 23 29

테스트 케이스 3

  • 입력: 1
  • 출력: (출력 없음)

결론

이번 강좌에서는 소수를 구하는 방법으로 에라토스테네스의 체 알고리즘을 사용하였습니다. 이 알고리즘은 코딩테스트에서 자주 출제되는 문제이기 때문에 반드시 숙지해 두어야 합니다. 알고리즘의 각 단계를 차근차근 이해하고, 다양한 입력값에 대해 테스트하여 그 유효성을 검증하는 것이 중요합니다.

앞으로도 코틀린을 활용한 다양한 코딩 테스트 문제를 다룰 예정입니다. 계속해서 학습하시고, 각 알고리즘의 효율성과 동작 원리를 이해하는 데 집중하세요. 행복한 코딩 되세요!