계속 수정됩니다.

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

알고리즘: 주어진 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것

알고리즘 평가 기준

• 시간: 더 빠르게 동작해야 한다. 이를 위해서는 알고리즘의 수행 속도와 특성을 분석하는 능력이 필요하다.
• 공간: 더 적은 용량의 메모리를 사용해야 한다.

수행 속도가 중요하다. 더 많은 메모리를 사용해 수행 속도를 높이는 알고리즘(동적 계획법 등)이 있고 수행 속도를 희생해서 메모리 사용량을 줄인 알고리즘이 있다.

도입

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

• 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 뿐만 아니라 어떤 문자열 구현을 사용했는지, 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 최종 수행 시간이 크게 달라질 수 있다.
• 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못한다.

반복문(수행 횟수)이 알고리즘의 수행 시간을 지배한다.

선형 시간 알고리즘

수행 시간이 N에 정비례할 때 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 된다.
이런 알고리즘을 선형 시간(linear time) 알고리즘이라 부른다.

선형 이하 시간 알고리즘

이진 탐색 알고리즘으로 N개의 자료 중 하나를 찾는다고 하면 최대 $log_2N$ 번 만에 찾을 수 있다.
이와 같이 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간(sublinear time) 알고리즘이라 부른다.

이진 탐색

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

C++ STL 에는 x를 삽입할 수 있는 위치 중 가장 이른 것을 반환하는 lower_bound, upper_bound 가 있다.

지수 시간 알고리즘

다항 시간 알고리즘

반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘
$N$, $N^2$ , $N^{100}$ 모두 다항 시간 알고리즘

지수 시간 알고리즘

N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수 시간(exponential time)에 동작한다고 말한다.
지수 시간은 가장 큰 수행 시간 중 하나다.

다항 시간 알고리즘이 있는 문제는 계산적으로 쉬운 문제, 아직 없는 문제를 계산적으로 어려운 문제라고 이야기한다.

지수 시간이 걸리는 문제들을 효율적으로 해결할 수 있는 방법으로 조합 탐색이 있다.

소인수 분해의 수행 시간

입력으로 주어지는 숫자의 개수가 아니라 그 크기에 따라 수행 시간이 달라지는 알고리즘도 지수 수행 시간을 가질 수 있다.
자연수 N이 주어질 때 N의 소인수 분해 결과를 구할 때 최악의 경우인 반복문이 가장 많이 실행되는 경우는 주어진 수 N이 소수인 경우다.
입력의 값이 커질수록 숫자를 저장하는데 필요한 메모리의 공간이 증가한다.

이때 입력이 차지하는 비트의 수에 따라 수행 시간이 증가한다고 생각하면
비트의 수가 하나 증가할 때마다 표현할 수 있는 수의 범위와 알고리즘의 최대 수행 시간이 두 배로 증가하므로
입력의 크기를 입력이 차지하는 비트 수로 정의했을 때 입력의 크기에 대해 지수 시간이 걸린다고 말할 수 있다.

시간 복잡도

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

시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아니다.

입력의 크기가 수행 시간을 결정하는 유일한 척도는 아니다.
입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 미친다.
(탐색 문제에서 입력받은 배열에 찾는 원소의 위치에 따라 반복문이 실행되는 횟수가 달라짐)

최선의 수행 시간, 최악의 수행 시간, 평균적인 경우의 수행 시간
최악의 수행 시간이나 수행 시간의 기대치를 대개 사용한다.

점근적 시간 표기: O 표기

전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려
주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법

O 표기법의 의미

함수의 상한을 나타낸다.
N에 대한 함수 $f(N)$이 주어질 때, $f(N)=O(g(N))$이라고 쓰는 것은 다음과 같은 의미다.

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

O 표기법은 각 경우의 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련이 있지는 않다.

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

$N$개의 작은 작업들을 순서대로 하는데, 각 작업에 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다고 할 수 있다.

동적 배열을 다루는 18.2절, 10장의 연습 문제인 미나스 아노르에서 다룬다.

수행 시간 어림짐작하기

주먹구구 법칙

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

고려해야 하는 요소

