[알고리즘] Chapter 1 & 2

알고리즘이란 무엇인가?

알고리즘이란 정확히 정의된 계산 문제를 풀기 위한 특정 절차이다.

• 유한한 단계로 이루어진 절차이다.

• 실행될 액션들과 그 액션들의 순서를 나타낸다.

• 모호하지 않은 명령들이 순차적으로 나열된 것이다. 이들은 정당한 입력에 대해 요구되는 출력을 유한한 시간 내에 내놓아야한다.

알고리즘과 머신러닝의 차이

알고리즘은 입력이 주어지고, 그에 맞는 출력을 얻기 위해 문제를 해결하는 과정이다. 또한 문제가 엄밀하게 정의 되어 있다.

그에 반해 머신러닝은 이미 입력 과 정답을 바탕으로 알고리즘을 학습하는 것이다. 또한, 문제가 엄밀히 정의되어 있지 않아, 정확한 출력이 요구되지 않을 수도 있다.

따라서 알고리즘은 명백하게 정의된 수행절차들이고, 입출력 간의 관계를 정확하게 정의한다.

예를들어, 소수 구하기, 정렬하기 는 알고리즘 을 정의할 수 있는 문제이다.

알고리즘을 공부하는 절차

알고리즘은 두가지의 접근 방향이 있는데,

1. 문제 기반 : 같은 문제를 해결하는 여러가지 방법에 대해 연구할 수 있거나, (정렬)

2. 설계 기반 : 여러 문제를 한가지 방법으로 해결하는 방법에 대해 연구할 수 있다. (분할정복)

예시 : GCD 구하기

GCD 는 Greatest Common Divisor 의 약자로 한국어로 최대 공약수를 뜻한다.

이에 대해서는 유클리드 호제법을 이용할 수도 있고, 그냥 브루트 포스를 사용할 수도 있지만, 브루트 포스도 하나의 방법이며 이 자체로 알고리즘일 수도 있다는 사실을 알면 좋겠다.

실제로 의사코드를 제작하는 과정을 통해 직접 의사코드로 의사를 표현해보자.

GCD(m, n)
    while n != 0 do
        r <- m%n // m mod(n), m이 n보다 크다 가정.
        m <- n
        n <- r

이 의사코드가 맞는 지 증명을 하기 위해서는, 위에 반복문이 수행되는 반복 작업이 다른 error 나 argument 에 대해서 맞다는 것을 증명을 해야할 것이다.

알고리즘의 설계-분석 과정

알고리즘을 설계-분석하는 과정은 아래와 같다.

1. 문제를 이해하기

2. 상황 분석하기

   2-1. 연산 장치가 현실적으로 계산 가능한 양인가?

   2-2. 정확하게 풀 것인가? 근사치를 구할 것인가? (소수)

   2-3. 어떤 알고리즘 디자인 기술을 정할 것인가?

   2-4. 어떤 자료구조를 사용할 것인가?

3. 알고리즘 설계하기

4. 정확함을 증명하기

   4-1. 정확하지 않다면, 2번 항목과 3번 항목으로 돌아갈 수 있다.

5. 알고리즘을 분석하기 (얼마나 빠른지 등)

   5-1. 빠르지 않다면, 2번 항목과 3번 항목으로 돌아갈 수도 있다.

6. 알고리즘을 구현(Code) 하기

알고리즘을 증명하는 방법

알고리즘을 증명하는 방법은 수학에서 많이 가져올 수 있다. 필자는 애초에 알고리즘 자체가 수학의 일종이라고 생각한다.

이번 강의는 그 중 자주 사용되는 방법으로 몇가지를 소개한다.

일반적으로 두가지 경우를 먼저 소개한다.

정확하지 않음을 증명하기

대표적으로 반례를 찾는 것이다. 반례를 찾으면 알고리즘은 실패한 알고리즘이다.

정확함을 증명하기

모든 입력에 대해 정확함을 증명하기란 몇가지의 입력 예시만으론 쉽지가 않다. 이에 대해서는 수학적 귀납법을 활용한다.

증명하기

연역적 증명 (Deductive reasoning) 이란, 대전제를 이용해서 소전제가 맞음을 증명하는 방법이 있다.

귀납적 증명 (Inductive reasoning) 소전제를 모아서 하나의 증명을 하는 방법이다.

귀류법이란, 대전제가 틀렸음을 가정했을 때, 반례가 생김을 찾아서 증명하는 방법이다.

수학적 귀납법을 이용한 증명 과정

실제로 하나하나의 예시를 모아서 증명하기란 말이 되지 않는다. 따라서 이를 수학적으로 증명할 수 있는 방법이 있는데, 이것이 수학적 귀납법 이다.

수학적 귀납법은 도미노와 같다고 생각하면 된다.

1. 첫번째 사례 (P_1, basis) 가 옳다고 증명한다.

2. 1번째부터 k 번째 사례 (P_k, n >= k, P_1 … P_k) 가 옳다고 가정 한다.

3. 이때, 첫번째 사례부터 k번째 사례로 k + 1 번째 사례가 옳다고 증명하면, 이는 수학적으로 증명이 된다.

가우스 공식이 맞음을 증명하는 방법도 위 방법을 통해서 증명이 가능하다.

예시 : 정렬 알고리즘

정렬 문제란, 입력으로 특정 숫자의 나열에 대해 증가하는 순서의 순열로 출력하게 만드는 문제를 뜻한다.

삽입 정렬이 무엇인가?

삽입 정렬은 정렬 문제를 푸는 알고리즘 중에 하나이다.

A[] 는 입력된 배열

for j <- 2 to N
    do key <- A[j]
        i <- j-1 // i는 j-1부터 1까지 순회를 할 것이다.
        while i > 0 and A[i] > key
            do A[i + 1] <- A[i]
                i <- i-1
        A[i+1] <- key

위 예시를 잘 보면, j번째 순회에서 앞의 원소들을 하나하나씩 읽으며, j번째 값보다 i번째 값이 크면 하나씩 뒤로 넘겨준다.

그러다가, 작거나 같은 순간이 온다면, 그자리에 j번째 원소를 집어넣어주는 작업을 한다.

알고리즘 분석하기

해당 알고리즘이 빠른가? -> 걸리는 시간이 얼마나 되는가?

알고리즘이 좋은가? -> 어떻게 판별할 것인가?

알고리즘이 정확한가? -> 어떻게 증명할 것인가?

위의 사항들에 대해서 말할 수 있어야할 것이다.

분석에 대해서는 아래 3가지 경우의 수로 나뉠 수 있다.

• worst case : 가장 최악의 경우의 수를 뜻합니다. 시간이 가장 오래걸리는 경우를 뜻하지요.

• average case : 평균적인 경우의 수를 뜻합니다. 모든 경우의 수에 대해 평균으로 나누어 계산을 하므로 구하기 어렵습니다.

• best-case : 가장 빠르게 될 경우의 수를 뜻합니다. 시간이 가장 안걸리므로 너무 편향적인 결과를 보여주기도 합니다.

정확한 속도를 계산할 수 없어서 점근 표기법 (Asymptotic Analysis) 을 활용한다.

삽입정렬에서는 worst-case 는 역순으로 정렬된 배열이 주어졌을 때 일 것이고, best-case 는 이미 정렬된 배열이 주어졌을 때일 것이다. 그리고 average-case 는 best와 worst 만큼 역순과 정렬된 배열이 주어진 경우일 것이다.

따라서, worst case는 O(n^2), best case는 O(n), average case는 O(n^2 / 2) = O(n^2) 일 것이다.

이 표기법에 관해서는 이후 문서에서 상세하게 표시할 것이다.