Part1. 복잡도

복잡도

시간 복잡도

표기

• 빅오 표기법
  • 가장 빠르게 증가하는 항만을 고려!!
    

⭐코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요!!

⭐ 상수를 고려해야하는 경우도 존재!! 빅오 표기법이 항상 절대적인 것은 아님!

시간 제한이 1초인 문제에 대한 예시(대략 10,000,000개에 1초)

1. N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
2. N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
3. N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
4. N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

공간 복잡도

int를 기준으로 리스트 크기에 따른 메모리 사용량!!

1. int a[1000]: 4KB
2. int a[1000000]: 4MB
3. int a[2000][2000]: 16MB

⭐보통 코딩 테스트에서는 메모리 사용량이 128~512MB
⭐ 10000만 단위 이상의 리스트 크기는 이하면 안됨!

시간 메모리 측정

import time
start_time = time.time()

end_time = time.time()
print("time :", end_time-start_time)

최신 출제 경향과 준비 방향

코딩 테스트는 문제 해결 능력을 확인하는 시험

• 출제 빈도 높은 문제: 그리디, 구현, DFS/BFS, 다이나믹 프로그래밍, 그래프 이론, 정렬 …