[Algorithm Strategies] 2-4. 알고리즘 시간 복잡도 분석

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.

📕 목차
1. Overall
2. 선형 시간 알고리즘
3. 선형 이하 시간 알고리즘
4. 지수 시간 알고리즘
5. 시간 복잡도
6. 수행 시간 어림짐작하기
7. 계산 복잡도 클래스: P, NP, NP-완비

1. Overall

• 알고리즘 평가 기준
• 프로그램 실행 시간 != 알고리즘 속도
• 반복문이 지배한다

📌 알고리즘 평가 기준

시간
- 알고리즘 수행 시간이 작을 수록 더 빠르게 동작하는 것을 의미
- 시간 안에 실행되지 않는다면 답안의 정확도와 상관없이 오답
- 알고리즘 수행 속도와 특성을 분석하는 능력 필요
공간
- 적은 용량의 메모리를 사용
- 알고리즘이 아무리 빨라도, 너무 많은 메모리 공간을 요구한다면 오답

📌 프로그램 실행 시간 != 알고리즘 속도

같은 input과 output에 대한 각각의 알고리즘을 구현하고 수행 시간을 비교하는 것은 정확하지 않다.
프로그램 수행 시간은 알고리즘 외에 외부 요소에 의한 영향을 많이 받는다.
- 심지어 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 크게 달라질 수 있다.
- C++에서는 vector나 string보다는 참조형(reference)으로 넘겨주는 것이 좋다.

📌 반복문이 지배한다

자전거는 확실히 자동차를 운전할 때에 비해 부수적인 작업이 적다.

그냥 자물쇠를 풀고, 안장에 올라 탄 뒤, 페달을 밟으면 출발하므로.

하지만 달리기 시작하면 자전거는 자동차의 속도를 따라잡을 수 없다.

이렇게 한 가지 항목이 전체의 대소를 좌지우지 하는 것을 지배한다(dominate)고 표현한다.

그리고 알고리즘의 수행 시간은 반복문이 지배한다.

대개 알고리즘 수행 시간을 반복문이 수행되는 횟수로 측정한다.
반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현 한다.

// 코드 4.1 주어진 배열에서 가장 많이 등장하는 숫자 반환

// 주어진 배열 A에서 가장 많이 등장하는 숫자 반환
// 만약 두 가지 이상 있을 경우 아무것이나 반환
int majority1(const vector<int> &A) {
    int n = A.size();
    int majority = -1, majorityCount = 0;
    for (int i = 0; i < n; i++) {
        // A에 등장하는 A[i]의 수를 센다
        int V = A[i], count = 0;
        for (int j = 0; j < n; j++) {
            if (A[j] == V) count++;
        }
        if (count > majorityCount) {
            majorityCount = count;
            majority = V;
        }
    }
    return majority;
}

위 알고리즘은 N번 수행되는 반복문이 2개 겹쳐져 있으므로, 수행 시간은 $N^{2}$ 이다.

// 코드 4.2 주어진 배열에서 가장 많이 등장하는 숫자 반환 2

int majority2(const vector<int> &A) {
    int N = A.size();
    vector<int> count(101, 0);

    for (int i = 0; i < N; ++i)
        count[A[i]]++;

    // 지금까지 확인한 숫자 중 빈도수가 제일 큰 것을 majority에 저장한다.
    int majority = 0;
    for (int i = 1; i <= 100; i++)
        if (count[i] > count[majority])
            majority = i;

    return majority;
}

같은 문제를 다른 방식으로 구현한 위 알고리즘의 수행 시간은 $N + 100$ 이다.

하지만, N이 커질 수록 100은 상수 취급할 수 있기 때문에 수행 시간을 N으로 쓴다.

2. 선형 시간 알고리즘

• 다이어트 현황 파악: 이동 평균 계산하기
• 선형 시간으로 바꾸기

📌 다이어트 현황 파악: 이동 평균 계산하기

이동 평균(moving average) : 시간(t)에 따른 변화량을 관찰할 때 유용한 통계적 기준
시간에 따른 관찰 값에 대한 M-이동 평균은 마지막 M개의 관찰 값의 평균으로 정의

// 코드 4.3 이동 평균

