시간 복잡도

알고리즘을 코드로 구현할 때, 시간 복잡도(Time Complexity)를 고려해야합니다. 시간 복잡도를 고려한다는 것은 연산횟수에 비례하여 시간이 얼마만큼 걸리는지에 대한 정도를 의미합니다.

시간의 비율이 최소화될수록 효율적인 알고리즘일 수도 있겠네요. 시간복잡도를 표현하는 방법으로 Big-O, Big-Ω, Big-θ가 있습니다. 이 세가지 방법 중 최악의 경우를 방지하기 위해 최악의 시간 복잡도인 Big-O 표기법을 많이 사용합니다.

표기법	의미	예
O(1)	입력값이 증가해도 시간을 늘지 않는다.	arr[3]와 같이 인덱스 접근
O(N)	입력값과 시간이 같은 비율로 증가하는 것입니다.	배열을 한번 반복하는 경우
O(log N)	경우의 수가 절반으로 줄여지는 경우를 말합니다.	BST와 같이 노드가 이동할때마다 절반으로 줄어드는 경우, 이분 탐색
O(N^2)	입력값이 증가함에 따라 N의 제곱도 증가하는 경우를 말합니다.	이중 반복문
O(C^N)	기하급수적으로 입력값이 증가하는 경우를 말합니다.	재귀로 구현하는 피보나치 수열

메모리 제약 사항

자바나 C/C++ 언어에서는 자료형의 표현 범위 제약이 있다. 예를 들어, 2,147,438,647 보다 더 큰수를 처리하기 위해 long long 자료형을 사용한다. 이보다 더 큰 수를 담으려면 BigInteger 라이브러리를 지원하지만 이는 코딩테스트에 작성하기엔 어렵기 때문에 잘 사용하지 않는다.

파이썬에는 직접 자료형을 지정할 필요없다.

리스트 고려사항

대체로 코딩 테스트에서는 128MB ~ 512MB 정도로 메모리를 제한한다. 때로는 수백만 개 이상의 데이터를 처리하는 문제가 출제된다.

데이터의 갯수(리스트 길이)	메모리 사용량
1,000	약 4KB
1,000,000 (백만)	약 4MB
1,000,000,000 (십억만)	약 40MB

채점 환경

파이썬은 C/C++에 비해 동작속도가 2배 정도 느리다. 대체적으로 시간 제한이 1초이고 데이터의 갯수가 100만 이면 $O(NlogN)$ 이내의 시간 복잡도까지 풀어야 한다. 어느정도 시간 복잡도의 알고리즘으로 풀 수 있을 것인지 예측할 수 있어야 한다.