[공주는 코딩하고 싶어] 1회차. 코딩테스트란

이것이 취업을 위한 코딩 테스트다 with 파이썬 26-81p

 

파이썬은 C++/자바에 비해 코드가 짧고 직관적

파이썬은 실행시간이나 메모리 관리가 매우 중요한 문제 유형이 아니면 짧은 코드로 표준 라이브러리만 활용해 프로그래밍 가능하다.

 

실습 환경 구축

온라인은 책에서 추천하는 repl it을 사용하기로 결정하고

오프라인은 파이참을 사용하기로 했다.

 

복잡도 : 알고리즘의 성능을 나타내는 척도.

1) 시간 복잡도 : 특정 크기 입력에 알고리즘이 얼마나 오래 걸리는가. 알고리즘을 위해 필요한 연산의 횟수.

2) 공간 복잡도 : 특정 크기 입력에 알고리즘이 얼마나 많은 메모리를 차지하는가. 알고리즘을 위해 필요한 메모리의 양

복잡도가 낮을수록 좋은 알고리즘!

 

시간 복잡도와 공간 복잡도는 일종의 trade-off 관계

 

시간 복잡도

- 시간 복잡도를 표현할 때는 Big-O 표기법을 사용한다.  (절대적이지는 않다.)

- 일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다.

Big-O 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(N logN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

-> 위에 있을수록 더 빠르다.

 

공간 복잡도

- 시간 복잡도와 마찬가지로 Big-O 표기법을 사용한다.

 

실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법.