// 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다.
vector<double> movingAverage1(const vector<double> &A, int M) {
    vector<double> ret;
    int N = A.size();
    
    for (int i = M - 1; i < N; ++i) {
        // A[i]까지의 이동 평균평균을 구한다.
        double partialSum = 0;
        for (int j = 0; j < M; ++j)
            partialSum += A[i - j];
        ret.push_back(partialSum / M);
    }
    return ret;
}

N개의 측정치에서 매달 M달 간의 이동 평균 계산 프로그램
전체 반복 횟수 : $M * (N - M + 1) = N * M - M^{2} + M$
- j ⇒ M
- i ⇒ N - M + 1 번

📌 선형 시간으로 바꾸기

N=300,000과 M=100,000 만 되어도 반복 횟수는 200억을 넘는다.
반복을 줄이기 위해서 중복 계산을 제거하는 방법이 있다.
1. 0~(M-1)일까지의 이동 평균을 구한다.
2. 1~M일을 구하기 위해서, ((1)번 이동 평균) - (0일 값) + (M일 값)로 구할 수 있다.

// 길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다
vector<double> movingAverage2(const vector<double> &A, int M) {
    vector<double> ret;
    int N = A.size();
    double partialSum = 0;

    for (int i = 0; i < M - 1; ++i)
        partialSum += A[i];
    for (int i = M - 1; i < N; ++i) {
        partialSum += A[i];
        ret.push_back(partialSum / M);
        partialSum -= A[i - M + 1];
    }
    return ret;
}

중첩 반복문을 두 개의 반복으로 풂으로써 N의 수행 시간으로 줄였다.

💡 일반적으로 우리가 찾을 수 있는 가장 좋은 알고리즘이 선형 시간(linear time) 알고리즘이다.

3. 선형 이하 시간 알고리즘

• 선형 이하 시간(sublinear time)
• 이진 탐색(binary search)

📌 선형 이하 시간(sublinear time)

10만 장의 사진에서 성형한 시점을 찾고 싶다면, 몇 장의 사진을 확인해야 할까?
1. 전체 사진을 시간 순으로 정렬(sort)한다.
2. 가운데 있는 5만 번째 사진을 확인한다.
3. (성형하지 않은 상태라면) 남은 5만 장 중의 가운데인 7만 5천 번째를 확인한다.
4. 이 과정을 반복한다.
$l o g_{2} N$ 의 시간 복잡도를 가진다.
선형 이하 시간(sublinear time) : 입력의 크기에 비해 수행 시간이 느리게 증가하는 알고리즘

📌 이진 탐색(binary search)

위에서 사용한 이진 탐색 알고리즘은 대표적은 선형 이하 시간 알고리즘 중 하나다.

// 반복문으로 구현
int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

// 재귀 함수로 구현
int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}

이진 탐색(binary search)
- binsearch(A[], x)
- 오름차순으로 정렬된 배열 A[], 찾고 싶은 값 x → A[i-1] < x ≤ A[i]인 i 반환
- 이때 A[-1] = -∞, A[N] = ∞로 가정
배열의 중간의 임의의 값을 선택하여 x와 비교 후, x가 중간 값보다 작으면 좌측, 크면 우측을 대상으로 다시 탐색한다.

4. 지수 시간 알고리즘

• 다항 시간 알고리즘
• 모든 답 후보를 평가하기 : 지수 시간 알고리즘
• 소인수 분해의 수행 시간

📌 다항 시간 알고리즘

다항식 : 변수 N, N^2, 그 외 N의 거듭제곱들의 선형 결합으로 이루어진 식
다항 시간 알고리즘 : 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘
다항 시간에도 크기의 차이는 많지만, 이보다 오랜 시간이 걸리는 알고리즘들이 있다.

📌 모든 답 후보를 평가하기 : 지수 시간 알고리즘

N명의 친구를 집들이로 초대하여, 할 줄 아는 M가지 음식 중 대접할 음식을 골라보자.

각각의 친구들은 알러지 때문에 못먹는 음식들이 있어서 잘 골라야 한다.

각 친구들이 먹을 수 있는 음식이 최소한 하나씩 있으려면, 최소 몇 가지 음식을 해야 할까?

// 코드 4.5 음식 메뉴 정하기

const int INF = 987654321;

// 이 메뉴로 모두가 식사할 수 있는지 여부를 반환한다.
bool canEverybodyEat(const vector<int> &menu) {
    // 각 친구들이 주어진 메뉴를 먹을 수 있는지 여부를 담은 배열을 만든다.
    vector<bool> edible(menu.size(), false);
    for (int i = 0; i < edible.size(); ++i)
        for (int j = 0; j < menu.size(); ++j)
            if (menu[j] <= i + 1)
                edible[i] = !edible[i - menu[j]];

    return edible.back();
}

