시간 복잡도

코딩 테스트 문제 중에는 프로그램 실행 시간이 특정 시간 미만이어야 한다는 조건이 있는 경우가 있습니다. 일반적으로 이 시간은 1초를 기준으로 하며, 문제에서 주어지는 모든 형태의 입력을 처리하는 데 프로그램이 1초 이상 걸리면 안 된다는 의미입니다. 시간 제한이 있는 문제에서는 실행 시간이 해당 제한 시간을 넘어간다면 시간 초과(TimeOut, TO)가 발생하여 오답으로 처리됩니다.

 

우리가 작성하는 코드가 문제에서 요구하는 만큼 효율적인지 알려면 어떻게 해야 할까요? 코드의 실행 시간을 측정하는 가장 쉬운 방법은 직접 예시 입력을 넣어 프로그램을 실행해보는 것입니다. 하지만 효율성을 측정하는 문제의 경우 대부분 입력 크기가 매우 큽니다. 1만 개의 입력을 받는 문제를 풀 때 코드가 효율적인지 측정하기 위해 모든 입력을 직접 넣을 수 없습니다.

 

이때는 우리가 작성하는 코드의 실행 시간이 입력 데이터의 크기와 어떤 상관관계가 있는지 파악해서 그 효율성을 계산합니다. 이렇게 코드 혹은 알고리즘의 실행 시간과 데이터의 상관관계를 가진 시간 복잡도라고 합니다.

 

시간 복잡도는 코딩 테스트에서 매우 중요한 개념으로, 이를 모르면 코딩 테스트에서 요구하는 효율적인 코드를 작성할 수 없습니다.

---

시간 복잡도(time complexity)는 코드의 실행 시간이 어떤 요인으로 결정되는지 나타내는 시간과 입력 데이터의 함수 관계입니다. 즉 코딩 테스트에서는 자신이 짠 코드의 시간 복잡도를 계산하여 문제에서 요구하는 입력을 제한 시간 내에 해결할 수 있는지 파악해야 합니다.

빅오 표기법

코딩 테스트에서 효율성을 검사하는 데 사용하는 시간 복잡도는 빅오(Big-O)을 사용합니다. 빅오 표기법은 알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계를 표기합니다. 입력 크기가 N이고, 이에 비례하는 시간이 걸린다면 O(N)으로 표기합니다.

    private int search(int[] array, int target){
        for(int i = 0; i<array.length; i++){
            if(array[i] == target){
                return i;
            }
        }

        return -1;
    }

이 코드는 평균적으로 배열 중간쯤에서 원소를 찾게 될 것입니다. 하지만 최아그이 경우에는 모든 원소를 순회한 후 원소를 찾게 됩니다. 즉, 전체 배열을 순회하므로 O(N) 시간 복잡도를 갖게 됩니다.

 

코딩 테스트에서 효율성을 묻는 문제는 문제 제한 사항에 명시되어 있는 조건을 극한으로 맞추는 입력 데이터를 사용해서 코드를 평가합니다. 따라서 입력될 수 있는 최악의 상황을 상정하여 시간 복잡도를 계산할 수 있도록 빅오 표기법을 사용합니다.

 

 

프로그램 실행 시간 1초라는 제한이 있을 때, 어느 정도 시간 복잡도이어야 시간 제한을 만족할 수 있을까요?

• 1초를 만족하는 정해진 시간 복잡도는 문제별로 다릅니다. 문제별로 주어지는 입력 데이터의 종류와 그 개수가 다르기 때문에 정해진 시간 복잡도는 있을 수 없습니다. 하지만 입력 조건에서 명시되어 있는 최악의 경우을 시간 복잡도에 대입해보았을 때 1억이 넘지 않는다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 가능성이 높습니다.
• 예를 들어 문제에서 주어진 조건에 따라 N 값이 최대 1만이라고 가정한다면, 시간 복잡도 O(N logN)을 갖는 코드는 N을 대입했을 때 그 값이 약 13만으로 계산되기 때문에 충분히 효율적인 코드라고 할 수 있습니다. 하지만 작성한 코드가 시간 복잡도 O(N제곱)을 갖는다면 N을 대입했을 때 1억이 되기 때문에 시간 제한을 맞추지 못할 가능성이 매우 큽니다.

