Before Reading¶

3. 코딩과 디버깅에 관하여¶

3.5 변수 범위의 이해¶

자료형의 프로모션¶

• 부호 없는 정수형과 부호 있는 정수형이 섞여 있는 경우: 부호 없는 정수형으로 변환
  • C++의 STL 에서는 모든 컨테이너의 size() 가 부호 없는 정수형인 size_t 로 캐스팅됨

3.6 실수 자료형의 이해¶

IEEE 754 표준¶

가장 많은 컴퓨터/컴파일러들에서 사용되는 실수 표기 방식

• 이진수로 실수를 표기
• floating-point 표기법
• 무한대, subnormal number, NaN(Not a Number) 등의 특수한 값이 존재

실수의 이진법 표기¶

1011.101 -> 11.625
#1/2 + 0 + 1/8 = 0.625

부동 소수점(floating-point) 표기¶

소수부분과 정수부분을 몇 비트씩 배정할지

정수부나 소수부에 너무 많은 비트 수를 배정할 경우, 큰 수를 표현하지 못하거나 정확도가 떨어지는 문제가 발생함. 따라서 IEEE 754를 포함한 대부분의 실수 표준에서는 소수점을 옮길 수 있도록 함.

실수 변수는 다음과 같은 3가지의 정보를 저장하게 됨.

• 부호 비트(sign bit): 양수인지 음수인지 여부
• 지수(exponent): 소수점을 몇 칸 옮겼나?
• 가수(mantissa): 소수점을 옮긴 실수의 최상위 X 비트

부호 비트는 1비트.

가수의 첫자리는 항상 1이기 때문에 따로 저장할 필요가 없다. 따라서 저장용량이 52비트뿐이지만, 53비트의 가수를 표현할 수 있다.

절대오차와 상대오차를 모두 이용한 실수 비교¶

bool doubleEqual(double a, double b) {
    double diff = fabs(a - b);
    // 절대오차가 허용 범위 안일 경우 무조건 true 반환
    if(diff < 1e-10) return true;
    // 이 이외의 경우에는 상대오차를 사용
    return diff <= 1e-8 * max(fabs(a), fabs(b));
}

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

4.2 선형 시간 알고리즘¶

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

이동평균(moving average)은 주식의 가격, 연간 국내 총생산(GDP) 등 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준이다. 시간에 따라 관찰된 숫자들이 주어질 때 M-이동 평균은 마지막 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;
}

선형 시간에 실행되는 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다. 주어진 입력을 최소한 한 번씩 쳐다보기라도 하려면 선형 시간이 걸릴 수 밖에 없기 때문이다!

4.3 선형 이하 시간 알고리즘¶

입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간(sublinear time) 알고리즘이라고 부른다. ex) 절반씩 나눠서 확인하는 경우는 밑이 2인 로그 시간이 걸린다.

이진 탐색(binary search)¶

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

위 함수가 배열 A[]에서 x를 삽입할 수 있는 위치 중 가장 앞에 있는 것을 반환한다고 생각하면 좀 더 쉽다. 대개의 배열이나 리스트 구현에서 i번째 위치에 새 원소를 삽입한다는 것은 i번째와 그 이후의 원소들을 뒤로 한 칸씩 밀어내고 들어간다는 뜻이다. 따라서 ==A[]에 x가 존재하는 경우 이 함수는 첫 번째 x의 위치를 반환하고, 없는 경우 x보다 큰 첫 번째 원소를 반환==한다.

4.4 지수 시간 알고리즘¶

다항 시간 알고리즘¶

반복문의 수행횟수를 입력 크기의 다항식 \(N, N^2, N^x\) 등의 선형 결합으로 이뤄진 알고리즘들을 다항 시간 알고리즘이라고 부른다. 다항 시간이라고 분류되는 알고리즘 간에는 엄청나게 큰 시간 차이가 날 수 있다. 그렇다면 왜 이들을 묶어서 이름을 붙인 걸까? 다항 시간보다 더더욱 오랜 시간이 걸리는 알고리즘들이 있기 때문이다.

