[알고리즘 접근] 시간 초과를 예방할 수 있는 방법

최근에 알고리즘 테스트를 준비하면서, 학교의 중앙도서관에 알고리즘 코딩테스트 관련 책이 소장되어 있다는 것을 확인하고 흥미가 생겨 그 책을 확인했다. 

한 장 한 장 넘기면서 내게 모자란 부분을 채우려고 책장을 넘기는 와중, 아주 흥미로운 부분이 눈에 들어왔다.

 

백준을 기준으로 하면, 단순히 연산을 1억 번 이상 진행하게 되면 1초가 걸린다는 부분이었다.

 

그렇다면, 이것을 반대로 생각해 보면, 문제에서 주어진 가장 큰 데이터 코너 케이스를 기반으로 가장 큰 수부터 고려해 문제를 해결해 나갈 수 있을 것이다.

 

어차피 작은 숫자는, 아주 큰 숫자를 기준으로 생각하여 문제를 풀었을 때 무조건 시간 초과가 나지 않을 것이다. 

 

만약에, N 이 2^15 제곱이고, 우리는 한 변이 N 인 정사각형 모양 2차원 배열에서 최악의 경우를 상정한다고 가정해 보자. 

이때, 2^30 은, 2^32 가 약 21억인 것을 감안하면, 한 7억~8억 에 해당하는 숫자일 것이다.

 

만약 그런데, 시간 제한이 0.5초라면, 여기에서 우리는 한 가지 결론에 도달할 수 있게 되는 것이다. 

 

"절대로 순차적으로 하나하나 확인하면서 문제를 해결해서는 안된다" 

 

라는 결론에 이를 수 있게 되는 것이다.

애초에, 가장 큰 수인 2^15 를 변으로 하는 정사각형 2차원 배열이라면, 최악의 경우 7~8초가 걸리는 일이기 때문이다. 내가 출제자라고 하더라도, 이 부분은 시간 초과가 나게 하는 테스트 케이스를 추가할 수 있을 것이다. 

 

시간 초과를 무조건적으로 예방할 수 있는 아주 좋은 방법은,

 

"들어갈 수 있는 가장 큰 숫자를 먼저 생각해 문제에 접근하기"

"Big O Notation 에서, N 에 가장 큰 숫자를 넣어서 그 결과가 1억 번의 연산을 넘지 않도록 하기" 

 

정도가 될 것이다.

 

만약, O(N^2) 인데, N 의 최대 크기가 100만 이라고 가정해 보자. 이 때, 제한 시간이 1초라면 무조건적으로 시간 초과가 날 것이라고 예견할 수 있다. 그렇다면, 반드시 시간복잡도가 낮은 다른 방법을 생각해 내야만 한다. 그래야, 시간을 효율적으로 사용하여 효과적으로 문제 해결을 할 수 있을 것이다.

 

출처 : https://lemonlemon.tistory.com/54