코딩테스트는 기업이 지원자의 minimum quality를 보장하고 싶어서 만든 제도이다.
따라서 기본지식을 테스트하기 위해 문제마다 핵심 알고리즘을 넣는 게 현재까지의 코테 트렌드이다.
이 사고를 바탕으로 핵심 알고리즘 1개 들어갔다는 가정을 세운다.(어려운 문제는 1개+α)
그러면 n과 시간복잡도 관계에 따른 핵심 알고리즘 추리로 빠른 문제 전개를 진행한다.
문제 순서도
1. n개수를 파악하여 최대 시간 복잡도(빅오 표기법)를 생각한다.
2. 시간복잡도에 따른 알고리즘을 생각한다.
3. 시간복잡도에 따른 초변환을 하여 가능한 시간인지 파악한다.
4. 해당 알고리즘과 문제를 대입해 보며 가장 적절한 알고리즘을 빠르게 찾아낸다.
1. n개수와 시간 복잡도
2. 시간 복잡도와 초
3. 시간복잡도에 따른 알고리즘
O(1): 해시테이블(검색)
O(logN):이진트리, heapq(우선순위 큐), 이진탐색, 소수 구하기(약수제거) => 에라토스테네스의 체(n**0.5)
O(N): dp(10만 개 이상)
O(NlogN): 정렬+투포인터, 정렬, LIS(이진탐색 쓸 경우)
O(N^2): 2차원 배열 완전탐색(bfs,dfs), 그래프 완전탐색, 슬라이딩 윈도우, 브루트포스, 다익스트라, 프림(MST)
O(N^3): 플로이드