지수 시간 알고리즘¶

모두가 먹을 수 있는 음식을 차릴때, 음식이 최소 가짓수가 되도록 하는 코드

const int INF = 987654321;
// check everyone can eat w/ this menu
bool canEverybodyEat(const vector<int>& menu);
// the number of menu
int M;
// select making food-th menu
int selectMenu(vector<int>& menu, int food) {
    // base: after finishing to select menu
    if (food == M) {
        if(canEverybodyEat(menu)) return menu.size();
        // if there are people who cannot eat any food, return INF
        return INF;
    }
    // calculate result when not eating food-th menu
    int ret = selectMenu(menu, food + 1);
    // calculate result when eating food-th menu and compare above two anwser,
    // and then take smaller one.
    menu.push_back(food);
    ret = min(ret, selectMenu(menu, food + 1));
    return ret;
}

M가지의 음식마다 만들다 만들지 않는다의 두 선택지가 있으니 만들 수 있는 답은 모두 \(2^M\) 가지이다. 답을 하나 만들때마다 canEverybodyEat()을 수행하니 이 알고리즘의 수행 시간은 \(2^M\)에 canEverybodyEat()의 수행시간을 곱한 것이 된다. canEverybodyEat()을 수행할 때 반복문이 \(N*M\) 번 수행된다고 가정하면 전체 수행시간은 \(N*M*2^M\) 이 된다.

이와 같이 N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘들은 지수시간(exponential time)에 동작한다고 말함. 지수 시간은 가장 큰 수행 시간 중에 하나로, 입력의 크기에 따라 다항 시간과는 반대로 비교도 안 되게 빠르게 증가함.

지수 시간보다 빠른 알고리즘을 찾지 못한 문제들이 전산학에는 쌓이고 쌓였음. 앞서 다룬 이 문제는 사실 집합 덮개(set cover)라고 부르는 유명한 문제로 아직까지 다항 시간 알고리즘이 존재한다는 증거도, 존재하지 않는다는 증거도 발견되지 않았다.

4.5 시간 복잡도¶

시간 복잡도(time complexity) 란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다. 기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산이라고 생각하면 된다. 예를 들어 다음은 기본적인 연산이다.

• 두 부호 있는 32비트 정수의 사칙연산
• 두 실수형 변수의 대소 비교
• 한 변수에 다른 변수 대입하기

반면 다음과 같은 연산들은 반복문을 포함하기 때문에 기본적인 연산이 아니다.

• 정수 배열 정렬하기
• 두 문자열이 서로 같은지 확인하기
• 입력된 수 소인수 분해하기

가장 깊이 중첩된 반복문의 내부에 있는 기본적인 연산들은 더 쪼갤 수 없기 때문에, 이것이 시간 복잡도의 대략적인 기준이 된다.

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

입력의 크기가 수행 시간을 결정하는 유일한 척도는 아니다. 입력이 어떤 형태로 구성되어 있는지도 수행 시간에 영향을 미친다. 입력의 종류에 따라 수행 시간이 달라지는 경우를 고려하기 위해 우리는 최선 / 최악의 경우, 그리고 평균적인 경우에 대한 수행 시간을 각각 따로 계산한다.

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

Big-O Notation을 사용해 알고리즘의 수행 시간을 표기한다. O 표기법은 간단히 말해 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지를 다 버리는 표기법이다. 최고차항을 제외한 모든 것을 들어내기 때문에, 수행 시간의 O 표기는 훨씬 계산하기 간편하다. 이 표기법을 쓸 때 알고리즘의 시간 복잡도는 반복문에 의해 결정되기 때문에, 반복문들이 몇 번이나 실행되는지만을 보면 된다.

O 표기법의 의미¶

O 표기법은 대략적으로 함수의 상한을 나타낸다는데 그 의미가 있다. 여기서 상한의 의미는 약간 특이하다. N에 대한 함수 \(f(N)\) 이 주어질 때, \(f(N) = O(g(N))\) 이라고 쓰는 것은 다음과 같은 의미이다.

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

