맞왜틀 : 1초에 1억번 연산

PS풀이를 할 때 제일 먼저 볼 것은 바로 문제에서 주어진 시간과 N이 얼마인지 확인하는 것이다.

 

그 내에서 어떤 연산을 하느냐에 따라 초당 연산횟수가 다를 수도 있지만 컴퓨터는 가장 표준적으로 1초에 1억번의 연산을 한다. 

 

예를 들어 1초만 허락된다는 공통조건을 전제로 한 상태에서,

 

N <= 10,000은 대강 2중 for문 정도가 가능하다는 뜻이다 10,000^2 = 1억

이 경우 시간복잡도는 O(N^2)에 해당한다. 대표적으로 벨만 포드 알고리즘이 해당한다. 

 

이외에도 여러 연산이 있다. 제일 먼저 할 것이 이런 것들이다.