[알고리즘] 소프티어 Lv2. 바이러스 (Python)

Softeer 알고리즘 문제 풀기

문제: Lv2. 바이러스

https://softeer.ai/practice/6284

 

시간초과 난 풀이

다음과 같이 ** 연산자를 이용해서 풀이했더니, 몇몇 테스트케이스들에서 시간초과가 떴다.

import sys
input = sys.stdin.readline

# 처음 바이러스의 수 K, 증가율 P, 총 시간 N(초)
K, P, N = map(int, input().split())

print(K*(P**N) % 1000000007)

📌 Point

P**N  # P를 N번 곱하는 연산 수행

• ** 연산자는 기본적으로 O(N) 의 시간이 걸린다.
• 만약 N이 매우 크면 (예: 10^9), 연산 시간이 엄청 오래 걸려서 시간 초과가 발생할 가능성이 높다.
• 게다가 거듭제곱 결과가 매우 커지면, 메모리 사용량도 커질 수 있다.

 

 

정답 풀이

내장된 pow 함수를 사용하니까 해결되었다.
그리고 변수들을 알아보기 쉽게 virus, rate, n으로 수정하였다.

import sys
input = sys.stdin.readline

# 처음 바이러스의 수 virus, 증가율 rate, 총 시간 n(초)
virus, rate, n = map(int, input().split())

print(virus * pow(rate, n, 1000000007) % 1000000007)

 

📌 Point

pow(rate, n, 1000000007)  # 모듈러 거듭제곱

• pow(base, exp, mod)는 O(log N) 시간 복잡도로 동작한다.
• 이는 빠른 거듭제곱 (Exponentiation by Squaring) 알고리즘을 사용해서 거듭제곱을 효율적으로 계산하기 때문이다.
• 이 방식은 거듭제곱을 반복적으로 반으로 줄여가면서 계산하기 때문에 훨씬 빠르다.

시간 복잡도 비교

x ** y	기본 거듭제곱	O(y) (최악의 경우)
pow(x, y)	x ** y 와 동일	O(y) (최악의 경우)
pow(x, y, mod)	모듈러 거듭제곱 (빠른 거듭제곱 알고리즘 사용)	O(log y)