시간 복잡도와 인풋에 의한 알고리즘 설계

알고리즘이라는 세계에 처음 입문하게 되면 가장 먼저 만나는 녀석중에 하나라고도 할 수 있는 시간 복잡도.

오늘은 이 개념에 대해 빠르게 훑고, 코딩 테스트에 적용시켜서 생각해볼 수 있는 부분을 정리한다.

시간 복잡도 (Time Complexity)

일단, 복잡도라고 생각해서 말 그대로 마구 꼬여있고 이해하기 어려운 그런 의미의 ‘복잡’을 생각하면 안된다.

여기서 시간 복잡도라는 것은, 간단하게 말해서 얼마나 오래 걸리는가?에 대한 정도라고 생각하면 된다.

그러므로, 복잡도가 크다는 것은 곧 시간이 오래 걸린다는 의미이고, 반대로 작다는 것은 그만큼 빨리 처리된다는 뜻이다.

이러한 정도를 표기하기 위해서 가장 많이 쓰는 표기법은 Big - O 표기법이다.

Big O Notation

이는 ‘만약에 이 알고리즘이 가장 오래 걸린다면 얼마나 걸리는가?’를 따지는 표기법이다. 즉, 최악의 상황일 때 이정도 걸린다는 의미로 받아들이면 된다.

빅오 표기법에서는

상수 → logN → N → NlogN → N^2 → N^3 → 2^N 의 순서로 점점 시간이 오래 걸린다.

이때, 유의할 점은 만약 어떤 함수 내부에 다른 함수를 호출하는 경우가 있다면, 호출되는 함수까지 포함해서 시간 복잡도를 계산해줘야한다는 점이다.

이는 코딩 테스트를 준비할 때, 자신이 만들어낸 프로그램이 최악일 때 얼마나 걸리는지를 판단하는 데에 중요한 척도가 된다.

코딩 테스트

나는 프론트엔드 개발자로서 코딩 테스트를 준비하기에 자바스크립트 (Javascript)를 통해 준비하는 중이다.

자바스크립트 언어는 보통 1억번의 연산을 진행하는 경우에 처리시간이 1~5초 정도 걸린다고 한다.

그리고, 대부분의 코딩 테스트에서 패스의 여부를 가리는 실행시간 또한 1~5초 정도이다.

그러면, 이제 우리는 이렇게 생각해야 한다.

입력값의 범위와 수행시간

코딩 테스트에서는 명확한 입력값의 정보를 제공한다.

이러한 정보 중에서는 입력값의 범위에 대한 정보 또한 포함한다. 예를 들면 0 < N < 500 이런거다.

그러면, 우리는 이제 역으로 우리가 작성해야할 알고리즘이 어느정도의 복잡도를 가지면 좋을지를 판단할 수 있다.

예를 들어, 위처럼 입력값이 0 < N < 500 라면, 500^3 = 125000000 (1.25억)이다.

그럼 딱 1~5초 정도의 계산값이 나온다는 말이다.

그럼 우리가 작성할 알고리즘의 복잡도가 대충 O(N^3)의 복잡도를 가지도록 작성하면 통과할 수 있다는 말이 된다.

이처럼, 우리는 입력값의 범위와 실행시간을 쓱 보고 알고리즘의 복잡도에 대한 각을 잡을 수 있다는 뜻이다.

물론 모든 경우에 그냥 무조건 빠른 알고리즘을 만들 수 있다면 더 좋겠지만, 일단 어느정도 출제자로부터 힌트는 얻을 수 있는 셈이다.