코딩테스트를 풀다보면 이런 시간제한을 마주하게 되고 가끔은 시간초과 마주하게 되고 가끔은 시간초과 RunTimeError가 나기도 한다.
따라서 시간제한을 통과할 수 있는 알고리즘을 선택하여 문제를 푸는 것이 중요함.
시간복잡도
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
알고리즘에서 시간복잡도란 처리하는 입력크기와 실행시간 간의 상관관계를 나타낸다. 다시말해 문제를 해결하기 위한 연산 횟수를 의미하는 것.
문제에서 주어진 데이터 크기를 통해 시간복잡도를 미리 계산해볼 수 있다.
보통 코딩테스트에서는 1초에 1억(10⁸)번 의 연산이 가능하다고 보고 계산한다. 만약 시간제한이 2초라면 2억번의 연산이 맥시멈이라는 뜻.
시간제한이 1초인 경우 입력 갯수에 따라 허용되는 시간복잡도는 아래와 같다. (참고만 할 것)
시간복잡도를 표기하는 유형에는 빅오, 빅오메가, 빅세타와 같은 표기법이 있는데 그 중 빅오(O) 표기법을 사용하여 알고리즘의 실행 시간을 계산한다.
빅오 표기법
어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 (영향력이 가장 큰 항만 남기는 것) 차수를 지워 O(...)와 같이 표기하면 된다. 예를 들어 어떤 프로그램의 연산 횟수가 f(x) = 2x² + 3x + 5라면 시간 복잡도를 O(x²)로 표기하면 되는 것이다.
시간복잡도 계산하기
많이 사용되는 시간복잡도
O(1), O(log n), O(n), O(n log n), O(n²)
- O(1)
- 입력값의 크기에 상관없이 일정한 실행시간을 가짐. 가장 빠른 시간 복잡도.
- 배열에서 특정 인덱스에 접근하는 경우이다.
- O(log n)
- 입력값이 2배씩 증가할 때마다 실행시간이 1배씩 증가한다.
- 이진탐색과 같은 알고리즘의 경우
- O(n)
- 입력값의 크기에 비례하여 실행 시간이 증가
- 배열의 모든 요소를 순회하며 처리하는 경우
- O(n log n)
- 입력값이 커질수록 실행시간이 증가하지만 O(n²)보다는 빠름
- 대부분의 퀵 정렬과 병합 정렬과 같은 정렬 알고리즘의 경우
- O(n²)
- 입력값의 제곱에 비례하여 실행시간이 증가
- 이중 반복문을 사용하는 경우
코딩테스트에서는 보통 시간제한이 1초인 경우가 많기때문에
1억번의 실행횟수를 1초로 계산하는 것이 유용하다.
예시
-
예시 1
입력의 크기(문제에서 주어지는 입력 조건의 최대 범위)가 10,000일때
O(n²)인 알고리즘은 1초 내에 처리할 수 없음 -> 10,000² = 100,000,000
O(n log n)이나O(n)알고리즘은 1초 내에 처리할 수 있음. -
예시2
우선 주어진 데이터의 갯수를 확인한다. 위의 사진에서10^6이라는 숫자를 보고 이에 알맞은 알고리즘을 사용해야 한다.
시간 제한이 1초일 때
O(n²)는 10⁶ × 10⁶ = 10¹² -> ❌ 절대 불가능
O(n log n)또는O(n)까지만 가능
코테에 자주 나오는 알고리즘 시간복잡도
-
정렬 알고리즘
-
탐색 알고리즘
-
그래프 알고리즘
-
그리디 & 투 포인터 & 슬라이딩 윈도우
-
정수 및 수학
-
기타 자주 등장하는 자료구조
로그 계산 참고
log₂(1,000) ≈ 10
log₂(10,000) ≈ 13.3
log₂(100,000) ≈ 16.6
log₂(1,000,000) ≈ 19.9
