[알고리즘 문제 해결 전략] Ch02. 알고리즘 분석

02 알고리즘 분석 (04 ~ 05)

04 알고리즘 시간 복잡도 분석

4.1 도입

두 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것이다.

하지만 프로그램의 실행 시간은 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합하다.

가장 큰 이유는 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지 수 많은 요소에 의해 바뀔 수 있기 때문이다.

두 번째 이유는 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못하기 때문이다.

알고리즘의 수행 시간을 지배하는 것은 반복문이다. 입력의 크기가 작을 때는 반복외의 다른 부분들이 갖는 비중이 클 수가 있지만, 입력의 크기가 커지면 커질 수록 반복문이 알고리즘의 수행시간을 지배하게 된다.

4.2 선형 시간 알고리즘

입력값 N에 대해 수행시간이 정비례 하는 알고리즘. 시간복잡도는 O(N). 선형 시간에 실행되는 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.

4.3 선형 시간 이하 알고리즘

입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘. 시간복잡도는 O(logN). 입력으로 주어진 자료에 대해 우리가 미리 알고 있는 지식을 활용하면 가능하다. 대표적으로 이진 탐색(binary search)이 있다.

이진 탐색 알고리즘이 하는 일을 정의하면 다음과 같다.

binsearch (A[], x) = 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때 A[i-1] < x < A[i]인 i를 반환한다. 이 때 A[-1] = - 무한대, A[N] = 무한대 로 가정한다.

이 함수는 배열 A[]에서 x를 삽입할 수 있는 위치 중 가장 앞에 있는 것을 반환한다고 생각하면 쉽다. 예를 들어 A = [1,2,4,5,6], x = 3 인 경우 binsearch(A, x) = 2 가 되는 것이다. (A[1] = 2 < x = 3 < A[2] = 4)

4.4 지수 시간 알고리즘

반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들을 다항 시간 알고리즘이라고 부른다. 이 때 시간복잡도는 O(N), O(N^2), O(N^100) 등이 될 수 있다.

N이 하나 증가할 때 마다 걸리는 시간이 배로 증가하는 알고리즘들을 지수 시간(exponential time)에 동작한다고 말한다. 지수 시간은 가장 큰 수행 시간 중 하나로 입력의 크기에 따라 다항 시간과는 비교도 안되게 빠르게 증가한다. 시간복잡도는 O(2^N) 등이 될 수 있다.

4.5 시간 복잡도

시간 복잡도(time complexity)는 가장 널리 사용되고 있는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다.

가장 깊이 중첩된 반복문의 내부에 있는 기본적인 연산들은 더 쪼갤 수 없기 때문에 이것이 시간 복잡도의 대략적인 기준이 된다.

입력의 크기가 수행 시간을 결정하는 유일한 척도는 아니다. 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 미친다.

예를 들어 배열에서 주어진 숫자를 찾아서 그 위치를 반환하는 함수를 아래 코드와 같이 구현했다고 할 때 이 알고리즘에서 반복문이 실행되는 횟수는 찾는 원소의 위치에 따라 달라진다. 운 좋게 처음에 찾을 수도 있고, 맨 마지막에 가야 찾을 수도 있기 때문이다.

int firstIndex(const vector<int>& array, int element) {
    for(int i = 0; i < array.size(); ++i) 
        if(array[i] == element)
            return 1;
    return -1;
}

이와 같이 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 우리는 최선/최악의 경우, 그리고 평균적인 경우에 대한 수행 시간을 각각 따로 계산한다.

시간 복잡도를 간단하게 표현하기 위해 간단하게 빅오 표기법(Big-O Notation)이라는 것을 사용해서 알고리즘의 수행 시간을 표기한다. 빅오 표기법은 간단하게 말하면 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다.

빅오 표기법은 대략적으로 함수의 상한을 나타낸다는 데 그 의미가 있다. 다만 이 방법이 최악의 수행시간과 관련이 있는 것은 아니므로 주의한다.

대표적인 정렬 알고리즘인 선택 정렬과 삽입 정렬을 살펴보자.

void selectionSort(vector<int>& A) {
    for(int i = 0; i < A.size(); ++i) {
        int minIndex = i;
        for(int j = i+1; j < A.size(); ++j)
            if(A[minIndex] > A[j])
                minIndex = j;
        swap(A[i], A[minIndex]);
    }
}
void insertionSort(vector<int>& A) {
    for(int i = 0; i < A.size(); ++i)
        int j = i;
        while(j > 0 && A[j-1] > A[j]) {
            swap(A[j-1], A[j]);
            --j;
        }
    }
}