O 표기법이 수행 시간의 상한을 나타낸다는 사실을 통해 알고리즘의 최악의 수행 시간을 알아냈다고 착각하는 일이 흔히 있다. 하지만 O 표기법은 각 격우의 수행 시간을 간단히 나타내는 표기법일 뿐, 특별히 최악의 수행 시간과 관련 있는 것은 아니다. 예를 들어 퀵정렬의 최악의 수행 시간은 \(O(N^2)\) 이며, 평균 수행 시간은 \(O(NlogN)\) 이다.

4.6 수행 시간 어림짐작하기¶

주먹구구 법칙¶

입력의 최대 크기 N이 10000이고, 테스트 케이스 하나를 푸는데 시간 제한이 1초인 문제를 풀고 있다고 가정하자. 처음에 만든 알고리즘의 시간 복잡도가 \(O(N^3)\) 이라고 한다면 과연 이 알고리즘으로 시간 내에 문제를 풀 수 있을까? \(O(N^2), O(NlogN)\)의 경우는 어떨까?

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(\(10^8\))을 넘어가면 시간 제한을 초과할 가능성이 있다. *물론 시간이 지날수록 CPU는 빨라지므로 1억이라는 숫자는 갈수록 커질것이다. 그러나 하드웨어의 속도는 아주 천천히 증가하고, 어차피 이 법칙 자체가 근사값이기 때문에 1억이란 기준은 현재까진 유효한것 같다.

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

문제의 특성 공부하기¶

계산 복잡도 이론은 각 문제의 특성을 공부하는 학문이다. 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타낸다. 빠른 알고리즘이 있는 문제는 계산적으로 쉽고, 빠른 알고리즘이 없는 문제는 계산적으로 어렵다고 말한다.

계산 복잡도 이론에서는 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 부른다. 예를 들어 정렬 문제에는 다항 시간 알고리즘이 수없이 많이 존재하므로, 정렬 문제는 P 문제이다. P 문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스(complexity class)라고 부른다. 엄청나게 다양하고 많은 복잡도 클래스가 있지만, 그중 두 가지의 클래스가 가장 중요하다. 바로 P 문제와 NP 문제이다.

난이도의 함정¶

P는 polynomial, NP는 non-polynomial 의 머릿글자이지만, NP 문제가 다항 시간에 풀 수 없는 문제란 것은 아니다! 어떤 문제를 다항 시간에 풀 수 있음을 증명하기란 쉽지만, 풀 수 없음을 보이기는 어렵다는 점!!

NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미함. 예를 들어 부분 집합 합 문제는 NP 문제이다. 부분 집합 합 문제의 답이 주어졌을 때 이것이 원래 집합의 부분 집합인지, 그리고 원소들의 합이 S 인지 다항 시간에 쉽게 확인할 수 있기 때문이다. 또한 모든 P 문제들은 NP 문제에도 포함된다. 주어진 문제를 푸는 다항 시간 알고리즘이 존재한다면 이를 사용해 문제를 처음부터 다시 푼 뒤 답을 비교하는 방식으로 답의 정당성을 다항 시간에 확인할 수 있기 때문이다.

5. 알고리즘의 정당성 증명¶

5.1 도입¶

알고리즘의 정당성 증명¶

알고리즘의 증명을 공부해야 하는 가장 큰 이유는 많은 경우 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문이다. 모든 알고리즘은 사실 치열한 고민과 개선 과정을 거쳐 태어난다(어느 날 의사코드가 적힌 종이가 하늘에서 팔랑팔랑 떨어지지 않음).

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

100개의 도미노가 순서대로 놓여있는 광경 상상. - 첫번째 도미노는 직접 손으로 밀어서 쓰러뜨린다. - 한 도미노가 쓰러지면 다음 도미노 역시 반드시 쓰러진다.

그러면 마지막 도미노 또한 쓰러진다는 것을 직관적으로 알 수 있다.

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

