이것이 취업을 위한 코딩테스트다 - 1. 코딩 테스트 개요
복잡도( Complexity )
- 복잡도는 알고리즘의 성능을 나타내는 척도
- 시간 복잡도와 공간 복잡도로 나눌 수 있다.
시간 복잡도 ( Time Complexity )
ㆍ특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미
ㆍ알고리즘을 위해 필요한 연산의 횟수
공간 복잡도 ( Space Complexity )
ㆍ특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
ㆍ알고리즘을 위해 필요한 메모리의 양
* 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법
시간 복잡도
- 알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간복잡도를 의미한다.
- 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과 ( Time Limit Exceeded ) ' 라는 메세지와 함께 오답 처리
- 시간 복잡도를 표현할 때는 빅오( Big-O ) 표기법을 사용한다.
ㆍ 빅오 표기법을 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법
ㆍ 다시 말해 함수의 상한만을 나타낸다.
- 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다.
- 그러니 최악의 경우의 시간 복잡도를 우선적으로 고려해야한다
| 빅오 표기법 | 명칭 |
| O(1) | 상수 시간( Constant time ) |
| O(logN) | 로그 시간( Log time ) |
| O(N) | 선형 시간 |
| O(NlogN) | 로그 선형 시간 |
| O(N^2) | 이차 시간 |
| O(N^3) | 삼차 시간 |
| O(2^n) | 지수 시간 |
- 자주 등장하는 시간 복잡도 표인데, 위쪽에 있을수록 더 빠르다.
- 일반적인 코딩 테스트에서는 상수를 고려해야하는 경우는 적지만, 빅오표기법이 항상 절대적인 것은 아니다!
- 특정한 알고리즘의 시간 복잡도가 O(N^K) 일 때( 이때 K는 상수 값을 가진다 ), 이를 ' 다항 시간에 동작하는 알고리즘 ' 이라고 한다.
ㆍ이차 시간, 삼차 시간 등이 모두 다항 시간에 해당한다.
- 시간 복잡도 분석은 문제 풀이의 핵심이다.
- 알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 먼저 보기도 한다
- 시간제한이 1초인 문제에 대한 예시
ㆍN의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다
ㆍN의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다
ㆍN의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계...
ㆍN의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계...
공간 복잡도
- 공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다.
- 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼 메모리 사용량에도 절대적인 제한이 있다
ㆍ일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.
- 코딩 테스트 문제는 대부분 리스트(배열)을 사용해서 풀어야 한다.
- 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자
ㆍint a[1000] : 4KB
ㆍint a[1000000] : 4KB
ㆍint a[2000][2000] : 16KB
- 코딩 테스트에서 보통 메모리 사용량을 128~512MB 정도로 제한한다
ㆍ다시 말해 일반적인 경우 데이터의 갯수가 1000만 단위가 넘어가지 않도록 설계할 것
- 파이썬에서도 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억하자
ㆍ만약 리스트의 크기가 1000만 단위 이상이라면 알고리즘을 잘못 설계한지 고민할 것
시간과 메모리 측정
- 수행 시간을 측정하는 소스코드 예시
import time
start_time = time.time() # 측정 시작
#프로그램 소스 코드
end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력