알고리즘문제 시간 제한

백준 문제보면 항상 문제설명 위에 있다.

 

알고리즘 문제를 풀다보면 시간제한이란 것이 항상 존재한다.

 

시간제한은 해당 문제의 풀수있는 알고리즘을 제한하기 위해서 존재한다.

 

이때 일반적으로 1초 = 1억번 계산한다라고 생각하면 될것.

 

이 시간과 주어진 문제의 입력조건의 최대값을 참고해서 알맞는 알고리즘을 도출해낼것.

 

예를 들어서 시간 제한: 2초, input값이 최대 10억일때. 

 

무식하게 for문 2번 사용하는 짓은 절대로 문제가 안풀린다. (O(N^2)이기 때문에)

 

알고리즘의 복잡도는 O(N)도 부족하다, 적어도 O(NlogN)은 되어야지 해당 문제를 풀수가 있다.

 

요약) 

 - 시간제한 1초는 대략 1억번이다. 

 - 최대값 생각해서 알고리즘 잘 골라서 풀어라