BigO와 입력제한

"10^8 = 1초"

코딩테스트는 시간제약이 있습니다.

시간을 잡아먹는 경우 중에,

1. 구현하다가 막히는 경우

아이디어를 상세히 짜놓고 나서 푸는 방식으로 예방할 수 있습니다.

2. 시간복잡도에서 막히는 경우

문제에서 제시하는 조건인 입력 조건을 이용하면 됩니다.

(우선, 시간복잡도는 루프의 개수 와 자료구조 를 종합하여 계산합니다.)

(1) n <= 20 인 경우,

브루트 포스로 풀어도 되는 경우 (즉, 최적화 없이 그냥 푸는 방법) 도 통과!
O(n!), O(2^n)

(2) n <= 100 인 경우,

웬만한 삼중 루프 통과
O(n^3), 플로이드와샬 알고리즘

(3) n <= 1000 인 경우,

웬만한 이중 루프 통과
O(n^2), 벨만포드 알고리즘

(4) n <= 10,000 인 경우,

O(n), O(nlogn)
DP, dijkstra, unionFind, segmentTree, twoPointer

참고 : https://www.youtube.com/watch?v=PFKPdjdWbQ8