[백준 1016] 제곱 ㄴㄴ 수

백준 1016번: 제곱 ㄴㄴ 수 - 상세 풀이

🔍 1. 문제 소개

백준 1016번 문제 "제곱 ㄴㄴ 수"는 주어진 범위 [`min`, `max`] 내에서 제곱ㄴㄴ수의 개수를 찾는 문제입니다. 제곱ㄴㄴ수는 1보다 큰 제곱수로 나누어떨어지지 않는 정수를 의미합니다. 예를 들어, 1보다 큰 제곱수는 4, 9, 16, 25, ... 등이며, 이러한 수들로 나누어떨어지지 않는 수가 제곱ㄴㄴ수입니다. 문제에서는 최솟값 min과 최댓값 max가 주어지며, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력해야 합니다.

💡 2. 문제 해석

문제의 핵심은 주어진 범위 내의 모든 수를 검사하여 제곱ㄴㄴ수인지 판별하는 것입니다. 단순히 모든 수를 일일이 검사하는 방법은 시간 복잡도가 매우 높아 효율적이지 않습니다. 따라서, 효율적인 알고리즘을 사용하여 문제를 해결해야 합니다. 문제의 제약 조건은 min과 max의 값이 매우 클 수 있다는 점입니다. 따라서, 시간 복잡도를 최소화하는 알고리즘 설계가 중요합니다.

🧠 3. 접근 방법

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 응용하여 해결할 수 있습니다. 에라토스테네스의 체는 소수를 찾는 알고리즘이지만, 이 문제에서는 제곱수의 배수를 제거하는 방식으로 응용됩니다.

1. **범위 설정:** `min`부터 `max`까지의 범위를 설정합니다.

2. 제곱수 생성: $\sqrt{max}$까지의 모든 정수를 제곱하여 제곱수들을 생성합니다. 3. 체 생성: `min`부터 `max`까지의 범위를 나타내는 `Boolean` 배열을 생성합니다. 처음에는 모든 원소를 `true`로 초기화합니다. `true`는 제곱ㄴㄴ수 후보, `false`는 제곱ㄴㄴ수가 아님을 나타냅니다. 4. 제곱수 배수 제거: 각 제곱수에 대해, 그 배수들을 `Boolean` 배열에서 `false`로 설정합니다. 즉, 제곱수의 배수들은 제곱ㄴㄴ수가 아니므로 제거합니다. 5. 개수 계산: 최종적으로 `Boolean` 배열에서 `true`인 원소의 개수를 계산하여 출력합니다.

⚙️ 4. 구현 과정

1. 입력으로 `min`과 `max`를 받습니다. `Long` 타입으로 입력받지만, `max - min`이 `Int` 범위를 벗어나는 경우 예외 처리를 합니다.

2. `min`부터 `max`까지의 범위를 나타내는 `BooleanArray` `sieve`를 생성하고 `true`로 초기화합니다. 3. 2부터 $\sqrt{max}$까지의 정수 `i`를 순회하며, 각 `i`의 제곱수인 `square`의 배수들을 `min`부터 `max` 사이에서 찾아 `sieve`에서 `false`로 표시합니다. 배수를 찾을 때는 `min`을 `square`로 나눈 몫의 다음 정수부터 시작하여 `square`씩 증가시키면서 효율적으로 찾을 수 있습니다. 4. `sieve` 배열에서 `true`인 원소의 개수를 세어 결과를 출력합니다.

💻 5. 코드 설명

import kotlin.math.sqrt
import kotlin.math.ceil

fun main() {
    val (min, max) = readLine()!!.split(" ").map { it.toLong() }

    val range = (max - min + 1).toInt()
    val isDivisibleBySquare = BooleanArray(range) { false }
    val limit = sqrt(max.toDouble()).toLong()

    for (i in 2..limit) {
        val square = i * i
        var first = ceil(min.toDouble() / square).toLong() * square
        if (first < min) {
            first += square
        }
        for (multiple in first..max step square) {
            val index = (multiple - min).toInt()
            if (index in 0 until range) {
                isDivisibleBySquare[index] = true
            }
        }
    }

    val count = range - isDivisibleBySquare.count { !it }
    println(count)
}

* readLine()!!.split(" ").map { it.toLong() }: 입력을 받아 Long 타입의 min과 max 변수에 저장합니다. * val range = (max - min + 1).toInt(): min부터 max까지의 범위 크기를 계산합니다. * val isDivisibleBySquare = BooleanArray(range) { false }: 해당 범위의 각 숫자가 제곱수로 나누어지는지 여부를 저장하는 BooleanArray를 생성하고 초기화합니다. `false`는 아직 제곱수로 나누어지지 않는다고 가정합니다. * val limit = sqrt(max.toDouble()).toLong(): $\sqrt{max}$ 값을 계산하여 제곱수를 생성할 상한값을 정합니다. `toDouble()`을 사용하여 정확도를 높입니다. * for (i in 2..limit) 루프: 2부터 limit까지의 정수를 순회하며 제곱수를 생성합니다. * val square = i * i: 현재 정수 i의 제곱수를 계산합니다. * var first = ceil(min.toDouble() / square).toLong() * square: 범위 [`min`, `max`] 내에서 `square`의 첫 번째 배수를 찾습니다. * if (first < min) { first += square }: 만약 계산된 첫 번째 배수가 `min`보다 작다면, `square`를 한 번 더 더하여 범위 내의 첫 번째 배수를 정확히 찾습니다. * for (multiple in first..max step square) 루프: `first`부터 `max`까지 `square`씩 증가시키면서 `square`의 모든 배수를 순회합니다. * val index = (multiple - min).toInt(): 현재 배수 `multiple`이 범위 내에서 몇 번째 숫자인지를 나타내는 인덱스를 계산합니다. * if (index in 0 until range) { isDivisibleBySquare[index] = true }: 해당 인덱스의 값을 `true`로 설정하여 `min + index`가 제곱수 `square`로 나누어짐을 표시합니다. * val count = range - isDivisibleBySquare.count { !it }: `isDivisibleBySquare` 배열에서 `false` 값의 개수를 세어 제곱ㄴㄴ수의 개수를 계산합니다.

⏱️ 6. 시간 복잡도와 공간 복잡도 분석

* 시간 복잡도: 바깥쪽 루프는 O(√max)번 반복됩니다. 안쪽 루프는 각 제곱수 `square`에 대해 대략 O((max - min) / square)번 반복됩니다. 전체 시간 복잡도는 대략 O((max - min) * √max / (min의 최소 제곱근)) 정도로 분석될 수 있습니다. 주어진 제약 조건 (max - min ≤ 1,000,000) 하에서 효율적인 시간 복잡도를 가집니다. * 공간 복잡도: `isDivisibleBySquare` 배열의 크기가 `max - min + 1`이므로, O(max - min)의 공간이 필요합니다.

🎯 7. 결론

이 문제는 에라토스테네스의 체 알고리즘을 응용하여 주어진 범위 내의 제곱ㄴㄴ수를 효율적으로 찾을 수 있습니다. $\sqrt{max}$까지의 제곱수들을 이용하여 해당 범위 내의 배수들을 제거하는 방식으로 문제를 해결함으로써, 모든 수를 일일이 소인수분해하는 비효율적인 방법을 피할 수 있습니다. 주어진 제약 조건 내에서 제시된 코드는 충분히 빠르고 효율적으로 동작합니다.