코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기

복잡도

코딩테스트를 준비하기 전, 시간 복잡도와 공간복잡도 이해 해야한다.

대부분의 코딩테스트 문제에는 제한 시간과 메모리가 존재한다.

이를 바탕으로 적절한 시/공간 복잡도를 계산한 뒤 적절한 알고리즘을 사용할 필요성이 있다.

시간 복잡도

'제한시간'안에 알고리즘 문제를 해결하기 위해서는 시간복잡도를 이해해야 한다.

일반적으로 O(N)과 같은 빅오 표기법을 기준으로 연산 횟수를 계산한다.

for 문으로 문제를 해결할 시 시간복잡도는 다음과 같다.

1. 단일 for문: O(N)
2. 이중 for문: O(N²)
3. 삼중 for문: O(N³)

N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보자면

 

N = 500

• O(N³)일 경우 1.25 * 10⁸의 연산 횟수가 필요하다.
• O(N²)일 경우 2.5 * 10⁵의 연산 횟수가 필요하다.

C언어 기준 10억번 연산 시 1초 이상이 걸린다고 알려져 있다.

파이썬은 더 오래 걸릴 것이므로, 최악의 경우를 잘 고려해야 할 것 같다.

 

 

N = 1000

• O(N³)일 경우 10⁹의 연산 횟수가 필요하다.
• O(N²)일 경우 10⁶의 연산 횟수가 필요하다.

주어진 N의 값이 1000수준이라면 간단하게 O(N²) 알고리즘으로 해결이 가능하다.

 

 

N = 100,000

 

N=10만일 경우다. 이 때부터는 알고리즘을 신중히 선택할 필요가 있다.

• O(N²)일 경우 10¹⁰의 연산 횟수가 필요하다.
• O(NlogN)일 경우 약 $510^5log10 = 1.5 * 10^6$의 연산 횟수가 필요하다.

따라서 N이 10만개부터는 O(N²) 수준 알고리즘으로는 해결이 어렵다.일반적인 정렬 알고리즘의 시간 복잡도가 O(NlogN)이다.

 

 

N = 10,000,000

 

N=1000만일 경우다. 이 때부터는 O(NlogN)으로도 해결이 어렵다.

• O(NlogN)일 경우 약 $810^8log10 = 2.4 * 10^9$의 연산 횟수가 필요하다.
• O(N)일 경우 약 10⁸의 연산 횟수, 천만번 연산 횟수가 필요하다.
• O(logN)일 경우 약 8 * log¹⁰ = 26의 연산 횟수가 필요하다.

N이 천만 이상일 경우는 O(N)의 선형 시간 알고리즘을 혹은, O(logN)의 로그 시간 알고리즘을 사용해야 한다. 이진 탐색의 경우 O(logN) 복잡도를 가진다.

공간 복잡도

공간복잡도는 제한된 메모리 안에서 문제를 해결해야 한다는 것을 의미한다.

일반적인 int 형 자료형이 4Byte라는 것을 가정했을 때, 배열 기준 크기는 다음과 같다.

• int arr[1000] : 4byte * 1000 = 4kb
• int arr[1000000] : 4byte * 10⁶ = 4mb
• int arr[1000][1000] : 4byte * 10⁶ = 4mb
• int arr[2000][2000] : 4byte * 10⁶ * 4byte = 16 * 10⁶byte = 16mb

보통 100만개 이상의 배열을 선언하는 경우는 드물기 때문에 1000만개 이상의 배열을 선언했다면 알고리즘 설계를 제대로 하고 있는지 점검이 필요하다.

 

코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기 (tistory.com)