[코테준비] 시간 복잡도를 고려하자

시간복잡도 줄이는 법

최대 1억이 넘는가를 확인한다 1억 = 1초

N의 크기를 보고 알고리즘을 유추

순서대로 시간을 줄여보자

1. O(n) 탐색보다는 hashmap을 쓰자
   • 단, hash도 저격당하면 O(n)임 -> 100점은 못 받는다고 보면 된다 (하지만 풀었죠?)
2. 정렬이 되어 있다면 binary search
   1. 이진 탐색  -> O(log n)
   2. 정렬 -> O(NlogN)
3. 투포인터 알고리즘 -> O(N)
   • 리스트를 순차적으로 접근해야할 때 사용가능 ex) 연속 수열의 합
4. 누적합 배열을 이용 -> O(N)으로 구현 가능
   • DP문제처럼 누적합 배열의 이전 값을 이용하면 O(N)으로 구현