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 문제에도 포함된다. 주어진 문제를 푸는 다항 시간 알고리즘이 존재한다면 이를 사용해 문제를 처음부터 다시 푼 뒤 답을 비교하는 방식으로 답의 정당성을 다항 시간에 확인할 수 있기 때문이다.