[알고리즘] 코딩테스트 - 복잡도

복잡도란?

복잡도 (Complexity)는 알고리즘의 성능을 나타내는 척도이다.

복잡도는 크게 두가지로 구분할 수 있다.

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

 

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

 

동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다.

 

시간복잡도와  공간복잡도는 일종의 거래 관계가 성립한다. 메모리를 많이 사용하는 대신 시간적 이점을 얻을 수 있는 경우가 있는데 이 방법으로 메모이제이션 기법이 있다.

 

 

시간 복잡도

시간 복잡도를 표기할 때는 빅오(big -O)표기법을 사용한다. 빅오 표기법을 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하여 표기하는 표기법이다. 흔한 케이스는 아니지만 차수가 작은항의 값이 매우 클때 미치는 영향이 크므로 빅오 표기법이 항상 절대적인 것은 아니다.

 

일반 적인 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제풀이에서 사용하기 어렵다.

시간 복잡도 분석은 문제풀이의 핵심이다. 문제의 조건 부터 확인하면 문제를 풀기위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치챌 수 있다. ex_) 데이터 N이 1000만개를 넘어가며 시간제한이 1초라면 O(N)으로 동작하는 알고리즘을 작성해야 한다고 예측할 수 있다.

 

제한시간이 1초인 문제들에 대하여...

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 사용하여 문제를 해결할 수 있다.
• N의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 사용하여 문제를 해결할 수 있다.
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(Nlog N)인 알고리즘을 사용하여 문제를 해결할 수 있다.
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 사용하여 문제를 해결할 수 있다.

 

공간 복잡도

공간 복잡도를 표기할 때도 시간 복잡도와 마찬가지로 빅오(big -O)표기법을 사용한다. 일반적으로 메모리 사용량에도 절대적인 제한이 있는데 사용량 기준은 MB단위로 제시된다. 

코딩테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한하므로 일반적으로 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다.

 

 

시간 - 메모리 측정

파이썬에서는 프로그램 수행시간, 메모리 사용량을 측정할 수 있다.

#수행시간 측정 소스코드
import time
start_time = time.time() #측정 시작

#프로그램 소스코드
end_time = time.time()
print("time:" , end_time - start_time) #수행 시간 출력

자신이 설계한 알고리즘의 성능을 실제로 확인해보기 위하여 시간측정 라이브러리를 사용해보는 습관을 기르는 것이 좋다.

 

---

책 : 이것이 취업을 위한 코딩테스트 이다.