이것이 취업을 위한 코딩테스트다 - 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)	# 수행 시간 출력