• 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: 어디까지나 예측 값
• 반복문의 내부가 복잡한 경우
• 메모리 사용 패턴이 복잡한 경우
• 언어와 컴파일러의 차이
• 구형 컴퓨터를 사용하는 경우

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

계산 복잡도 이론: 각 문제에 대해 이를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제들을 분류하고 각 분류의 특성을 연구하는 학문

P 문제: 다항 시간 알고리즘이 존재하는 문제들의 집합
NP 문제: 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제

계산 복잡도 클래스: P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합

어려운 문제의 기준

• 정말 어려운 문제를 잘 골라서 이것을 어려운 문제의 기준으로 삼는다.
• 그리고 앞으로는 기준 문제만큼 어렵거나 그보다 어려운 문제들, 다시 말해 '기준 이상으로 어려운 문제들'만을 어렵다고 부른다.

난이도의 비교

환산: 한 문제를 다른 문제로 바꿔서 푸는 기법

A를 푸는 가장 빠른 알고리즘을 환산 알고리즘과 결합해 B를 푸는 알고리즘을 만들었다.
환산 알고리즘이 무시할 수 있는 정도로 빠르다고 가정하면 결합된 알고리즘은 B를 푸는 가장 빠른 알고리즘이 같거나 더 빠를 테니,
결국 B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를 수밖에 없다.
A가 B 이상으로 어렵다는 의미

NP 문제, NP 난해 문제

어려운 문제의 기준은 SAT 문제
SAT 문제는 모든 NP 문제 이상으로 어렵다.
SAT 문제란 N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제

((a||b||!c)&&(!c||!a)&&((!a&&b)||(b&&!c)))&&(!b||(!a&&!c))

SAT를 다항 시간에 풀 수 있으면 NP 문제들을 전부 다항 시간에 풀 수 있다. 이런 속성을 갖는 문제들의 집합을 NP-난해 문제라고 부른다.

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

P=NP?

1. NP-난해 문제 중 하나를 다항 시간에 풀 수 있다면, 이 알고리즘을 이용해 NP에 속한 모든 문제를 다항 시간에 풀 수 있다.
2. NP 문제 중 하나를 골라 P에 포함되어 있지 않음을, 다시 말해 다항 시간에 푸는 방법이 없음을 증명하면 P≠NP 임을 보일 수 있다.

더 읽을거리

재귀적인 알고리즘의 시간 복잡도를 계산하는 쉬운 방법으로 마스터 정리(Master Theorem)가 있다. O 표기법을 쉽게 계산할 수 있도록 도와준다.

알고리즘의 정당성 증명

단위 테스트는 알고리즘에 문제가 있음을 증명할 수는 있어도 문제가 없음을 증명할 수는 없다.
알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다.

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

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

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

반복문 불변식은 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다.
반복문이 마지막에 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 한다.
불변식을 이용하여 다음과 같이 반복문의 정당성을 증명한다.

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

단정문을 이용해 반복문 불변식 강제하기

불변식을 단정문으로 강제해 버리면 해당 불변식이 깨졌을 때 프로그램이 강제 종료되기 때문에 불변식의 유지에 문제가 있다는 사실을 아주 쉽게 알 수 있다.

귀류법

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법을 귀류법이라 한다.

귀류법을 이용한 증명들

알고리즘의 결과가 최선(최단 경로 탐색, 가장 높은 탑 쌓기)임을 보이기 위해 각 단계에서 최선을 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선을 선택을 한다면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명한다

다른 기술들

비둘기집의 원리

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

동전 뒤집기

100개의 동전이 바닥에 깔려 잇는데 이 중 F개는 앞면, 100-F개는 뒷면이 위로 놓여 있다.
우리는 이 동전들이 모두 앞면을 위로 하게 뒤집고 싶은데, 한 번 뒤집을 때 반드시 X개의 동전을 한꺼번에 뒤집어야 한다.
같은 동전을 두 번 이상 뒤집는 것도 상관없다.
이때 뒤집는 횟수를 최소화하고 싶다면 답의 상한을 얼마일까?

정답은 100. (이해 못함)

순환 소수 찾기

분수 $\frac{a}{b}$가 주어질 때 실수 연산을 쓰지 않고 이 분수를 소수 형태로 출력하려 한다.

