목차
개요
복잡도는 알고리즘의 성능을 나타내는 척도이다. 필자도 아직 걸음마 떼고 있는 실정이라 이게 뭐 대수인가 싶었다. 역시 사람은 문제가 닥치기 전까지는 무지한 법이다...
1. 시간 복잡도 (Time Complexity)
시간 복잡도란 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다.
보통 코딩 테스트에는 시간 제한이 있으며 (출제자가 문제를 해결하라고 준 시간 제한이 아닌 프로그램 출력까지 걸리는 시간**) 문제에서 만점을 받기 위해서는 해당 시간안에 동작하는 프로그램을 작성해야 한다. 프로그램을 비효율적으로 작성하면 '시간 초과'로 도배된 창을 만날 수 있다.
2. 빅오 표기법(Big - O)
알고리즘을 작성하고 실행할 때 보통 실행하는 단계의 수를 직접 세거나 결정하는 일은 흔치 않다. 이를 간단히 정리하기 위한 방법이 바로 빅오 표기법이다. 입력되는 다수의 데이터에서 제일 빠르게 상한하는 값만 고려해서 나타내어 이해하기 쉽게 나타낸다. 우리가 과거에 배웠던 극한의 계산에 대해 생각해보면 쉽게 이해할 수 있다.
다음의 식에서
제일 큰 차수의 항만 고려해서 계산을 하기 때문에 답은 위와 같이 나왔다는 걸 알 수 있다. (물론 세세하게 파고 들어가면 극한과 빅오표기법은 정확하게 같지는 않다. 이 글에서는 설명을 위해서 극한에 대한 설명을 사용했다.)
만약에 단계가 7N + 1 인 프로그램을 작성한다고 하면 프로그램을 실행할 때 N = 100,000 과 같다면 총 단계의 수는 7 X 100,000 + 1 이 된다. 이러한 결과에서 마지막 + 1 제외하고 생각한다고 해서 총 단계 수에 중대한 영향을 미치지 않는다.
따라서 이를 빅오표기법으로 나타내면 O(7N)이 된다.
예제 1. 연산 횟수가 \( N \)에 비례할 때
array = [3, 5, 1, 2, 4]
summary = 0
for x in array:
summary += x
print(summary)이를 빅오 표기법으로 나타내면 O(N)이 된다. 물론 코드에서는 단순히 더하는 연산이외의 출력부분 도 있지만 이는 N이 커지면 커질 수록 무시할 수 있을 만큼 작아질 것이다.
예제 2. 연산 횟수가 \( N^{2} \)에 비례할 때
array = [3, 5, 1, 2, 4]
summary = 0
for i in array:
for j in array:
temp = i * j
print(temp)이를 빅오 표기법으로 나타내면 O(\( N^{2} )\)이 된다. 물론 모든 이중 반복문의 시간 복잡도가 O(\( N^{2} )\)가 되는 것은 아니다.
다음은 자주 사용되는 시간 복잡도 표인데 위에 있을수록 실행 시간이 빠르다.
| 빅오 표기법 | 명칭 |
| \( O(1)\) | 상수 시간(Constant time) |
| \( O(logN)\) | 로그 시간(Log time) |
| \( O(N)\) | 선형 시간 |
| \( O(NlogN)\) | 로그 선형 시간 |
| \( O(N^{2})\) | 이차 시간 |
| \( O(N^{3})\) | 삼차 시간 |
| \( O(2^{n})\) | 지수 시간 |
일반적으로 코딩 테스트 환경에서는 \ O(N^{3}) \ 을 넘어가면 문제 풀이에서 사용하기 어렵다. 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 넘어가면 C 언어를 기준으로 통상 1초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 10초 이상의 시간이 걸릴 수 있다. 특히 연산 시간이 더욱 느린 파이썬에서는 더 오래걸리며, 보통 코딩테스트 문제에서 시간 제한이 1 ~ 5초 가량인것을 감안하면 연산 횟수가 많아질 수록 오답 판정을 받을 확률이 높다.
다음은 각기 다른 시간 복잡도에서 연산횟수가 N의 크기에 따라서 어떻게 분포되는지 나타낸다.
| N이 1,000일 때의 연산 횟수 | |
| \( O(N)\) | 1,000 |
| \( O(NlogN)\) | 10,000 |
| \( O(N^{3})\) | 1,000,000 |
| \( O(N^{3})\) | 1,000,000,000 |
문제의 시간 제한에 따라서 다른 시간 복잡도를 선택하여 프로그램을 작성한다면 시간 복잡도를 줄일 수 있다.
3. 예시
백준 1931 : 회의실 배정
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 \( 2 ^{31} -1\)보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
아이디어
이 문제에 대한 해답을 생각해내는 건 그리 어렵지 않다. 회의가 끝나는 시간을 기준으로 하고 정렬하여 첫 번째 회의 이후 가능한 회의의 수를 리스트에 넣어 정리하거나 filter()를 통해 정리하면 될거라고 생각하였다.
N = int(input())
time_table = []
for i in range(N):
a, b = map(int, input().split())
time_table.append([a, b])
time_table.sort(key = lambda x : x[1])
start_meeting = time_table[0][1]
cnt = 1
for _ in range(N):
a = list(filter(lambda x : x[0] >= start_meeting, time_table))
start_meeting = a[0][1]
cnt += 1
if len(a) == 1:
break
print(cnt)위의 제출 이전 시도에서는 for 문 대신 while 문을 사용하였는데 보통 while 문의 시간이 더 오래 걸리므로 for 문으로 대체하였다. 위 제출은 시간 초과로 인한 오답이었다. 따라서 time 라이브러리를 이용해 시간을 재어 보았는데 결과는 다음과 같았다.
이후에 질문을 검색해보니 시간초과로 인한 오답이 매우 많았고, 결국 회의 시작 시간과 끝나는 시간 모두를 한 for 문에 넣어서 시간을 줄여서 해결하였다.
N = int(input())
time_table = []
for i in range(N):
a, b = map(int, input().split())
time_table.append([a, b])
time_table = sorted(time_table, key = lambda x : x[0])
time_table = sorted(time_table, key = lambda x : x[1])
last = 0
cnt = 0
for i, j in time_table:
if i >= last:
cnt += 1
last = j
print(cnt)
이처럼 코딩 테스트에서 시간 복잡도를 고려하지 않고 프로그램을 작성하면 답은 맞았음에도 불구하고 시간초과로 인해 오답 판정을 받을 수 있음을 유의하자..
다음부터는 이러지 말자,,하하
출처
나동빈, [이것이 코딩테스트다 with 파이썬], 한빛미디어, 46 - 53 쪽