int M;
// food 번째 음식을 만들 지 여부를 결정
int selectMenu(vector<int> &menu, int food) {
    // 기저 사례: 모든 음식에 대해 만들지 여부를 결정했을 때
    if (food == menu.size()) {
        if (canEverybodyEat(menu))
            return menu.size();
        return INF; // 아무것도 못 먹는 사람이 있는 경우
    }

    // 이 음식을 만들지 않을 경우
    int ret = selectMenu(menu, food + 1);
    // 이 음식을 만드는 경우의 답을 계산해서 더 작은 것을 취한다.
    menu.push_back(food);
    ret = min(ret, selectMenu(menu, food + 1));
    menu.pop_back();
    return ret;
}

재귀 호출을 통하여 모든 경우를 탐색한 알고리즘
- M가지 음식마다 "만든다", "안 만든다"라는 선택지가 있으므로 2^M가지 답 생성
- 알고리즘 수행 시간 = 2^M * canEverybodyEat() (약, N*M*2^(M))
지수 시간(exponential time) 알고리즘은 가장 큰 수행 시간 중 하나를 갖는다.
전산학에는 지수 시간보다 빠른 알고리즘을 찾지 못한 문제들이 널리고 널렸다.
이를 좀더 효율적으로 해결하는 방법들이 있긴 하지만, 지수 시간을 다항 시간으로 바꿔주지는 못한다.

📌 소인수 분해의 수행 시간

입력 갯수가 아닌, 주어지는 숫자의 크기에 따라 수행 시간이 달라지기도 한다.

// 코드 4.6 가장 간단한 형태의 소인수 분해 알고리즘

// 자연수 n의 소인수 분해 결과를 담은 정수 배열을 반환한다
vector<int> factor(int n) {
    if (n==1) return vector<int>(1, 1); // n=1인 경우 예외 처리
    vector<int> ret;
    // 가장 작은 소인수부터 시작해 한 번에 하나씩 추가한다
    for (int div = 2; n > 1; ++div) {
        while (n % div == 0) {
            n /= div;
            ret.push_back(div);
        }
    }
    return ret;
}

N이 소수일 때 factor()의 반복 횟수는 N-1 (일반적으로 선형 시간 알고리즘)
이전의 알고리즘들은 입력값으로 필요 메모리 공간이 파악 가능했으나, 여기선 N의 값에 따라 특정 범위를 가정할 수 없다. (그저 입력 값이 클 수록, 필요한 메모리 공간(ret)이 증가한다.)
입력이 차지하는 비트 수에 따라 수행 시간이 증가한다고 가정
- 비트 수 하나 증가 → 표현할 수 있는 범위와 알고리즘 최대 수행 시간 두 배로 증가

입력의 크기 = 입력이 차지하는 비트수로 가정하면, 코드 4.6은 입력의 크기에 대해 지수 시간이 걸린다고 말할 수 있다.

5. 시간 복잡도

• 시간 복잡도(time complexity)
• 입력 종류에 따른 수행 시간 변화
• 점근적 시간 표기: O 표기
• O 표기법 의미
• 시간 복잡도 분석 연습
• 시간 복잡도의 분할 상환 분석

📌 시간 복잡도(time complexity)

알고리즘 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
1. 기본적인 연산
  - 두 부호 있는 32 bit 정수 사칙연산
  - 두 실수형 변수 대소 비교
  - 한 병수에 다른 변수 대입
2. 기본적인 연산이 아닌 것
  - 정수 배열 정렬
  - 두 문자열 비교
  - 입력된 수 소인수 분해
시간 복잡도가 높으면, 입력의 크기에 대해 수행 시간이 더 빠르게 증가한다.
- 입력이 충분히 작다면, 시간 복잡도가 높은 알고리즘이 더 빠른 경우도 있다.

📌 입력 종류에 따른 수행 시간 변화

// array[i] = element인 첫 i를 반환. 없으면 -1
int firstIndex(const vector<int> &array, int element) {
    for (int i = 0; i < array.size(); ++i)
        if (array[i] == element)
            return i;
    return -1;
}