• 단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다. 앞의 예에서는 100개의 도미노를 도미노 하나씩으로 나누었다. 이 과정은 너무 당연해서 잊어버리기 쉽지만 가끔은 중요할 때가 있다.
• 첫 단계 증명: 그중 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 앞의 예에서는 첫 번째 도미노가 넘어짐을 증명하는 것이 이 과정이다.
• 귀납 증명: 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다. 앞의 예에서는 한 도미노가 쓰러지면 다음 도미노는 반드시 쓰러짐을 보이는 것이다.

반복문 불변식¶

귀납법을 이용해 알고리즘의 정당성을 증명할 때는 반복문 불변식(loop invariant) 이라는 개념이 유용하게 쓰인다. 반복문 불변식이란 반복문의 내용이 한번 실행될때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다. 반복문이 마지막에 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 하는 것이다. 불변식을 이용하면 반복문의 정당성을 다음과 같이 증명할 수 있다.

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

// (*) 불변식은 여기서 성립해야 함
while(어떤 조건) {
    // 반복문 내용의 시작
    ...
    // 반복문 내용의 끝
    // (**) 불변식은 여기에서도 성립해야 함
}

5.3 귀류법¶

귀류법은 대개 어떤 선택이 항상 최선임을 증명하고자 할 때 많이 이용된다. 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에, 사실은 그런 일이 있을 수 없음을 보이면 우리가 최선의 답을 선택했음을 보일 수 있으니까요.

귀류법을 이용한 증명들¶

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

5.4 다른 기술들¶

비둘기집의 원리¶

Pigeonhole Principle

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

구성적 증명¶

Constructive Proof

원하는 어떤 답이 존재한다는 사실을 증명하기 위해서 사용된다. '답이 존재하는가'에 대한 대답으로 '이렇게 만들면 된다'라고 하는 것이 구성적 증명이기 때문에, 구성적 증명의 내용은 사실상 알고리즘인 경우가 많다.

6. 무식하게 풀기¶

6.1 도입¶

가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부른다. 완전 탐색은 더 빠른 알고리즘의 기반이 되기도 하기 때문에 완전 탐색에 대해 잘 익혀둘 필요가 있다.

6.2 재귀 호출과 완전 탐색¶

재귀 호출¶

1부터 n까지의 합을 반환하는 함수의 구현 시에 n개의 숫자의 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 하자. n 만 따로 빼내면, 1부터 n-1까지의 조각들이 남는데, 이들은 모두 처리한 결과는 다름아닌 1부터 n-1까지의 합이다.

// 필수조건: n>=1
// 결과: 1부터 n까지의 합을 반환한다.
int recursiveSum(int n){
    if (n == 1) return 1;
    return n + recursiveSum(n - 1);
}

n=1 이면 조각이 하나뿐이니 더 이상 쪼개질 작업이 없다. 이처럼 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례(base case)라고 한다.

문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해줄 수 있는 강력한 무기가 된다.

예제: 중첩 반복문 대체하기¶

0부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드.

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        for (int k = j + 1; k < n; k++)
            for (int l = k + 1; l < n; l++)
                cout << i << " " << j << " " << k << " " << l << endl;

위 코드 조각이 하는 작업은 네 개의 조각으로 나눌 수 있다. 각 조각에서 하나의 원소를 고르는 것이다. 이렇게 원소를 고른 뒤, 남은 원소들을 고르는 작업을 자기 자신을 호출해 떠넘기는 재귀 함수를 작성하자. 이때 남은 원소들을 고르는 '작업'을 다음과 같은 입력들의 집합으로 정의할 수 있다.

• 원소들의 총 개수
• 더 골라야 할 원소들의 개수
• 지금까지 고른 원소들의 번호

아래 코드는 이 작업을 하는 재귀 함수를 보여준다. 이 코드는 실질적으로 앞의 코드 조각에서 for문 하나만을 별도의 함수로 떼어낸 것과 다르지 않다.

// n 개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘

// n: 전체 원소의 수
// picked: 지금까지 고른 원소들의 번호
// toPick: 더 고를 원소의 수
// 일때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.

void pick(int n, vector<int>& picked, int toPick) {

}