02 알고리즘 분석

개관

어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 알고리즘이라 한다.

 

알고리즘은 알고리즘이 사용하는 시간과 공간으로 평가할 수 있다.

 

 

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

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

 

보통 빅오 표기법을 이용해 표현한다.

 

주먹구구 수행시간 짐작

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

 

주먹구구는 주먹구구이다.

실제 내부 반복문은 더 높을 수 있다. 

파일 입출력, 실수 연산이 많다면 더 오래걸린다.

메모리 사용 패턴이 복잡한경우 더 빨라질 수 있다. 캐시 사용.

언어와 컴파일러 차이로 속도가 달라진다.

하드웨어 차이.

 

실제 적용

1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제.

예를 들어 [-7, 4, -3, 6, 3, -8, 3, 4]에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3]으로 그 합은 10이다.

 

첫번째, 주어진 배열의 모든 부분 구간을 순회하면서 그 합을 계산하는 알고리즘.

 

가장 무식한 방법

//numeric_limits는 해당 자료형의 표현 한계치를 구할 때 사용한다.
//아래 경우에는 int의 최소 표현 값을 반환한다.
const int MIN = numeric_limits<int>::min();

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도O(N³)
//비효율적인 최대합 구하는 알고리즘
//모든 경우의 수를 다 계산해서 구한다.
int inefficientMaxSum(const vector<int>& A){
    int N = A.size(), ret = MIN;
    for(int i=0; i<N;++i)
        for(int j=i; j<N; ++j)
        {
            //구간 A[i..j]의 합을 구한다.
            int sum = 0;
            for(int k=i; k<=j; ++k)
                sum += A[k];
            ret = max(ret, sum);
        }
    
    return ret;
}

 

sum을 구할 때, 처음부터 더해주는 부분이 중복된다.

sum을 구할 때 처음부터 다시 구하지 않도록 수정한다.

 

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간복잡도:O(N²)
int betterMaxSum(const vector<int>& A)
{
    int  = A.size(), ret = MIN;
    for(int i=0; i<N; ++i)
    {
        int sum = 0;
        for(int j = i; j <N; ++j)
        {
            sum += A[j];
            ret = max(ret, sum);
        }
    }
    return ret;
}

 순차적으로 더 하면서 for문이 하나 사라졌다.

 

분할 정복 기법을 이용하면 더욱 빠른 시간에 동작하는 알고리즘을 설계할 수 있다.

입력받은 배열을 우선 절반으로 잘라 왼쪽 배열과 오른쪽 배열로 나눈다.

정답은 왼쪽 배열에 있을 수도, 오른쪽에 있을 수도, 두배열 사이에 걸쳐있을 수도 있다.

 

각 경우의 답을 재귀함수와 탐욕법을 이용해서 계산하면, 분할 정복 알고리즘이 된다.

//A[lo..hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도 O(N*logN)
int fastMaxSum(const vector<int> &A, int lo, int hi)
{
    //기저 사례: 구간의 길이가 1인 경우. 하나짜리.
    if(lo == hi) return A[lo];
    
    //배열을 A[lo..mid], A[mid+1..hi]로 나눈다.
    int mid = (lo+hi)/2;
    
    //두 부분에 걸쳐있는 경우와 하나에만 속한 경우를 나눠 계산
    
    //두 부분에 모두 걸쳐있는 최대 합 구간을 찾는다.
    //이 구간은 A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다.
    //중앙은 붙어있어야 하므로 양쪽으로 늘어나면서 최대 값을 구한다.
    
    //A[i..mid] 형태를 갖는 최대 구간을 찾는다.
    int left = MIN, right = MIN, sum=0;
    for(int i = mid; i>=lo; --i)
    {
        sum += A[i];
        left = max(left, sum);
    }
    
    //A[mid+1..j] 형태를 갖는 최대 구간을 찾는다.
    sum = 0;
    for(int j=mid+1; j<=hi; ++j)
    {
        sum += A[j];
        right = max(right, sum);
    }
    
    //최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
    int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid+1, hi));
    
    //두 경우 중 최대 치를 반환한다.
    return max(left + right, single);
}

 

이 문제를 선형시간에 푸는 방법은 동적계획법 사용이다.

A[i]를 오른쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수  maxAt(i)를 정의해보자.

A[i]에서 끝나는 최대 합 부분 구간은 항상 A[i] 하나만으로 구성되어 있거나, A[i-1]을 오른쪽 끝으로 갖는 최대 합 부분 구간의 오른쪽에 A[i]를 붙인 형태로 구성되어 있습니다.

A[i]를 오른쪽 끝으로 가져야 하기에.. A[i]혼자거나, A[i] + maxAt(i-1)이다.

 

따라서 점화식으로 표현하면 다음과 같다.

maxAt(i) = max(A[i], maxAt(i-1) + A[i]) = max(0, maxAt(i-1)) + A[i]

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도:O(N)
int fastestMaxSum(const vector<int>& A)
{
    int N = A.size(), ret = MIN, psum = 0;
    for(int i = 0; i<N; ++i)
    {
        //이전 까지 계산한 값에 현재 요소를 더한 것과 현재 요소를 비교하여 큰 것을 psum이 할당.
        //이전까지 계산한 값+현재 요소가 현재 요소보다 작다면 잘리는 효과.
        psum = max(psum, 0) + A[i];
        //기존 계산 값과, 새로 계산한 값 중 큰 것을 ret에 할당.
        ret = max(psum, ret);
    }
    return ret;
}

 

 

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

계산 복잡도 이론에서는 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 한다.

다항시간 알고리즘이 존재하지 않으면 NP.

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

 

임의의 NP문제를 다항식 시간 내에 'A' 문제로 환원(reduction 또는 transformation)할 수 있는 경우, 이 'A'문제를 'NP-난해(NP-hard) 문제'라고 부른다. NP-난해 문제 중에는 NP 문제가 아닌 것도 있다.

 

NP 문제들 중에서 NP-난해 문제인 것을 가리켜 'NP-완전(NP-complete) 문제'라고 부른다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게 되는 셈이므로 NP 문제들 중에서는 가장 핵심이 되는 문제들인 셈이다.

 

 

05 알고리즘의 정당성 증명

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

수학적 귀납볍은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법입니다.

 

단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다.

첫단계 증명: 그 중 첫 단계에서 증명하고 싶은 내용이 성립함을 보입니다.

귀납 증명: 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

 

반복문 불변식

귀납법은 알고리즘의 정당성을 증명할 때 유용하게 사용되는 기법이다.

반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건이다.

 

1.반복문 진입시에 불변식이 성립함을 보인다.

2.반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.

3. 반복문 종료 시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

 

//(*)불변식은 여기에서 성립해야 한다.
while(조건){
    ..
    //(**)불변식은 여기에서도 성립해야한다.
}

 

반복문 안에서 변하면 안되는 조건을 어기지 않는지 확인하는 과정이다.

 

단정문을 통해서 반복문 불변식을 강제할 수 있다.

 

 

비둘기집의 원리

비둘기집 원리는 간단하게 말해서 n+1개의 물건을 n개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다.