코딩테스트 관점에서의 시간복잡도

개요

지금껏 시간복잡도에 대해선 무엇인지, 어떻게 구하는지에 대해서만 알았지

구체적으로 어떤 상황에 쓰이는지는 적절한 상황이 없었는데

 

코딩테스트를 준비하며 시간 제한, 메모리 제한 등과 함께 같이 제시된 조건들을 기준으로

시간복잡도를 생각해 어떤 알고리즘을 사용할 수 있을지 유추하기도 한다는 정보를 알게 되었다.

 

시간복잡도

O(1)	상수 시간(Constant time)
O(log N)	로그 시간(Log time)
O(N)	선형 시간
O(N log N)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

위는 자주 사용되는 시간복잡도로, 위쪽일수록 빠르다.

 

컴퓨터 과학에서 특정 알고리즘의 시간복잡도가 O(N^k)일 때, 이를 '다항 시간에 동작하는 알고리즘' 이라고 말한다.

ex) 이차 시간, 삼차 시간

보통 O(N^3)를 넘어가면 문제 풀이에서 사용하기 어렵다.

 

활용

이 포스팅을 통해 말하고자 하는 건 문제 조건을 확인해

최악의 경우에 어떤 시간복잡도를 갖는 알고리즘을 구현할지 유추할 수 있다는 것이다.

 

만약, 데이터 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초인 문제를 풀 때

최악의 경우 O(N)의 시간복잡도로 동작하는 알고리즘을 작성해야 할 것임을 알 수 있다.

 

마찬가지로 데이터 크기나 탐색 범위가 100억이나 1,000억을 넘어가는 경우

'이진 탐색'등과 같이 O(log N)의 시간복잡도로 동작하는 알고리즘을 작성해야 할 것이다.

 

이처럼 조건을 통해 어떤 알고리즘을 사용할지에 대한 힌트를 얻을 수 있다.

다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.

• N의 범위가 500인 경우: 시간복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우: 시간복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000인 경우: 시간복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000인 경우: 시간복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

정리

가끔 다른 알고리즘 문제에 조건으로 나오는 범위에 대해 

'값에 대한 범위를 제한하는 것 말고 어떤 역할이 있지 않을까?' 라는 생각을 한 적은 있지만

이정도로 활용할 방법을 한 적은 전혀 없었는데 이렇게 유용하게 쓰일줄은 몰랐다. 

때문에 이렇게 포스팅을 하게 됐다.

 

아직은 이 방법을 알았다해도 머릿속에 들어오지도 않고 또 하나의 외울 것으로 밖에 안보이지만

언젠가 활용해서 더 좋고 훌륭한 코드를 작성할 수 있지 않을까 싶다.

 

 

 

 

* 위 관련 정보들의 출처는 '이것이 취업을 위한 코딩테스트다' 책에서 가져옴