운이 좋으면 처음에 찾고, 아니라면 마지막까지 탐색해야 한다.
최선/최악, 평균 수행 시간을 따로 계산할 필요가 있다.
- 최선의 수행 시간: 원소가 배열의 맨 앞에 있는 경우에 수행 횟수 1
- 최악의 수행 시간: 원고가 배열의 맨 끝에 있는 경우에 수행 횟수 N
- 평균적인 수행 시간: N/2
일반적으로 최악의 수행 시간(≅ 수행 시간 기대치)을 많이 사용한다.

📌 점근적 시간 표기: O 표기

문제	반복문 수행 횟수	O 표기
이동 평균 구하기	N	O(N)
이진 탐색	lgN	O(lgN)
집합 덮개	NM2^(M)	O(NM2^(M))

전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고, 반복문의 반복 수만 고려한다. (지배 시간)
빅 오 표기법(Big-O Notation) : 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버림 (O: order)
- $f (N) = \frac{\sqrt{5}}{3} N^{2} - N l g \frac{N}{2} + 16 N - 7$ ⇒ $O (N^{2})$
- $2^{N} M = O (2^{N} M)$
- $\frac{1}{64} N^{2} M + 64 N M = O (N^{2} M)$
- $N^{2} M + N l g M + N M^{2} = O (N^{2} M + N M^{2})$ (어느 한쪽이 지배적인지 모르므로 둘 다 포함)
- $42 = O (1)$ (상수 시간(constant-time) 알고리즘)

📌 O 표기법 의미

💡 빅 오 표기법은 대략적으로 함수의 상한을 나타낸다.

f(N) = O(g(N))은 다음과 같은 의미를 가진다.

아주 큰 $N_{0}$ 와 C( $N_{0}$ , C>0)를 적절히 선택하면 $N_{0} <= N$ 인 모든 N에 대해 |f(N)| <= C*|g(N)|이 참이 되도록 할 수 있다.

$N^{2} + 100 * N + 1 = O (N^{2})$ 에서 N이 매우 커지면, 두 항은 큰 차이가 없게 된다.
이때, 적절한 상수 C를 택해 $N^{2}$ 에 곱해주면 $N^{2}$ 이 더 크다고 할 수 있다.

빅 오 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법이다.

이는 최악의 수행 시간과 관련이 있지는 않다.

✒️ 퀵 정렬(Quick sort)

퀵 정렬 최악의 시간 복잡도는 $O (N^{2})$ 이다.
그러나 평균 시간 복잡도는 O(NlgN) 정도에 불과하다.

📌 시간 복잡도 분석 연습

// 코드 4.8 선택 정렬과 삽입 정렬

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[j] < A[minIndex])
                minIndex = j;
        swap(A[i], A[minIndex]);
    }
}

void insertionSort(vector<int> &A) {
    for (int i = 0; i < A.size(); ++i) {
        // A[0..i-1]에 A[i]를 끼워넣는다.
        int j = i;
        while (j > 0 && A[j - 1] > A[j]) {
            swap(A[j - 1], A[j]);
            j--;
        }
    }
}

선택 정렬의 경우, 시간 복잡도를 다음처럼 계산할 수 있다.

$(N - 1) + (N - 2) + \dots + 1 = \sum_{N - 1}^{i = 1} = \frac{(N - 1) \cdot N}{2} = \frac{1}{2} N^{2} - \frac{1}{2} N = O (N^{2})$

더 간단하게는 최대 O(N)번 실행되는 for문이 중첩되어 있으므로 $O (N^{2})$ 라고 봐도 무방하다.

삽입 정렬의 경우

최선의 경우 : 이미 정렬된 배열이라면 while은 곧바로 종료되므로 for문에 의해 결정 ⇒ O(N)
최악의 경우 : 역순으로 정렬된 배열이면 매번 while이 최대로 동작 ⇒ O(N^2)

즉, 삽입 정렬은 입력의 종류에 따라 시간 복잡도가 크게 바뀐다.

그럼에도 흔히 사용하는 O(N^2) 정렬 중 가장 빠른 알고리즘으로 알려져 있다.

📌 시간 복잡도의 분할 상환 분석

언제나 반복문의 개수로 시간 복잡도를 정하지는 않는다.
분할 상황 분석(amorized analysis)는 보다 정확한 분석 방법을 사용한다.
- N개의 task가 각자 걸리는 시간은 다르지만, 전체 시간은 일정한 경우 사용 가능
- (각 task에 걸리는 평균 시간) = (전체 시간) / (task 개수)
동적 배열을 다루거나, 미나스 아노르 해법 등이 예시

