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

※ 다음 강좌의 내용을 정리한 것입니다.

www.youtube.com/watch?v=Pj3IX2VehkU&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=2

 

- 알고리즘의 성능을 평가하기 위해 복잡도의 개념이 사용됩니다.

시간 복잡도(수행 시간)와 공간 복잡도(메모리 사용량)가 있으며, 같은 기능을 수행할 때, 복잡도가 낮을수록 좋은 알고리즘입니다.

 

- 빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법입니다.

함수의 상한만을 나타내게 됩니다.(Upper-bound)

시간 복잡도(N은 데이터의 개수)

- 모든 2중 반복문의 시간 복잡도가 O(N²)인 것은 아닙니다.

또한, 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 합니다.

 

- PyPy의 경우 때때로 C언어보다도 빠르게 동작하기도 합니다. 가능하면 PyPy로 제출하는게 좋습니다.

Python3로 제출해서 안되면 PyPy로, PyPy로 안되면 Python3로 제출해 보는 게 좋습니다.

 

- 코딩테스트 문제에서 시간제한은 통상 1~5초가량이며, 명시되어 있지 않은 경우, 대략 5초 정도로 생각하고 푸는 것이 합리적입니다.

 

- 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행 시간 요구사항)입니다.

 

시간 복잡도 Example

- 대부분 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제합니다.

(먼저, 문제를 온전히 이해하고, 어떤 식으로 코드를 작성해나갈지 생각한 다음에 코드를 작성하는 걸 추천합니다.)

 

- 수행 시간 측정은 다음과 같이 합니다.

 

시간 측정