라이브러리 함수는 공짜가 아닙니다.

시간 초과를 받는 주 원인이 무엇일까요? 많은 초보들은 이에 대해 '코드가 너무 길어서 그렇지 않을까?' 하고 생각합니다.  하지만 실상은 반대인 경우가 더 많습니다. 알고리즘 문제 풀이에서 코드의 수행 시간을 결정하는 가장 큰 요인은 일반적으로 시간 복잡도이며, 시간 복잡도를 고려하여 작성하였다면 아무리 엄청나게 긴 코드를 작성하더라도 한 번 실행된 것만 가지고 웬만한 문제에서 시간을 초과시킬 일은 없습니다. 반면에 시간 복잡도를 고려하지 않고 오로지 답만 구할 수 있도록 코드를 짧게 줄인 코드는 시간을 초과할 가능성이 높습니다.

 

이와 관련하여 대표적으로 흔하게 하는 실수가 바로 라이브러리 함수의 시간 복잡도를 고려하지 않고 그 기능만을 목적으로 사용하는 것입니다. 아주 편리하지만 매우 비효율적인, 대표적인 라이브러리 함수들의 오용 예시들에는 다음과 같은 것들이 있습니다.

 

• (C++) find(vector.begin(), vector.end(), x), (Python) x in list, list.count(x), list.index(x): 아무런 처리를 해놓지 않은 평범한 배열에서 어떤 특정한 원소의 값을 찾는 것은 그 어떤 알고리즘으로도 모든 원소를 전부 탐색하는 것보다 빠르게 구현할 수가 없습니다. 당연히 라이브러리들도 평범한 배열 객체에 대해서는 별도의 전처리를 하지 않으며, 이 안에 특정 원소가 있는지, 몇 개가 있는지를 찾는 것은 이 배열 전체를 탐색하는 것으로 이루어집니다. 직접 반복문을 돌려서 찾는 것에 비해 적어도 시간 복잡도상으로는 빠르지 않습니다. Python의 경우 x in str도 마찬가지로 느립니다.
• (C++) vector.erase(vector.begin()), (Python) list.pop(0): 역시 아무런 처리를 해놓지 않은 평범한 배열에서 맨 앞의 원소를 지우는 것은 간단한 일이 아닙니다. 배열의 시작점이 고정되어 있기 때문에, 맨 앞의 원소를 지운다면 라이브러리들은 이 배열의 형태를 올바르게 유지하기 위해 뒤의 모든 원소를 전부 앞으로 한 칸씩, 수작업으로 당겨오게 됩니다. 이는 당연히 배열의 크기에 비례하는 시간이 걸립니다. 꼭 맨 앞이 아니라 임의의 원소를 지우더라도 마찬가지입니다. 해당 원소의 위치보다 뒤쪽의 모든 원소들을 전부 앞으로 한 칸씩 당겨오는 작업이 동반됩니다. 단, 가장 뒤쪽의 원소를 지우는 것은 뒤에 당겨올 원소가 없기 때문에 문제가 되지 않습니다.
• (C++) vector.insert(vector.begin(), x), (Python) list.insert(0, x): 위와 같은 이유로 배열의 맨 앞이나 임의의 위치에 원소를 추가하는 것도 비효율적입니다. 어떤 위치에 원소를 새로 삽입하면 기존에 그 위치에 있던 원소와 그 뒤의 모든 원소들을 아까와는 반대로 전부 뒤로 한 칸씩 밀어내야 하기 때문입니다. 역시 마찬가지로 배열의 맨 뒤에 원소를 추가하는 것은 이후 밀어내야 할 원소가 없기 때문에 문제가 되지 않습니다.
• (C++) reverse(vector.begin(), vector.end()), (Python) list = list[::-1]: 배열을 뒤집는 것도 공짜가 아닙니다. 배열을 뒤집는다는 것은 말 그대로 모든 원소의 위치를 전부 뒤집은 후의 위치로 옮긴다는 것입니다. Python의 경우 슬라이싱을 하는 행위 자체가 해당 범위의 원소들을 복사한 새로운 list 객체를 만들어내는 것이고, 어떤 객체를 새로 만드는 데에는 당연히 그 객체의 크기에 비례하는 시간이 걸립니다.
• (Python) 큰 정수 연산: Python의 int는 사실상 표현할 수 있는 수의 크기에 제한이 없는, 임의의 큰 수를 지원하는 biginteger입니다. 하지만 그것이 곧 아무리 큰 정수에 대해서도 연산을 똑같이 빨리 할 수 있다는 뜻은 아닙니다. 사람이 한 자릿수끼리의 사칙연산을 계산하는 것보다 열 자릿수끼리의 사칙연산을 계산하는 것이 훨씬 느리듯이, Python도 마찬가지로 n자리의 수끼리의 사칙연산을 계산하는 것보다 10n자리끼리의 사칙연산을 계산하는 것이 훨씬 느립니다. 그나마 덧셈, 뺄셈의 경우 자릿수에 비례하는 수준이지만, 곱셈이나 나눗셈은 그보다도 훨씬 더 급격하게 느려집니다. 따라서 단순히 Python의 큰 수 표현 능력만 믿고 수가 폭발적으로 증가하는 것을 그대로 놔둬서는 안 됩니다. 대표적인 경우가 x로 나눈 나머지를 구하라는 문제들인데, 이런 문제는 보통 원래 답 자체가 어마어마하게 크기 때문에 나눈 나머지를 구하라는 의미이므로 그냥 원래 답을 구하고 마지막에만 x로 나누었다가는 계산 과정에서 시간이 초과될 가능성이 높습니다.
• (C++) int a[N] = {0}, memset(a, sizeof(a), 0), fill(a, a + N, 0), fill_n(a, N, 0), (Python) [0] * N 등: 크기가 N인 배열을 초기화하는 것은 N에 비례하는 시간이 걸립니다. 당연하게도, 배열의 전체를 초기화하는 것은 그 배열의 모든 원소를 전부 순회하면서 그 값을 원하는 값으로 세팅하는 것과 같습니다. memset처럼 보다 빠르게 메모리를 채워나가는 걸 쓰더라도, 상수적으로 몇배 정도가 빠를 뿐 시간 복잡도가 개선되는 것은 아닙니다. 예를 들어, 테스트 케이스가 최대 10만 개인 문제에서 크기 10만의 배열을 매번 새로 만들면 대략 100억 번 정도의 연산이 요구되며, 컴포넌트가 여럿으로 분리된 그래프에서 새로 BFS나 DFS를 시작할 때마다 visited 배열을 전부 새로 만들고 초기화를 하면 최악의 경우 정점의 개수의 제곱에 해당하는 시간 복잡도가 될 수도 있습니다.

 

