알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 시간복잡도

[무료] Do it! 알고리즘 코딩테스트 with Python - 인프런 | 강의

자료구조/알고리즘을 C++로 배워서 파이썬으로 구현할 때 어려움이 있었기 때문에 위 강의를 듣고 정리해보겠삼

 

01-1 시간 복잡도 표기법 알아보기

시간 복잡도: 주어진 문제를 해결하기 위한 연산 횟수

 

시간 복잡도 유형

- Ω(n): best case의 연산 횟수를 나타낸 표기법

- θ(n): average case의 연산 횟수를 나타낸 표기법

- O(n): worst case의 연산 횟수를 나타낸 표기법

 

코딩 테스트에서 사용하는 시간 복잡도 유형

빅오를 기준으로 계산하는 것이 좋음 (모든 테스트 케이스를 통과해야하기 때문)

 

01-2 시간 복잡도 활용하기

알고리즘 선택의 기준으로 사용

1. 데이터의 크기 범위 보기

2. 최악을 기준으로 보기 때문에 가장 큰 값 보기

3. 2초안에 해결해야 되기 때문에 2 x 20,000,000

 

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

 

알고리즘 적합성 평가

버블 정렬 = (1,000,000)² > 40,000,000 -> 부적합 알고리즘

병합 정렬 = 1,000,000log₂(1,000,000) < 40,000,000 -> 적합 알고리즘

 

시간 복잡도를 바탕으로 코드 로직 개선하기

- 시간 복잡도 도출 기준

① 상수는 시간 복잡도 계산에서 제외한다.

② 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.