[백준 1009] 분산처리

백준 1009번: 분산처리 - 상세 풀이

🔍 1. 문제 소개

백준 1009번 문제 "분산처리"는 10대의 컴퓨터가 순차적으로 데이터를 처리하는 상황을 가정합니다. 1번 컴퓨터는 1번, 11번, 21번... 데이터를 처리하고, 2번 컴퓨터는 2번, 12번, 22번... 데이터를 처리하는 식입니다. 총 데이터 개수는 a^b개이며, 마지막 데이터를 처리하는 컴퓨터의 번호를 출력하는 것이 문제의 목표입니다.

💡 2. 문제 해석

문제의 핵심은 a^b를 10으로 나눈 나머지를 구하는 것입니다. 나머지가 0이면 10번 컴퓨터, 나머지가 k이면 k번 컴퓨터가 마지막 데이터를 처리합니다. a와 b의 범위는 1 ≤ a < 100, 1 ≤ b < 1,000,000 이므로, a^b는 매우 큰 값이 될 수 있어 일반적인 정수 자료형으로는 처리하기 어렵습니다. 따라서 효율적인 계산 방법이 필요합니다.

🧠 3. 접근 방법

문제에서 중요한 점은 마지막 데이터를 처리하는 컴퓨터의 번호는 a^b 의 일의 자리 숫자에만 의존한다는 것입니다. 따라서 a^b를 직접 계산할 필요 없이, (a^b) mod 10 을 계산하면 됩니다. 이는 모듈러 거듭제곱 (Modular Exponentiation) 알고리즘을 사용하여 효율적으로 계산할 수 있습니다. 모듈러 거듭제곱 알고리즘은 반복 제곱을 이용하여 시간 복잡도를 O(log b)로 줄여줍니다.

⚙️ 4. 구현 과정

1. 입력으로 테스트 케이스의 개수 T를 받습니다.

2. 각 테스트 케이스마다 a와 b를 입력받습니다. 3. a의 일의 자리 숫자를 구합니다 (a % 10). a가 0이면 결과는 10입니다. 4. 모듈러 거듭제곱 함수를 사용하여 (a^b) mod 10을 계산합니다. 5. 결과를 출력합니다.

💻 5. 코드 설명

fun main() {
    val t = readLine()!!.toInt()
    for (i in 0 until t) {
        val (a, b) = readLine()!!.split(" ").map { it.toLong() }
        val lastDigitA = a % 10
        var result = if (lastDigitA == 0L) 10L else lastDigitA
        if (b > 0) {
            result = power(result, b)
        }
        println(result)
    }
}

fun power(base: Long, exp: Long): Long {
    if (exp == 0L) return 1L
    if (exp == 1L) return base % 10L
    val halfPower = power(base, exp / 2)
    val square = (halfPower * halfPower) % 10L
    return if (exp % 2 == 0L) square else (square * (base % 10L)) % 10L
}

* main 함수는 입력을 받고, power 함수를 호출하여 결과를 계산합니다. a가 0인 경우를 처리하여 10을 출력하도록 합니다. * power 함수는 모듈러 거듭제곱을 재귀적으로 구현합니다. exp가 0이면 1, 1이면 base % 10을 반환합니다. 그 외의 경우에는 분할 정복 방식으로 계산합니다. 모든 연산은 % 10L을 통해 나머지를 계산하여 값이 너무 커지는 것을 방지합니다.

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

* 시간 복잡도: power 함수는 모듈러 거듭제곱을 사용하므로 시간 복잡도는 O(log b)입니다. main 함수의 반복문은 T번 실행되므로 전체 시간 복잡도는 O(T log b)입니다.

* 공간 복잡도: 재귀 호출 깊이가 최대 log b이므로, 공간 복잡도는 O(log b)입니다. 하지만 실제 사용되는 메모리는 상수 크기이므로, 공간 복잡도는 사실상 O(1)에 가깝습니다.

🎯 7. 결론

이 문제는 큰 수를 다루는 문제이지만, 모듈러 거듭제곱 알고리즘을 통해 효율적으로 해결할 수 있음을 보여줍니다. BigInteger를 사용하지 않고 Long 자료형과 모듈러 연산만으로도 충분히 문제를 해결할 수 있으며, 이를 통해 시간 및 공간 효율성을 크게 높였습니다. 이 문제를 통해 큰 수 연산에서 효율적인 알고리즘의 중요성을 다시 한번 확인할 수 있었습니다. 추가 개선으로는 반복문을 이용한 모듈러 거듭제곱 구현을 통해 재귀 호출에 따른 오버헤드를 줄일 수 있을 것입니다.