구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.
📕 목차
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억을 넘는다.
- 반복을 줄이기 위해서 중복 계산을 제거하는 방법이 있다.
- 0~(M-1)일까지의 이동 평균을 구한다.
- 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만 장의 사진에서 성형한 시점을 찾고 싶다면, 몇 장의 사진을 확인해야 할까?
- 전체 사진을 시간 순으로 정렬(sort)한다.
- 가운데 있는 5만 번째 사진을 확인한다.
- (성형하지 않은 상태라면) 남은 5만 장 중의 가운데인 7만 5천 번째를 확인한다.
- 이 과정을 반복한다.
- \( log_{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)
- 알고리즘 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
- 기본적인 연산
- 두 부호 있는 32 bit 정수 사칙연산
- 두 실수형 변수 대소 비교
- 한 병수에 다른 변수 대입
- 기본적인 연산이 아닌 것
- 정수 배열 정렬
- 두 문자열 비교
- 입력된 수 소인수 분해
- 기본적인 연산
- 시간 복잡도가 높으면, 입력의 크기에 대해 수행 시간이 더 빠르게 증가한다.
- 입력이 충분히 작다면, 시간 복잡도가 높은 알고리즘이 더 빠른 경우도 있다.
📌 입력 종류에 따른 수행 시간 변화
// 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) |
| 집합 덮개 | N*M*2^(M) | O(N*M*2^(M)) |
- 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고, 반복문의 반복 수만 고려한다. (지배 시간)
- 빅 오 표기법(Big-O Notation) : 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버림 (O: order)
- \( f(N) = \frac{\sqrt{5}}{3}N^{2} - Nlg\frac{N}{2} + 16N - 7 \) ⇒ \( O(N^{2}) \)
- \( 2^{N}M = O(2^{N}M) \)
- \( \frac{1}{64}N^{2}M + 64NM = O(N^{2}M) \)
- \( N^{2}M + NlgM + NM^{2} = O(N^{2}M + NM^{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)+\cdots +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(NlgN) \)
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-완비 문제 중 하나를 풀 수 있음을 깨달았다면, 이 문제를 다항 시간에 푸는 것은 인류 역사상 아무도 못한 일이라는 사실을 알 수 있다.
그럴 때는 모델링을 달리 하거나, 근사해를 찾는 방향으로 길을 바꿔야 한다.