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

🔸복잡도

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

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

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

따라서 시간 복잡도와 공간복잡도에 대해 이번 기회에 정리하려고 합니다.

🔸시간복잡도

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

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

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

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

N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보겠습니다.

N=500

N=500일 경우

1. $O(N^3)$일 경우 $1.25 * 10^8$의 연산 횟수가 필요합니다.
2. $O(N^2)$일 경우 $2.5 * 10^5$의 연산 횟수가 필요합니다.

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

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

N=1000

1. $O(N^3)$일 경우 $10^9$의 연산 횟수가 필요합니다.
2. $O(N^2)$일 경우 $10^6$의 연산 횟수가 필요합니다.

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

N=100,000

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

1. $O(N^2)$일 경우 $10^{10}$의 연산 횟수가 필요합니다.
2. $O(NlogN)$일 경우 약 $510^5log10 = 1.5 * 10^6$의 연산 횟수가 필요합니다.

따라서 N이 10만개부터는 $O(N^2)$ 수준 알고리즘으로는 해결이 어렵습니다.

일반적인 정렬 알고리즘의 시간 복잡도가 $O(NlogN)$입니다.

N=10,000,000

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

1. $O(NlogN)$일 경우 약 $810^8log10 = 2.4 * 10^9$의 연산 횟수가 필요합니다.
2. $O(N)$일 경우 약 $10^8$의 연산 횟수, 천만번 연산 횟수가 필요합니다.
3. $O(logN)$일 경우 약 $8 * log10 = 26$의 연산 횟수가 필요합니다.

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

🔸공간복잡도

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

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

1. int arr[1000]: $4byte * 1000=4KB$
2. int arr[1000000]: $4byte*10^6=4MB$
3. int arr[1000][1000]: $4byte*10^6=4MB$
4. int arr[2000][2000]: $4 * 10^6 * 4btye=16*10^6byte=16MB$

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