6. 수행 시간 어림짐작하기

• 주먹구구 법칙
• 주먹구구 법칙은 주먹구구일 뿐
• 실제 적용
• 수행 시간 확인

📌 주먹구구 법칙

💡 반복문 횟수 1억번 ≅ 1s

프로그램 작성 전에 알고리즘 시간 복잡도로 수행 시간을 어림짐작할 수 있어야 한다.
그러나, 입력의 크기 외의 요소들이 수행 속도를 열 배 정도는 쉽게 바꿀 수 있다.
위 법칙은 수행 횟수가 기준의 10% 이하인 경우와 기준의 10배를 넘는 경우에만 사용하는 것이 좋다.

📌 주먹구구 법칙은 주먹구구일 뿐

시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
- Big-O notation은 어디까지나 적당한 예측값
반복문 내부가 복잡한 경우
- 계산이 복잡할 수록 오차 범위가 커진다.
- 예측을 하는 것도 쉽지 않다. (반복문 내부는 단순할 수록 좋다.)
메모리 사용 패턴이 복잡한 경우
- CPU는 메모리의 자료를 직접 접근하는 대신 Cache라는 작고 빠른 메모리로 옮겨온 뒤 처리한다.
- Cache로 데이터를 가져올 때는 인접한 자료들을 함께 가져온다.
- 따라서, 메모리 상 데이터의 밀집도가 높을 수록 프로그램 실제 수행 속도에 큰 영향을 준다.
언어와 컴파일러
구형 컴퓨터

📌 실제 적용

1차원 배열에서 연속된 부분 구간 중, 그 합이 최대인 구간을 구해보자.

1️⃣ 배열 모든 부분 구간 순회

// 코드 4.9 최대 연속 부분 구간 합 문제를 푸는 무식한 알고리즘들

const int MIN = numeric_limits<int>::min();

// A[]의 연속된 부분 구간의 최대 합을 구한다
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;
}

// A[]의 연속된 부분 구간의 최대 합을 구한다
int betterMaxSum(const vector<int> &A) {
    int N = 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;
}

위는 $O (N^{3})$ , 아래는 $O (N^{2})$ 의 시간 복잡도를 가진다.
inefficientMaxSum()은 무식하게 모든 경우를 탐색하고, betterMaxSum()은 중복 구간을 풀어 한 단계 개선했다.

2️⃣ 분할 정복 기법 적용

// 코드 4.10 최대 연속 부분 구간 합 문제를 푸는 분할 정복 알고리즘

const int MIN = numeric_limits<int>::min();

// A[lo..hi]의 연속된 부분 구간의 최대합을 구한다. (분할 정복)
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] 형태를 갖는 구간의 합으로 이루어진다
    int left = MIN, right = MIN, sum = 0;
    for (int i = mid; i >= lo; --i) {
        sum += A[i];
        left = max(left, sum);
    }
    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);
}

재귀 호출과 탐욕법을 이용한 분할 정복 알고리즘 방법
시간 복잡도 : $O (N l g N)$

3️⃣ 동적 계획법 적용

코드 4.11 최대 연속 부분 구간 합 문제를 푸는 동적 계획법 알고리즘

const int MIN = numeric_limits<int>::min();

// A[]]의 연속된 부분 구간의 최대 합을 구한다
int fastestMaxSum(const vector<int> &A) {
    int N = A.size(), ret = MIN, psum = 0;
    for (int i = 0; i < N; ++i) {
        psum = max(psum, 0) + A[i];
        ret = max(psum, ret);
    }
    return ret;
}

동적 계획법을 이용한 방법
maxAt(i) = max(0, maxAt(i-1)) + A[i] (단, maxAt(i)는 A[i]를 오른쪽 끝으로 갖는 구간의 최대 합)\
시간 복잡도 : O(N)

📌 수행 시간 확인

N = 1,000
- $O (N^{3})$ : 10억이 나오므로 주의하는 것이 좋다.
- 다른 알고리즘들은 무사히 통과할 것이다.
N = 10,000
- $O (N^{3})$ : Time out
- $O (N^{2})$ : 1억 정도이므로 주의하는 것이 좋다.
- 다른 두 알고리즘은 무사히 통과할 것이다.
N = 100,000
- $O (N^{2})$ : Time out
- 다른 두 알고리즘은 무사히 통과할 것이다.

