[이것이 코딩 테스트다] 알고리즘 성능 평가

 

시간 / 공간 복잡도

시간 복잡도 : 알고리즘의 수행 시간 분석

공간 복잡도 : 알고리즘의 메모리 사용량 분석

   (복잡도↓  →  알고리즘 Good)

 

cf.) 복잡도 : 성능적인 측면에서의 복잡도

- 시간 복잡도가 높다 = 수행 시간이 길다

- 시간 복잡도가 낮다 = 수행 시간이 짧다

- 공간 복잡도가 높다 = 많은 메모리가 필요하다

- 공간 복잡도가 낮다 = 많은 메모리가 필요하지 않다

 

 

 

빅오 표기법

빅오 표기법

: 복잡도를 표기하는 방식

: 가장 빠르게 증가하는 항만을 고려하는 표기법

: 극한의 개념으로 생각하면 쉽다

  ex) 3N^3 + 5N^2  →  O(N^3)

 

 

빅오 표기법 성능 순서

(← Good)                                                                                 (Bad →)
O(1)  -  O(logN)  -  O(N)  -  O(NlogN)  -  O(N^2)  -  O(N^3)  -  O(2^n)
상수        로그         선형       로그선형        이차        삼차         지수      (시간)

 

*유의!

- 코딩 테스트 문제에서 시간 제한은 1~5초

- 어느 정도 소요 시간을 예측해서 알고리즘을 설계하는 것이 중요하다!

- 문제 풀 때 가장 먼저 확인해야 할 것은 시간 제한 (수행시간 요구 사항)

 

ex) 시간 제한 = 1초

- N의 범위 : 500  →  O(N^3)인 알고리즘

- N의 범위 : 2,000  →  O(N^2)인 알고리즘

- N의 범위 : 100,000  →  O(NlogN)인 알고리즘

- N의 범위 : 10,000,000  →  O(N) 인 알고리즘

 

 

 

알고리즘 문제 해결

[ 알고리즘 문제 해결 방법 ]

1. 지문 읽기 (문제 하나하나 꼼꼼히 분석해보기, 단계별로 쪼개보기)

2. 요구사항(복잡도) 분석 (어느정도 성능으로 동작하는 프로그램을 작성해야 정답으로 인정되는지)

3. 문제 해결 아이디어 찾기

4. 소스 코드 설계 및 코딩

 

(바로 코드를 작성하는 것 보다는, 문제를 온전히 이해하고 어떻게 코드로 작성할지 정리가 된 다음에 코드 작성하는 것을 추천!)

 

 

cf.) 수행 시간 측정 소스코드

import time

start_time = time.time()
#중간에 프로그램 소스 코드 들어감
end_time = time.time()

print("time: ", end_time-start_time) #수행시간 출력