[TIL] 시간 복잡도와 알고리즘 문제 풀기

시간 복잡도니 공간 복잡도니 하는 이야기는 전공 공부할 때나 자격증 준비할 때나 아주 기초로 넘어가곤 했지만, 정작 알고리즘 문제를 풀 때는 어떻게 적용을 시키는게 좋을지 감이 잡히지 않았다. 그에 관한 내용에 대해 서술한다.

---

시간 복잡도란?

어떠한 알고리즘에서 걸리는 시간을 의미한다. 정확하게 시간으로 측정할 수 없기 때문에, 코드 한 줄 한 줄이 얼마나 수행되느냐를 세어 계산하곤 한다. 이 때 (입력의 크기 등에 의해서) 최악의 시간이 든다고 계산하여 빅오표기법으로 나타낸다.

 

예를 들어 보자.

# 1 <= N <= 1000
print(N) # O(1)

이 코드의 경우, 입력 N의 크기의 상관 없이 코드가 한 번만 수행된다. 따라서 O(1)로 표기한다.

 

# 1 <= N <= 1000
for i in range(N):
	print(i) # O(N)

이 코드의 경우, N의 크기에 따라 1번에서 1000번까지 수행된다. 따라서 O(N)으로 표기한다.

 

좀 더 실제 문제 같은 예를 들어보자.

- N명의 사람이 식당에서 주문을 하려고 한다.
- 메뉴판은 총 1개가 존재한다.
- 각 사람이 메뉴판을 읽고 주문을 하는 데에는 모두 동일하게 M 시간이 걸린다.
- 모든 음식은 동시에 나온다.
- 각 사람이 음식을 먹는 시간은 서로 상이하며, 각 A(i) 시간이 걸린다.
- 각 사람이 음식값을 계산하는데 걸리는 시간은 모두 동일하게 P 시간이 걸린다.

Q1. 모든 사람이 음식을 주문하는데 걸리는 시간은? : NM
Q2. 모든 사람이 식사를 마치는데 걸리는 시간은? : max(A)
Q3. 모든 사람이 음식값을 계산하는데 걸리는 시간은? : NP

Q1 에서, 메뉴판이 1개 밖에 없기 때문에, i 번째 사람은 i-1 번째 사람이 메뉴판을 읽을 때 까지 기다려야 한다. 따라서 NM 이다.

(나머지는 이하생략)

---

시간 복잡도의 계산

빅오 표기법에서의 시간 복잡도는 다음과 같이 계산한다.

1. 상수는 버린다. 
	O(3N) = O(N)
    O(6) = O(1)
2. 두 가지 항이 있을 때, 같은 변수면 큰 것만 남기고 버린다. 
	O(3N^2 + 6N) = O(N^2)
3. 두 가지 항이 있을 때, 다른 변수면 놔둔다. (N^2과 M 중 어느 것이 더 큰지 알 수 없기 때문이다.)
	O(N^2 + M)

---

1초가 걸리는 입력의 크기

일반적으로 코드가 1억 회 수행될 때, 1초가 걸린다고 판단한다. (실제 환경에 따라 상이함)

시간 복잡도	1초가 걸리는 입력N의 크기
O(1)
O(lgN)
O(N)	1억
O(N^2)	5백만
O(N^3)	500
O(2^N)	20
O(N!)	10