< 과제 >
[ 문제 ]
유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다.채점 시스템은 1초에 100000000()가지 동작을 할 수 있다.
여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라.
[ 입력 ]
입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다.그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의 수를 나타내는 T랑 제한시간(초 단위) 를 나타내는 L이 주어진다. (1 <= C <= 100, 1 <= N <= 1000000, 1 <= T, L <= 10, N, T, L은 정수)
시간 복잡도는 다음과 같은 5개 중 하나로 주어진다.
- O (N)
- O (N^2)
- O (N^3)
- O (2^N)
- O (N!)
[ 출력 ]
각 테스트 케이스들에 대하여 시간 초과가 나면 "TLE!", 시간 초과가 나지 않으면 "May Pass." 를 출력한다.[ 예제 입력 1 ]
5
O(N) 1000 10 10
O(2^N) 1000 10 10
O(N!) 2 10 10
O(N^3) 1000 1 10
O(N^3) 1001 1 10[ 예제 출력 1 ]
May Pass.
TLE!
May Pass.
May Pass.
TLE!
< 내 코드 >
import math
C = int(input())
for _ in range(C):
temp = input().split()
S = temp[0]
N, T, L = map(int, temp[1:])
limit = (10 ** 8) * L
if S == "O(N)":
if N * T <= limit:
print("May Pass.")
else:
print("TLE!")
if S == "O(N^2)":
if ((N ** 2) * T) <= limit:
print("May Pass.")
else:
print("TLE!")
if S == "O(N^3)":
if ((N ** 3) * T) <= limit:
print("May Pass.")
else:
print("TLE!")
if S == "O(2^N)":
if ((2 ** N) * T) <= limit:
print("May Pass.")
else:
print("TLE!")
if S == "O(N!)":
if (math.factorial(N) * T) <= limit:
print("May Pass.")
else:
print("TLE!")- 입력 받는 S의 종류 중 팩토리얼 계산도 있기 때문에 math 모듈을 import 한다.
- 시간 복잡도는 O(N), θ(N), Ω(N)가 있으며 각각 최악의 복잡도, 평균 복잡도, 최선의 복잡도이다. 일반적으로 시간 복잡도를 나타낼 때에는 테스트별 최악의 복잡도를 기준으로 삼는다.
- 시간 복잡도는 (최대 테스트 길이 * 테스트 케이스 개수)로 계산하며, 각각의 시간 복잡도에 대하여 계산하는 방법은 아래와 같다.(문제에서 테스트 케이스 개수는 T로 놓음)
- O (N) =
- O (N^2) =
- O (N^3) =
- O (2^N) =
- O (N!) =
- 제한시간은 L(초)로 받으며, 1초에 번 동작할 수 있다고 한다. 따라서 각 시간 복잡도는 보다 작아야 한다.
< 피드백 >
- 시간 복잡도에 대한 개념을 깊이 있게 다룬적은 없었는데, 시간 복잡도에 대해 공부할 수 있는 좋은 기회였다.
- 그런데, 이론을 아는 것과 그것을 구현하는 것은 분명한 차이가 있음을 느꼈다. 아는 것도 중요하지만, 구현하지 못하면 의미가 없다. 알고리즘 공부를 열심히 해야겠다.
< 출처 >