물론 이와 같은 라이브러리 함수를 필요 시에, 시간 복잡도를 고려하여 감당이 되는 한도 내에서 사용하는 것은 반드시 잘못된 것은 아닙니다. 그러나 단순히 라이브러리가 해당 기능을 지원한다는 이유만으로, 귀찮은 구현을 직접 하지 않아도 한 줄로 편리하게 처리할 수 있다는 것만을 생각하고 사용했다가는 시간 초과의 늪에 빠지기 쉽습니다. 라이브러리 함수는 절대 우리가 직접 구현하면 느린 로직을 기적같이 초단시간에 해내는 마법사가 아닙니다. 라이브러리 함수들도 내부적으로는 우리가 직접 구현하는 것과 같은 자료구조를 사용하고 있으며, 다만 그것이 좀 잘 되어있을 뿐입니다. 내가 어떤 연산의 시간 복잡도를 어떻게 개선해야 할지 모르겠다면, 라이브러리 함수도 그것을 알아서 해주지 못할 가능성이 높습니다. 따라서 라이브러리 함수를 사용하기 전에 해당 함수의 시간 복잡도가 어떻게 되는지를 레퍼런스를 통해 알아보고, 어디까지나 해당 시간 복잡도로도 문제 해결이 가능한 경우에만 그 라이브러리의 기능을 사용하도록 해야 합니다.