[강의] 코딩테스트 시간복잡도

날짜 : 2024-06-13

시간 : 20:00~22:00 (2h)

시간 복잡도 측정하는 이유 : 미리 실행시간을 측정해서, 최대 입력일 때 버틸 수 있는지를 보는 것

시간 복잡도 : 실행시간과 입력값 n의 함수 관계

n은 문제의 크기, 입력 데이터의 크기, 반복 횟수 등 문맥에 따라 다를 수 있음

어떤 수치가 반복 횟수에 영향을 주는지 알면 된다!

시간 복잡도를 통해서 실행시간을 정확히 알 순 없음. 경항성만 파악하는 것이 목표

같은 O(n*2)이더라도 앞에 계수가 뭐냐에 따라 시간 복잡도 통과할수도 실패할수도 있음

코딩테스트에서는 빅오는 같은데 함수가 시간이 많이 걸려서 통과 안되는 경우는 거의 없긴 함

[함수, 연산자, 메서드의 시간복잡도]

set에 값이 있는지 체크하는 코드, if val in {1,3,5,7} : O(1)

sort() : O(nlogn)

heappush() / heappop() : O(logn)

deque.popleft() <<< del list[0]

[심화 - 흔히 실수하는 예시]

longest Consective 예시 - 중복 제거하여 시간복잡도 단축

if prev not in nums_dict : 시작점만 그 다음 while문을 돌도록 구현하여 중복을 제거함

상수 시간도 완전 무시할 순 없다. (specific한 영역이긴 함)

동작 방식을 알아야 한다.

bfs의 시간복잡도 : O(n^3)가 아니라 O(V+E) ✔ ✔ ✔ -> WHY?

보통 V, E가 크게 주어지지는 않기 때문에 bfs, dfs로 풀 때는 시간 복잡도가 초과되지않는다고 생각해도 됨

완전 탐색을 할 때 재귀를 많이 쓴다.

재귀의 시간복잡도 : 시간 복잡도 계산은 가능하지만, 엄밀하지 못하다. 수학적으로 복잡.

얼추 <코드 실행 2^n * 코드의 시간복잡도> 로 계산

백트래킹의 시간복잡도 : 계산이 불가한 영역이 있음

70% 시간복잡도를 계산하면 유용. 나머지 30%는 계산 못하는 경우거나 의미 없는 경우

[코테 실전 적용]

기준점 : 10^8

시간복잡도는 만능이 아니지만

이렇게 푸는게 맞나? 싶을 때 시간 복잡도로 풀이에 대한 확신을 얻을 수 있음

시간복잡도에 맞는 알고리즘 떠올리기 가능

시간 복잡도를 계산하고 코드를 작성하기

cod