💡 자신의 시간 복잡도에 문제의 제한 사항에 표기된 가장 큰 입력을 대입하여 계산했을 때 아무리 커도 1억을 넘기지 않아야 시간 제한에서 안전한 코드입니다.

 

❗️1억은 절대적인 기준은 아닙니다. 시간 복잡도를 나타내는 빅오 표기법은 실행 시간이 어떤 요인으로 결정된다는 것을 나타낼 뿐, 정확한 실행 시간을 나타내는 것이 아닙니다. 따라서 실제 계산한 수치가 1억보다 작더라도 시간 제한에 걸릴 수 있습니다. 하지만 일반적으로 코딩 테스트 문제는 시간 복잡도를 이용하여 이와 같은 방법으로 계산하면 애매하게 1억 근처에서 계산되는 경우는 거의 없을 것입니다. 대부분 1억보다 한참 아래 값으로 계산되거나 풀이가 잘못되어도 1억을 훨씬 넘는 값으로 계산되기 때문에 1억을 일종의 커트라인으로 생각할 수 있습니다.

 

코드를 작성하기 전에 풀이를 먼저 생각하고, 시간 복잡도를 이용하여 효율성이 검증되면 그 이후에 코드를 작성해야 합니다.

시간 복잡도 계산하기

가장 기본이 되는 방법은 반복 횟수를 세어 보는 것입니다. 일반적으로 입력되는 값들을 순회하면서 처리하는 데 반복문이 사용됩니다. 이렇게 사용되는 반복문이 어떤 값에 비례해서 반복하는지 따져 보면 시간 복잡도를 계산할 수 있습니다.

어림짐작해보기

시간 복잡도는 정확한 실행 시간을 계산하는 용도가 아닙니다. 단지 실행 시간이 어떤 요인으로 결정되는지 나타내는 수식일뿐입니다. 따라서 시간 복잡도에서는 곱하거나 더해지는 상수 부분은 나타내지 않습니다.

예를 들어 길이가 N인 배열의 반만 사용하는 알고리즘이 있다고 합시다. 이때 반복 횟수는 N/2일 것입니다. 이는 빅오 표기법으로 O(N/2)로 나타낼 수 있지만 상수 부분을 제외하고 O(N)으로만 표기합니다. N에 비례한다는 것을 나타내기 위해서 입니다. 이와 비슷하게 길이가 N인 배열을 두 번 반복하는 경우 또한 O(2N)이 아니라 O(N)으로 표기합니다. 즉, O(NM)이 되며, 문제 조건에 따라 N뿐만 아니라 M의 최댓값 또한 구하여 시간 복잡도에 대입해야 합니다.

 

또 다른 경우는 길이 N짜리 배열을 순회하고 그 다음에 길이 M짜리 배열을 순회하는 것입니다. 이 경우에는 N번 반복한 M번 반복하므로 O(N+M)으로 표기합니다. 이 때도 N과 M의 최댓값을 구하여 시간 복잡도에 대입해서 효율성을 판단해야 합니다.

시간 복잡도를 줄이는 방법

시간 복잡도 수식에 가장 큰 입력을 대입하여 계산한 결과가 1억 이상이려면 풀이가 충분히 효율적이지 않은 것입니다. 따라서 더욱 효율적인 풀이를 생각해 내어 시간 복잡도를 줄여야 합니다.

 

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

 

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

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

 

💡 문제를 보고 효율적인 풀이를 바로 떠올리기 어렵다면 문제에서 주어진 입력 조건을 이용하여 풀이의 시간 복잡도를 먼저 유추해보는 것도 풀이를 생각해내기에 좋은 힌트가 될 수 있습니다.

 

제한 시간이 1초일 때 유추 가능한 시간 복잡도와 알고리즘