[소프티어 Softeer] 바이러스 (Lv.2) - 파이썬(Python)

문제

https://softeer.ai/practice/6284

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

문제 풀이

오답 코드

import sys

input = sys.stdin.readline

k, p, n = map(int, input().split())

answer = k

for i in range(n):
    answer = answer * p 
print(answer % 1000000007)

 

첫 코드는 문제에서 명시한 것처럼 최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하였더니 시간초과가 발생합니다.

제약 조건상 N초의 최대가 10^6이었고 나의 알고리즘 시간복잡도는 O(n)이었기 때문에 왜 시간초과가 뜨는지 이해가 되지 않아 찾아보았습니다.

 

시간 초과가 발생하는 이유

오버플로우 발생

* 오버플로우: 변수나 메모리 공간에 저장할 수 있는 값의 범위를 초과하는 경우

정수형 변수는 일반적으로 고정된 비트 수를 사용하여 값을 저장합니다.

예를 들어, 32비트 정수형 변수는 -2,147,483,648부터 2,147,483,647까지의 값을 저장할 수 있습니다. 만약 이 범위를 초과하는 값을 저장하려고 하면 오버플로우가 발생합니다.

 

위 오답 코드는 K의 최대값이 10^8이고 P의 최대값이 10^8이기 때문에  반복문이 100만번 수행되면서 answer의 값은 기하급수적으로 커져 오버플로우가 발생합니다.

 

최종 정답 코드

모듈러 연산의 성질 덕분에 오답 코드와 정답 코드의 최종 결과는 동일합니다.

정답 코드는 각 단계마다 모듈러 연산을 수행하여 answer의 크기를 작게 유지하므로 메모리와 시간 효율성이 더 높습니다.

import sys

input = sys.stdin.readline

k, p, n = map(int, input().split())

answer = k

for i in range(n):
    answer = (answer * p) % 1000000007

print(answer)

 

오답 코드와 정답 코드의 결과가 같은 이유

모듈러 연산의 특성 때문에, 첫 번째 코드와 두 번째 코드의 결과는 동일합니다.
이는 모듈러 연산의 기본 성질에 의한 것입니다. 이 성질을 통해 반복적으로 모듈러 연산을 해도 최종 결과는 동일하게 유지됩니다.

이는 수학적인 공부가 필요하기 때문에 구글링 등을 통해서 모듈러 연산을 찾아보시기 바랍니다.

 

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

모듈로 연산이란? (개념 이해하기) | 암호학이란? | Khan Academy