알고리즘
[PS] 시간복잡도 - 코딩테스트 TIP
코딩테스트 문제를 풀 때, 입력의 크기 n에 대해 시간초과가 나지 않도록 알고리즘을 고려해야 한다.이 사실을 알고 있지만, 항상 특정 시간복잡도에 대해 n의 크기를 어느정도까지 가져갈 수 있는지를 까먹어 해당 글을 작성하게 됐다. 1️⃣ 입력의 크기에 따른 시간복잡도입력의 크기시간복잡도대표 알고리즘n \[O(n!)\]완전탐색n \[O(2^n)O(n^2*2^n)\]Bitmask DPn \[O(\sqrt{2}^n)\]MITMn \[O(n^3)\]Matrix Chain Multiplication(행렬 곱셈)n \[O(n^2)\] n \[O(n\sqrt{n})O(n\log^{2}n)\]모스(Mo's) 알고리즘n \[O(n\log n)\]정렬, LIS(최장 증가 부분 수열)n \[O(n)\]DP, DFS, Tre..
