2.2.2 시간 복잡도를 줄이는 방법

시간 복잡도 수식에 가장 큰 입력을 대입하여 계산한 결과가 1억 이상이라면 풀이가 충분히 효율적이지 않은 것입니다. 따라서 더욱 효율적인 풀이를 생각해 내어 시간 복잡도를 줄여야 합니다. 앞으로 살펴볼 많은 알고리즘과 자료 구조는 시간 복잡도를 줄여 더욱 효율적인 코드를 작성하기 위한 것입니다.

예를 들어 정렬된 배열 arr에서 특정 원소의 위치를 찾는 문제를 생각해봅시다. 배열의 모든 원소를 순회한다면 이는 O(N)의 시간 복잡도가 소요됩니다. 하지만 정렬되어 있다는 조건에 주목하면 이후에 살펴볼 이진 탐색을 적용할 수 있다는 것을 알 수 있습니다. 이진 탐색의 시간 복잡도는 O(logN)이므로 훨씬 효율적으로 탐색할 수 있습니다.

또 배열에서 중복을 제거한 원소들을 찾고 싶을 때 원소별로 배열 전체를 순회하면 O(N²)의 시간 복잡도가 소요됩니다. 이때는 자료 구조 Set을 이용하면 O(N)으로 해결할 수 있습니다. O(N²)과 O(N)은 N의 크기가 커질수록 엄청난 효율성 차이를 보입니다.

따라서 문제 조건에 맞는 적절한 알고리즘과 자료 구조를 이용하는 것이 코딩 테스트의 핵심입니다.