프로그램의 계산은 시간이 걸리는데 10^8번 연산을 하면 1초가 걸린다.
완전 탐색
- 순열의 시간 복잡도 ⇒ n!
- 조합의 시간 복잡도 ⇒ 2^n
- 2^29 ⇒ 536,870,915
- 2^30 ⇒ 1,073,741,824
- 부분집합을 구하는 시간 복잡도 ⇒ 2^n
입력 제한으로 확인할 수 있는 시간 복잡도
- n < 20 이면 어지간한 저질 구현도 통과가 됨.
- n ≤ 100 이면 적당한 삼중 루프가 통과됨. (브루트 포스, 빡구현, 완전탐색)
- n ≤ 1000 이면 적당한 이중 루프가 통과됨.
- n ≤ 10000 이면 머리를 좀 써야함.
- n < 10^8 이면 수학적 기믹이 필요함.
데이터의 범위( 코틀린 기준)
자료구조
수학적 개념들