[알고리즘 문제해결전략] 알고리즘 분석
알고리즘(Algorithm)이란?
어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 한 가지 방법을 명료하게 써 놓은 것
알고리즘을 평가하는 두 가지의 큰 기준은 알고리즘이 사용하는 시간과 공간입니다.
- 시간: 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 이야기입니다.
- 공간: 알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 이야기입니다.
알고리즘의 시간 복잡도 분석
프로그램의 실행 시간은 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합합니다.
가장 큰 이유는 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있기 때문입니다. 또한 어떤 문자열 구현을 사용했는지, 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 프로그램의 최종 수행 시간은 크게 달라질 수 있습니다.
알고리즘은 언제나 같은 속도로 동작하는 것이 아니며, 입력의 크기나 특성에 따라 수행 시간이 달라질 수 있습니다.
우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정합니다. 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현합니다.
선형시간(linear time) 알고리즘
입력의 크기에 대비해 걸리는 시간을 그래프로 그렸을 때 정확히 직선이 되는 알고리즘
선형 이하 시간(sublinear time) 알고리즘
입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘
이진 탐색(binary search)
$binsearch(A[], x)$ = 오름차순으로 정렬된 배열 $A[]$와 찾고 싶은 값 $x$가 주어질 때 $A[i-1] < x \leq A[i]$인 $i$를 반환한다. 이때 $A[-1]=-\infty$, $A[N]=\infty$ 로 가정한다.
조금 더 쉽게 풀어 말하자면, 배열 $A[]$에서 $x$를 삽입할 수 있는 위치 중 가장 앞에 있는 것을 반환합니다. 따라서 $A[]$에 $x$가 존재하는 경우에는 첫 번째로 발견하는 $x$의 위치를 반환하고, 없을 경우에는 $x$보다 큰 첫 번째 원소를 반환합니다.
다항 시간(Polynomial time) 알고리즘
변수 $N$과 $N^2$, 그 외 $N$의 거듭제곱들의 선형 결합으로 이루어진 식들을 다항식이라고 부르며, 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘이라고 부릅니다.
앞서 언급한 선형시간도 다항 시간 알고리즘에 해당되지만, 다항 시간이라는 하나의 분류에 포함되는 알고리즘 간에는 엄청난 큰 시간 차이가 존재할 수도 있습니다. 이러한 다항 시간 알고리즘보다 훨씬 오래 걸리는 알고리즘들이 있기 때문에 큰 차이가 있을 수 있음에도 다항 시간이라는 이름으로 묶어 놓은 것입니다.
지수 시간(exponential time) 알고리즘
$N$이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘
오래 걸린다고 하여 항상 이것보다 빠른 알고리즘이 있지는 않습니다. 이와 같이 아직까지 다항 시간 알고리즘이 존재한다는 증거도, 존재하지 않는다는 증거도 발견되지 않은 문제들을 집합 덮개(set cover)라고 합니다.
시간 복잡도(time complexity)
가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
기본적인 연산이란:
- 두 부호 있는 32비트 정수의 사칙연산
- 두 실수형 변수의 대소 비교
- 한 변수에 다른 변수 대입하기
기본적인 연산이 아닌 경우:
- 정수 배열 정렬하기
- 두 문자열이 서로 같은지 확인하기
- 입력된 수 소인수 분해하기
시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미입니다. 그렇다고 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니며, 입력의 크기가 충분히 작을 때는 시간 복잡도가 높은 알고리즘이 더 빠르게 작동할 수도 있습니다. 시간 복잡도가 낮은 알고리즘은 입력이 커지면 커질수록 더 효율적이게 됩니다.
입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 최선(best)/최악(worst)의 경우, 그리고 평균(Average)적인 경우에 대한 수행 시간을 각각 따로 계산합니다. 선형 탐색에 대한 최선, 최악 그리고 평균적인 경우의 수행 시간을 계산한다면,
- 최선의 수행 시간: 찾으려는 원소가 배열의 맨 앞에 있을 경우 수행 횟수는 1이 됩니다.
- 최악의 수행 시간: 배열에 해당 원소가 없을 경우 수행 횟수는 $N$이 됩니다.
- 평균적인 경우의 수행 시간: 존재할 수 있는 모든 입력의 등장 확률이 모두 같다고 가정합니다. 만약 주어진 배열이 항상 찾는 원소를 포한함다고 가정하면 반환 값의 기대치는 대략 $\frac{N}{2}$이 되고, 평균적인 수행 횟수는 $\frac{N}{2}$이 됩니다.
이 세 개의 기준 중 사람들이 대개 사용하는 것은 최악의 수행 시간 혹은 수행 시간의 기대치입니다.
대문자 O 표기법(Big-O Notation)
알고리즘이 복잡할 때 한 줄 한 줄 세고 있을 수만은 없기 때문에 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 빈복문의 반복 수만 고려하게 됩니다. 여기에서 이것을 더욱 간단하게 표현하여 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이 대문자 O 표기법(Big-O Notation)입니다.
- $2^NM=O(2^NM)$
- $\frac{1}{64}N^2M+64NM=O(N^2M)$
- $N^2M+NlgM+NM^2=O(N^2M+NM^2)$
- $42=O(1)$
세번째의 경우 $N^2M$과 $NM^2$ 어느 한쪽이 빠르게 증가한다고 할 수 없기 때문에 둘다 O표기에 포함됩니다. 마지막 예에서는 입력의 크기와 상관없이 항상 같은 시간이 걸리기 때문에 대문자 O 표기법으로 이 알고리즘은 1만큼의 시간밖에 걸리지 않는다고 씁니다. 이러한 알고리즘을 상수 시간(constant-time) 알고리즘이라고 부릅니다.
O 표기법의 의미
O 표기법은 대략적으로 함수의 상한을 나타냅니다.
$N$에 대한 함수 $f(N)=O(g(N))$이라고 쓰는 것은 다음과 같은 의미입니다.
아주 큰 $N_0$와 $C(N_0, C>0)$를 적절히 선택하면 $N_0 \leq N$인 모든 $N$에 대해 $\vert f(N) \vert \leq C \times \vert g(N) \vert$이 참이 되도록 할 수 있다.
O 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법일 뿐, O 표기법이 수행 시간의 상한을 나타낸다고 해서 특별히 최악의 수행 시간과 관련이 있는 것은 아닙니다.
이에 따른 예로, 선택 정렬(selection sort)과 삽입 정렬(insertion sort)은 둘 다 $O(N^2)$의 시간 복잡도를 가지지만, 삽입 정렬은 입력의 종류에 따라 $O(N)$의 속도까지 낼 수 있기 때문에 대부분의 경우 삽입 정렬이 선택 정렬보다 빠릅니다. 실제로 삽입 정렬은 흔히 사용하는 $O(N^2)$ 정렬 중 가장 빠른 알고리즘으로 알려져 있습니다.
아래에 두 정렬의 코드와 동작 과정을 설명한 포스팅의 링크를 달아두겠습니다.
수행 시간 어림짐작하기
입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억($10^8$)을 넘어가면 시간 제한을 초과할 가능성이 있다.
앞서 말했다시피 수행시간에는 많은 변수가 있으므로 이 방법은 그저 주먹구구 방식일 뿐이라는 것을 염두에 두어야 합니다.
계산 복잡도 클래스: P, NP, NP-완비(NP-Complete)
각 문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제들을 분류하고 각 분류의 특성을 연구하는 학문을 계산 복잡도 이론(Computational Complexity Theory)이라고 합니다.
문제의 특성 공부하기
계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타냅니다. 빠른 알고리즘이 있는 문제는 계산적으로 쉽고, 빠른 알고리즘이 없는 문제는 계산적으로 어렵다고 말합니다.
일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들만을 ‘빠르다’고 말합니다. 이렇게 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 부릅니다. P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스(complexity class)라고 부릅니다. 수많은 복잡도 클래스가 있지만, 그중 P 문제와 NP 문제가 가장 중요합니다.
난이도의 함정
P는 polynomial, NP는 non-polynomial의 머릿글자를 따왔으니 NP 문제가 다항 시간 알고리즘이 존재하지 않는 문제들의 집합이라고 생각해서는 안됩니다. 문제를 다항 시간에 풀 수 있음을 증명하기란 쉽지만, 풀 수 없음을 증명하기는 어렵습니다. 해당 문제의 다항 시간 알고리즘을 찾아내지 못하였다고 그런 알고리즘이 없다고 증명할 방법이 현재로썬 없기 때문에, 다항 시간 알고리즘이 존재하는 문제와 그렇지 않은 문제로 문제들을 구분하기는 어렵습니다.
계산 복잡도에서 흔히 말하는 ‘어려운 문제’들은 다음과 같이 정의됩니다.
- 정말 어려운 문제를 잘 골라서 이것을 어려운 문제의 기준으로 삼습니다.
- 기준 문제만큼 어렵거나 그보다 어려운 문제들, ‘기준 이상으로 어려운 문제들’만을 어렵다고 부릅니다.
문제 A가 문제 B 이상으로 어렵다고 말하려면, A를 푸는 가장 빠른 알고리즘이 B를 푸는 가장 빠른 알고리즘 이상의 시간이 걸려야 합니다.
계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산(reduction)이라는 기법을 이용합니다. 환산이란 한 문제를 다른 문제로 바꿔서 푸는 기법입니다.
- B 문제를 적절히 변형하여 A 문제로 바꾸는 환산 알고리즘이 존재한다고 가정하였을 때, A를 푸는 가장 빠른 알고리즘을 가져오면, 이것을 환산 알고리즘과 결합해 B를 푸는 알고리즘을 만들 수 있습니다.
- 환산 알고리즘이 무시할 수 있을 정도로 빠르다고 가정한다면, A문제의 알고리즘의 시간으로 B문제를 풀 수 있다는 것은 B문제를 푸는 가장 빠른 알고리즘은 A문제의 알고리즘과 같거나 더 빠를 수밖에 없습니다.
- 앞서 정의한 대로, A문제를 푸는 가장 빠른 알고리즘이 B문제를 푸는 가장 빠른 알고리즘 이상의 시간이 걸리기 때문에 A문제가 B문제 이상으로 어렵다는 것을 증명할 수 있게 됩니다.
NP 문제, NP 난해 문제
결과적으로 NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미합니다. 그렇기 때문에 모든 P문제들은 NP문제에도 포함됩니다.
앞서 난이도를 비교하는 법을 알았으니 ‘어려운 문제’의 기준이 되는 문제들을 알아야 문제들을 구분할 수 있을겁니다. 그 기준이 되는 것이 바로 SAT 문제(satisfiability problem)입니다.
SAT 문제는 모든 NP 문제 이상으로 어렵습니다. 이 말은 즉 SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다는 얘기가 됩니다. 이런 속성을 갖는 문제들의 집합을 NP-난해(NP-Hard) 문제라고 부릅니다. 또한 NP-난해 문제이면서 NP인 문제들을 NP-완비(NP-Complete) 문제라고 합니다.
Leave a comment