개요

코딩테스트를 진행함에 있어서, 잊어버리기 쉬운 기본 내용 정리 및 코드트리 정리

• 입출력
• 수학
• 문자열
• 정렬
• 자료구조
• DP
• 그래프 탐색

---

시간복잡도

O(1) < O(log₂n) < O(n) < O(n log₂n) < O(n²) < O(2ⁿ)

참고로 $logN$은 상용로그가 아닌 밑이 2

$N<=10$

• 시간 복잡도 $O(N!)$, $O(2^N)$, $O(3^N)$

$N<=20$

• 시간 복잡도 $O(2^N)$

$N<=100$

• 시간 복잡도 $O(N^4)$

$N<=500$

• 시간 복잡도 $O(N^3)$

$N<=1,000$

• 시간 복잡도 $O(N^2)$, $O(N^{2}logN)$

$N<=100,000$

• 시간 복잡도 $O(N)$, $O(NlogN)$, $O(logN)$, $O(1)$

---

공간복잡도

int a[2천만] : 80MB
int a[2백만] : 80 / 10 = 8MB
char a[2천만] : 80 / 4 = 20MB
double a[2천만] : 80 * 2 = 160MB