Big O 표기법

실제 알고리즘 러닝타임을 측정하기 위함도 있지만

장기적으로 데이터가 증가함에 따라 처리 시간의 증가율을 예측하기 위해 사용

 

시간 복잡도, 공간 복잡도 분석은 문제 풀이의 핵심

(= 최악의 경우에 대한 연산 횟수가 중요, 즉 최악의 경우의 시간 복잡도를 우선적으로 고려)

(= 시간 제한 1초, 메모리 제한 128MB)

* 문제를 해석하기 전에 조건을 먼저 확인

-  문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 알 수 있음

EX)

데이터 개수가 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성 or

데이터 크기나 탐색 범위가 100억이나 1,000억을 넘어가는 경우 "이진 탐색"과 같이 O(logN)의 시간 복잡도로 동작하는 알고리즘을 작성

 

코딩 테스트

- 대부분 리스트(배열)를 사용해서 푼다

(= 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문)