// a >= 0, b > 0 이라 가정
void printDecimal(int a, int b) {
	int iter = 0;
    while(a > 0) {
    	// 첫 번째와 두 번째 사이에 소수점을 찍는다.
        if(iter++ == 1) cout << '.';
        cout << a / b;
        a = (a % b) * 10;
    }
}

무한 소수를 인식해서 별도로 처리해줘야 한다.

a=(a%b)*10을 취하는 부분을 보자.
a%b의 결과는 언제나 [0, b-1] 범위의 값을 가진다.

while문이 b+1번 반복될 때까지 함수가 종료되지 않았다고 하자.
a%b의 결과는 b가지의 결과만 가질 수 있으니 결과가 중복될 것이다.

그러면 같은 결과가 첫 번째로 등장했을 때부터 두 번재 등장할 때까지가
무한히 순환되는 순환 소수임을 알 수 있다.

구성적 증명

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

하늘을 나는 교통 수단을 만들 수 있다는 주장을 증명하려 한다면 구성적 증명이 하는 일은 비행기를 만들어서 보여 주거나, 비행기 만드는 법이 적힌 설명서를 건네 주는 것이다.

안정적 결혼 문제

n명의 남성과 여성이 단체 미팅에서 만났다.
모든 사람은 자신이 원하는 상대방의 우선순위를 맘 속에 정했고, 각각 짝이 되었다.
다른 짝이 서로를 더 선호한다는 사실을 알게 되었는데, 이런 일이 일어나지 않도록
짝을 지어줄 수 있는 방법이 항상 있을까?

1. 처음에는 여성들이 모두 자신이 가장 선호하는 남성의 앞에 가서 프로포즈를 한다.
   남성이 그중 제일 마음에 드는 여성을 고르면 나머지는 제자리로 돌아간다.
2. 남은 여성들은 다음으로 짝의 여부에 상관없이 마음에 드는 남성에게 다가가 프로포즈한다.
   남성들은 현재 자기 짝보다 더 맘에 드는 여성이 다가왔다면, 지금의 파트너를 놓아주고 새 여성에게 넘어간다.
3. 더 프로포즈할 여성이 없을 때까지 2번 항목을 반복한다.

종료 증명

각 여성은 퇴짜 맞을 때마다 지금까지 프로포즈했던 남성들보다 우선순위가 낮은 남성에게 프로포즈한다. 따라서 각 여성이 최대 n명의 남성들에게 순서대로 프로포즈한 이후엔 더이상 프로포즈할 남성이 없으므로, 이 과정은 언젠가 종료한다.

모든 사람들이 짝을 찾는지 증명

프로포즈를 받은 남성은 그중 한 사람을 반드시 선택하므로 항상 짝이 있다.
귀류법을 적용하여 남녀 한 사람씩 짝을 찾지 못하고 남았다고 가정하자. 그런데 여성은 우선순위가 높은 순서대로 모두에게 한 번씩 프로포즈하기 때문에, 이 남성에게도 한 번은 프로포즈 했을 것이다. 이 남성은 프로포즈를 받아들였어야 하므로, 따라서 짝을 찾지 못하는 사람은 있을 수 없다.

짝들의 안정성

역시 귀류법으로 증명한다. 이 과정의 결과로 짝을 지었는데 짝이 아닌 두 남녀가 서로 자신의 짝보다 상대방을 더 선호한다고 가정하자.
여성은 지금 자신의 짝 이전에 그 남성에게 반드시 프로포즈했어야 한다.
그런데도 짝지어지지 않았다는 말은 더 맘에 드는 여성에게 프로포즈를 받아서 수락했다는 뜻이다. 더 맘에 드는 여성이 나타났을 때만 짝을 바꾸므로, 프로포즈 받았던 여성보다 맘에 들지 않는 여성과 최종적으로 짝이 되는 일은 없다.
따라서 우리가 가정했던 상황은 존재할 수 없다.

더 읽을거리

『생각하는 프로그래밍』(인사이트): 쉽게 읽을 수 있으면서 훌륭한 통찰을 여럿 담고있다. 반복문 불변식을 도입하여 이진 탐색 코드의 정당성을 한 줄 한 줄 엄밀하게 증명하는데, 프로그램 정당성 증명에 관한 가장 모범적인 예로 추천한다.