[백준] 시간 복잡도(시간제한)

백준 문제를 본격적으로 풀기 전에, 모든 코테 문제들은 시간 제한이 있다. (보통 일반적으로 1 ~ 5초의 시간제한이 주어진다.)

파이썬의 경우 약 2,000만 ~ 1억 번의 연산 횟수를 진행할 수 있다고 한다.

따라서 파이썬의 경우 1초에 1,000만번 또는 2,000만번 정도로 고려해서 시간 복잡도를 생각하면된다.

예를 들어 제한 시간이 1초인 문제는 연산 횟수가 2,000만 또는 3,000만이 넘는 알고리즘은 사용하면 안되는 것이다.

1,000만 차이가 너무 큰거 아닌가? 라고 생각할 수 있지만 컴퓨터 환경에서 문제를 푸는 연산 속도는 컴퓨터의 H/W 성능에 따라 차이가 나고 일률적으로 적용하기 힘들기 때문에 어림짐작으로 잡아도 상관없다.
(실제로 A 교재는 1,000만, B 교재는 2,000만, C 교재는 3,000만 등 조금씩 설명하는게 다르다...)

아래는 시간 복잡도를 토대로 제한 시간이 1초를 기준으로 가능한 최대 연산 횟수 (최대 입력 크기)이다.

시간 복잡도	최대 연산 횟수 (최대 입력 크기)
$O(N!)$	약 10번
$O(2^N)$	약 20 ~ 25번
$O(N^3)$	약 200 ~ 300번
$O(N^2)$	약 3,000 ~ 5,000번
$O(NlogN)$	약 100만번
$O(N)$	약 1,000만 ~ 2,000만번
$O(logN)$	약 10억번

예를 들어 아래와 같이 배열을 하나씩 탐색하는 알고리즘의 시간복잡도는 $O(N)$이다.

1	5	3	2	6	17

$O(N)$이 허용하는 연산 횟수는 2,000만으로 생각하면 데이터 개수가 최대 2,000만 개 이하이어야 해당 알고리즘을 사용할 수 있다.

이를 그대로 적용해서 아래와 같은 코테 문제가 있다고 생각해보자.

---

문제 (시간 제한 1초)

N개의 수 A1, A2, A3, ... An이 주어졌을 때... blablabla

---

입력

1번째 줄에 N과 M($1 ≤ N ≤ 10^5, 2 ≤ M ≤ 10^3$)... blablabla

---

이런 문제가 있다면 시간 제한이 1초이고 데이터 크기인 N의 최댓값이 100,000 개 (10만 개)이다.

따라서 $O(N^2)$은 사용할 수 없으며, $O(NlogN), O(N), O(logN)$의 알고리즘만 사용이 가능하다는 말이 된다.

☃️ 그럴리는 없지만 이해를 돕기 위해 제한 시간이 34초 이상이라면 $3,000 × 34 = 102,000 ≥ 100,000$이므로 $O(N^2)$ 알고리즘도 사용이 가능할 것이다.

그 이후에 문제에서 요구하는 정답이 어떤 것이냐에 따라 시간 복잡도를 충족하는 알고리즘을 한정지어 생각해볼 수 있다.

아래는 코딩테스트에 주로 등장하는 N의 범위에 따른 시간복잡도 선택이니, 참고하면 좋을 것 같다.

N의 범위	시간 복잡도
500	$O(N^3)$ 이하인 알고리즘 사용
2,000	$O(N^2)$ 이하인 알고리즘 사용
100,000	$O(NlogN)$ 이하인 알고리즘 사용
10,000,000	$O(N)$ 이하인 알고리즘 사용
1,000,000,000	$O(logN)$ 이하인 알고리즘 사용