백준 10696 Prof. Ossama 문제 풀이
이 문제는 지인에게 추천받아 풀어보게 되었습니다. 문제가 요구하는 것은 생각보다 간단하지만, 채점에 사용되는 테스트 케이스가 상당히 흥미롭습니다.
문제 파악하기
문제는 단순히 입력으로 주어진 n, x 에 대해 n % x 처리를 하면 됩니다. 즉, 아래와 같이 구현할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
from sys import stdin
input = stdin.readline
def compute(n: int, x: int) -> int:
return n % x
if __name__ == '__main__':
for t in range(int(input())):
n, x = map(int, input().split())
print(f'Case {t + 1}: {compute(n, x)}')
문제 풀어보기
TimeOut! Overflow!
위 코드는 두 가지 문제가 있습니다.
우선 위 코드를 제출하면 시간 초과를 받는데, 그 이유는 입력의 비정상적인 크기에 있습니다. n % x 에서 n은 1백만 자리수까지, x는 1e7까지 처리되어야 합니다.
또 위와 같은 코드는 파이썬이 모든 크기의 정수를 하나의 타입으로 처리할 수 있게 구현되었기 때문에 처리 시간을 제외하고는 문제가 없는 것처럼 보입니다. 하지만 다른 언어들은 저렇게 큰 수를 같은 방식으로 처리할 수 없습니다. unsigned long long 자료형도 최대 20자리(18,446,744,073,709,551,615) 수까지밖에 표현하지 못하므로 다른 대책이 필요합니다.
나머지 연산의 분배 법칙
사칙 연산들이 다 그렇듯, 나머지 연산도 분배 법칙이 성립하므로 수를 분할해서 연산할 수 있습니다.
1
(a + b) % m = ((a % m) + (b % m)) % m
이 특성은 큰 수를 통째로 처리하는 대신 큰 수를 구성하는 작은 수 여러개를 조금씩 처리하는 것도 유효한 값을 낼 수 있게 해줍니다.
1
2
3
4
5
6
7
8
9
n: str
x: str
remainder: int = 0
div = int(x)
for each in n:
remainder = (remainder * 10 + int(each)) % div
remainder
왜 통과하지?
위 코드를 제출해보면 제 시간에 답안이 통과하는 것을 확인할 수 있습니다. 조금 이상한 것 같으면서 납득되는 것 같기도 합니다.
큰 수를 통째로 나머지 연산했을때는 큰 수를 처리하니 시간이 오래걸렸다고 하더라도 이상할 게 없습니다. 하지만, 최소한 위 구현에서, 큰 수를 분할해서 나머지 연산한 코드는 수의 자릿수만큼 나머지 연산을 수행해야 합니다. str → int 형변환까지 고려하면 나머지 연산과 형변환을 1백만회 처리해야합니다. 큰 수 연산의 처리 시간이 오래 걸렸다면, 백만회 연산도 오래 걸려야 할 것만 같습니다.
(파이썬) 두 방식의 처리 시간
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import cProfile
from random import choice
def generate_random_integer(ln: int) -> str:
buf: list[str] = []
num_str = list('1234567890')
for i in range(ln):
buf.append(choice(num_str))
return ''.join(buf)
def compute(n: str, x: str) -> int:
def calc_int(n: str, x: str) -> int:
return int(n) % int(x)
def calc_str(n: str, x: str) -> int:
remainder: int = 0
div = int(x)
for each in n:
remainder = (remainder * 10 + int(each)) % div
return remainder
calc_int(n, x)
calc_str(n, x)
if __name__ == '__main__':
n = generate_random_integer(1000000)
x = generate_random_integer(7)
cProfile.run('compute(n, x)')
1
2
3
4
5
6
7
8
9
10
11
6 function calls in 5.065 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 5.065 5.065 <string>:1(<module>)
1 0.000 0.000 5.065 5.065 app.py:11(compute)
1 4.811 4.811 4.811 4.811 app.py:12(calc_int)
1 0.253 0.253 0.253 0.253 app.py:14(calc_str)
1 0.000 0.000 5.065 5.065 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
calc_int는 큰 수를 통째로 처리하는 함수, calc_str은 큰 수를 분할해서 처리하는 함수입니다. calc_int는 4.811, 5초에 가까운 실행 시간이 소요됐지만, calc_str은 0.2초만에 처리가 완료됩니다.
이번엔 조금 더 구체적으로, 프로파일러가 calc_int의 처리 과정을 전부 추적할 수 있도록 몇 개의 코드에 함수 래퍼(wrapper)를 추가하고 실행 시간을 측정했습니다.
1
2
3
4
5
6
7
8
9
10
11
12
8 function calls in 5.245 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 5.245 5.245 <string>:1(<module>)
1 0.000 0.000 5.245 5.245 app.py:11(compute)
1 0.001 0.001 4.980 4.980 app.py:12(calc_int)
2 4.978 2.489 4.978 2.489 app.py:13(conversion)
1 0.266 0.266 0.266 0.266 app.py:16(calc_str)
1 0.000 0.000 5.245 5.245 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
calc_int에서 가장 오랜 처리 시간을 차지하는 것은 conversion 이었습니다. 약 2.5초가 2회 소요되었습니다. conversion은 calc_int에서 문자열형 큰 수를 정수형 큰 수로 변환해주는 함수입니다. (conversion = lambda x: int(x)) 다시 말해, 시간 초과는 큰 수의 연산이 아니라 정수형 값을 생성하면서 발생한 것입니다.