개요

Last updated - 2024년 10월 21일 Edit Source

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

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

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

참고로 $log N$은 상용로그가 아닌 밑이 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(N log N)$, $O(log N)$, $O(1)$

1
2
3
4

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