4.6 수행시간 어림짐작하기

입력의 크기를 시간 복잡도에 대입하여 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다.

다만 이 법칙은 수많은 가정 위에 지어진 법칙이므로 맹신해서는 안 된다. 반복문의 내부가 복잡하거나 메모리 사용 패턴이 복잡할 경우 결과가 달라질 수 있음을 명심하자.

4.7 계산 복잡도 클래스: P, NP, NP-완비

계산 복잡도 이론은 각 문제의 특성을 공부하는 학문이다.

우리는 알고리즘의 문제가 쉽다/어렵다를 판단할 때 해당 문제를 해결할 수 있는 빠른 알고리즘이 있느냐?를 기준으로 삼을 수 있다. 여기서 빠른 알고리즘의 기준은 다항 시간 알고리즘을 기준으로 한다.

빠른 알고리즘이 있으면 계산적으로 쉽고, 빠른 알고리즘이 없으면 계산적으로 어렵다.

계산 복잡도 이론에서는 이렇게 다항 시간 알고리즘이 존재하는 문제들의 집합을 P라고 부른다. 예를 들어 정렬 문제는 다항 시간 알고리즘이 존재하므로 P 문제이다. P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스(complexity class)라고 부른다.

어떤 문제를 다항 시간에 풀 수 있음을 증명하기는 쉽지만, 풀 수 없음을 보이기는 어렵다.

예를 들어 부분 집합 합 문제를 푸는 다항 시간 알고리즘은 아직 아무도 찾아내지 못했는데, 그렇다고 그런 알고리즘이 없다고 증명하는 방법도 아직까지는 없다.

계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법을 사용한다. 환산이란 한 문제를 다른 한 문제로 바꿔서 푸는 기법이다.

예를 들어 B의 입력을 적절히 변형해 A의 입력으로 바꾸는 환산 알고리즘이 존재한다고 가정하면, A를 푸는 가장 빠른 알고리즘을 통해 환산 알고리즘과 결합하여 B를 푸는 알고리즘을 만들 수 있다. 환산 알고리즘의 시간이 거의 없다고 가정하면

A를 푸는 가장 빠른 알고리즘 시간 소요 = B를 푸는 알고리즘 시간 소요 > B를 푸는 가장 빠른 알고리즘 시간 소요

따라서 A가 B보다 더 어려운 문제임을 알 수 있다.

NP 문제는 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미한다.

예를 들어 부분 집합 합 문제는 NP 문제이다. 부분 집합 합 문제의 답이 주어졌을 때 이것이 원래 집합의 부분집합인지, 그리고 원소들의 합이 S인지, 다항 시간에 쉽게 확인할 수 있기 때문이다.

또한 모든 P 문제들은 모두 NP 문제에도 포함된다. 주어진 문제를 푸는 다항 시간 알고리즘이 존재한다면, 이를 사용해 문제를 처음부터 다시 푼 뒤 답을 비교하는 방식으로 답의 정당성을 다항 시간에 확인할 수 있기 때문이다.

NP 문제인지 판단하는 기준은 모든 NP 문제 이상으로 어려운 문제가 SAT(satisfiability problem) 문제인데, 바꿔 말하면 SAT 문제를 다항 시간에 풀 수 있으면, NP 문제들을 전부 다항 시간에 풀 수 있다는 이야기이다. 이런 속성을 가진 문제들의 집합을 NP-난해(NP-Hard) 문제라고 부른다.

NP-난해 문제이면서 NP인 문제들을 NP-완비(NP-Complete) 문제라고 한다.

05. 알고리즘의 정당성 증명

5장에서는 알고리즘의 증명을 위해 사용하는 기법을 다룬다. 알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문이다.

5.2 수학적 귀납법과 반복문 불변식

수학적 귀납법(mathematical induction)은 반복적인 구조를 갖는 명제들을 증명하는데 유용하게 사용하는 증명기법이다. 귀납적 증명은 크게 세 단계로 나뉘어 진다.

• 단계 나누기 : 증명하고 싶은 단계를 여러 단계로 나눈다.
• 첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다.
• 귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

예를 들어 사다리 게임을 예시로 들어보면, 사다리 게임에서 맨 위 선택지와 맨 아래 선택지가 1:1 대응이 되는 것을 귀납법으로 증명해보자.