테스트 환경 마다 다르겠지만, 책의 저자의 PC 환경에서는 모든 알고리즘들이 예상한 대로 작동했다.

또한, 주먹구구 법칙으로 예측한 것보다 느리게 동작한 프로그램은 없었다.

1억이라는 기준은 가능한 한 보수적으로 정한 것이므로 바람직한 현상이다.

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

• 문제의 특성 공부하기
• 난이도의 함정
• NP 문제, NP 난해 문제
• P = NP?

📌 문제의 특성 공부하기

시간 복잡도는 알고리즘의 특성이지 문제의 특성이 아니다.
계산 복잡도 이론은 각 문제의 특성을 공부하는 학문
- 정렬 문제: 주어진 N개의 정수를 정렬한 결과는 무엇인가
- 부분 집합 합(subset sum) 문제: N개의 수가 있을 때, 이 중 몇 개를 골라내서 합이 S가 되도록 할 수 있는가?
구현이 아무리 어려워도 빠른 알고리즘이 있다면 그 문제는 '쉽다'고 표현
- 빠른 알고리즘이란 다항 시간, 혹은 그보다 빠른 알고리즘만을 말한다.
P(polynomial) 문제 : 다항 시간 알고리즘이 존재하는 문제들의 집합
- ex. 정렬
NP(non-polynomial) 문제 : 답이 주어졌을 때, 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제
- ex. 부분 집합 합, 모든 P문제는 NP 문제에 포함

📌 난이도의 함정

💡 어떤 문제를 다항 시간에 풀 수 있음을 증명하는 것보다, 풀수 없음을 보이는 것이 더 어렵다

가능하다는 것은 하나의 사례를 들고오면 되지만, 불가능하다는 것은 모든 경우를 탐색해야 한다.
그러나 부분 집합 합 문제를 푸는 다항 시간 알고리즘을 아무도 못 찾아냈다는 것이, 존재하지 않음을 증명하지는 못한다.
따라서 다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 구분하기 힘들다.
계산 복잡도에서 말하는 '어려운 문제'란 다음과 같다.
- 정말 어려운 문제를 골라서 이것을 어려운 문제의 기준으로 삼는다.
- 기준 이상으로 어려운 문제들만을 어렵다고 부른다.

계산 복잡도 이론에서는 두 문제 난이도 비교를 위해 환산(reduction) 기법을 사용한다.

문제 A를 푸는 가장 빠른 알고리즘이 문제 B를 푸는 가장 빠른 알고리즘보다 느리다면, A가 B 이상으로 어렵다고 말할 수 있다.

📌 NP 문제, NP 난해 문제

SAT 문제(sattisfiability problem)
- 어려운 문제의 기준
- N개의 boolean 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제
  - boolean a, b, c는 다음 논리식을 만족한다.
  - ((a || b || !c) && (!c || !a) && ((!a && b) || (b && !c))) && (!b || (!a && !c))
- SAT 문제는 모든 NP 문제 이상으로 어렵다.
- SAT를 다항 시간에 풀 수 있다면, NP 문제들은 전부 다항 시간에 풀 수 있어야 한다. (by Cook-Levin Theorem)
  - 이를 NP-Hard 문제라고 한다.
  - NP-Hard 이면서 NP인 문제를 NP-Complete 문제라고 한다.

📌 P = NP?

P=NP 문제는 7대 수학 난제 중 하나다. 즉, 아무도 해결하지 못한 문제란 얘기다.

어려운 문제를 풀려고 이리저리 고민을 하다가, 어떤 변환을 거치면 이 문제를 이용해 NP-난해나 NP-완비 문제 중 하나를 풀 수 있음을 깨달았다면, 이 문제를 다항 시간에 푸는 것은 인류 역사상 아무도 못한 일이라는 사실을 알 수 있다.

그럴 때는 모델링을 달리 하거나, 근사해를 찾는 방향으로 길을 바꿔야 한다.

저작자표시 비영리 (새창열림)

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[Algorithm Strategies] 2-4. 알고리즘 시간 복잡도 분석

1. Overall

2. 선형 시간 알고리즘

3. 선형 이하 시간 알고리즘

4. 지수 시간 알고리즘

5. 시간 복잡도

6. 수행 시간 어림짐작하기

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

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역