• 단계 나누기 : 텅 빈 N개의 세로줄에서부터 시작해서 원하는 사다리가 될 때 까지 하나씩 가로 줄을 긋는다.
• 첫 단계 증명 : 텅 빈 N개의 세로줄에는 항상 맨 위 선택지와 맨 아래 선택지가 1:1 대응이 된다. 5.1(a)
• 귀납 증명 : 가로줄을 그어서 두 개의 세로줄을 연결한다. 이 때 두 세로줄의 결과는 뒤바뀐다. 두 세로줄의 결과가 바뀌어도 1:1 대응은 변하지 않고 다음 단계에서 1:1 속성이 유지된다. 5.1(b),(c),(d)는 한 줄씩 그어갈 때 마다 두 세로줄의 결과가 뒤바뀌는 모습을 보여준다.

귀납법을 이용해 알고리즘의 정당성을 증명할 때는 반복문 불변식(loop invariant)을 사용한다. 반복문 불변식이란 반복문의 내용이 한 번 실행될 때 마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다. 불변식을 이용하면 반복문의 정당성을 다음과 같이 증명할 수 있다.

1. 반복문 진입시에 불변식이 성립함을 보인다.
2. 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.
3. 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

예를 들어 이진탐색의 구현식을 보자.

// 필수조건: A는 오름차순으로 정렬되어 있다.
// 결과: A[i-1] < x <= A[i]인 i를 반환한다.
// 이 때 A[-1] = 음의 무한대, A[n] = 양의 무한대 라고 가정한다.
int binsearch(const vector<int>& A, int x) {
    int n = A.size();
    int lo = -1, hi = n;
    // 반복문 불변식 1: lo < hi
    // 반복문 불변식 2: A[lo] < x <= A[hi]
    // (*) 불변식은 여기서 성립해야 한다
    while(lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if(A[mid] < x)
            lo = mid;
        else
            hi = mid;
        // (**) 불변식은 여기서도 성립해야 한다.
    }
    return hi;

이진 탐색 내부의 while문은 두 개의 불변식을 유지한다. 첫 번째는 lo < hi 이고, 두 번째는 A[lo] < x <= A[hi] 이다. 이 불변식이 while문이 완전히 종료되고 함수의 마지막 줄에 올 때까지 성립했다고 가정하면 두 가지 사실을 알 수 있다.

1. lo + 1 = hi: while문 종료했으니 lo + 1 >= hi 인데, 불변식에 의하면 lo < hi 이니 lo + 1 = hi 일 수 밖에 없다.
2. A[lo] < x <= A[hi]: 애초에 불변식이 성립한다고 가정했으니 이것은 당연히 성립한다.

5.3 귀류법

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못되었음을 찾아내는 증명 기법을 귀류법이라 한다. 이 책에서 귀류법은 대개 어떤 선택이 항상 최선임을 증명하고자 할 때 많이 이용된다. 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 사실은 그런 일이 있을 수 없음을 보이면 우리가 최선의 답을 선택했음을 보일 수 있기 때문이다.

5.4 다른 기술들

비둘기집의 원리

10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기 집이 반드시 하나는 있게 마련이다.

구성적 증명

이 장에서 다룬 다른 기법들과는 다른 관점을 취하는 증명 방식으 구성적 증명(constructive proof)이 있다. 구성적 증명은 흔히 우리가 원하는 어떤 답이 존재한다는 사실을 증명하기 위해 사용된다. 답이 존재한다는 사실을 논증하는 것이 우리가 지금까지 이 장에서 다룬 방식이라면, 구성적 증명은 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시하는 증명이다.

예를 들어 하늘을 나는 교통수단을 만들 수 있다는 주장을 증명한다고 하자. 비구성적 증명(nonconstructive proof)은 양력의 법칙에서부터 시작해 지구의 공기 밀도, 사용할 수 있는 재료들의 강도와 탄성들을 하나하나 열거해가며 이러한 가정 하에 교통 수단이 하늘을 날 수 있음을 보이려 할 것이다. 반대로 구성적 증명이 하는 일은 비행기를 만들어서 보여주거나, 비행기를 만드는 법이 적힌 설명서를 건내주는 것이다.

'답이 존재하는가'에 대한 대답으로 '이렇게 만들면 된다'라고 하는 것이 구성적 증명이기 때문에, 구성적 증명의 내용은 사실상 알고리즘인 경우가 많다.