[Algorithms] 유클리드(Euclid) 호제법

미루고 미루다 드디어

알고리즘(Algorithms) 학습을 시작!

알고리즘이란

어떤 문제를 해결하기 위한

절차를 기술해 놓은 것입니다

절차는 어떠한 작동을

어떠한 순서로 행할 것인가를

나열한 것인데요

크게 아래의 4가지 특성을

만족해야 합니다

특성	설명
Preciseness(엄밀성)	기술된 내용은 한 가지 이상의 의미를 포함하지 않도록 해야 함
Effectiveness(실효성)	기술된 내용은 반드시 주어진 상황에 영향을 주어서 실제로 상황을 변화시키는 효과가 있어야 함
Input/Output(입출력)	반드시 입력이 주어지고 이러한 입력에 절차를 행한 실제 효과를 반영하는 출력이 있어야 함
Termination(종료성)	기술된 절차는 반드시 종료 상태에 도달해야 함

알고리즘의 종류로는

순차(Serial), 병렬(Parallel), 분산(Distributed) 등

여러 가지가 있습니다

지금부터 학습을 통해

하나씩 알아가야겠죠~

우선 맛보기로

옛날부터 널리 알려져 있는

대표적인 알고리즘 중의 하나인

유클리드(Euclid) 호제법을

C언어로 구현해보겠습니다

#include "euclid.h"

int gcd(int m, int n) {
    int r;
    while ( 1 ) {
        r = m % n;
        if ( r == 0 ) return(n);
        m = n;
        n = r;
    }
}

간단하죠~^^

그런데 위처럼 최대 공약수를

유클리드 호제법이라는

알고리즘으로 구했을 때

이것이 얼마나 정확한지와

이 프로그램이 얼마나 빠른지를

측정해야할 필요가 있습니다

바로 이런 이야기가

알고리즘의 정당성(Correctness) 입니다

정당성을 위한 조건에는

크게 두 가지가 있습니다

첫째로 어떠한 입력 데이터에 대해서도

틀린 답은 계산해 내지 않는다는 것이고

둘째로 어떠한 입력 데이터에 대해서도

유한 시간 내에 답을 내는 것입니다

여기서 어떠한 입력 데이터란

주어진 문제의 조건에 맞는

모든 데이터라는 의미로

가령 위의 유클리드 호제법에서

실수값이 들어왔을 때는

고려하지 않는다는 것입니다

일반적으로 어떤 하나의 문제에

알고리즘이 여러 개 존재할 수 있습니다

이럴 때는 빠르거나 메모리를

적게 이용해서 계산할 수 있으면

좋은 알고리즘이라하며

그 중 가장 중요한 척도로

복잡도(Complexity)가 등장합니다

복잡도에는 시간(time) 복잡도와

공간(space) 복잡도가 있으며

이를 평가하기 위해

점근적인 복잡도 평가를 사용합니다

점근적인 복잡도 평가는

입력 데이터의 개수 n의 값이

무한에 가까워졌을 때

중요 항 이외의 항을 무시하여

복잡도가 어떻게 되느냐에 주목합니다

또 점근적인 복잡도 평가를

간단히 하기 위해서

𝑂표기법(big-oh notation)과

Ω표기법(big-omega notation)을 이용합니다

𝑂표기법은 알고리즘이

이보다 늦지는 않다는 의미에서

복잡도의 상한(upper bound)을 제시하며

Ω표기법은 그 문제를 더 이상

빨리 해결할 수 없다는 의미에서

복잡도의 하한(lower bound)을 나타냅니다

참고로 𝜃표기법(big-theta notation)도 있는데 𝑂표기법이나 Ω표기법이
하한 또는 상한만을 나타내기 때문에
터무니 없는 함수로도
그 조건을 만족시킬수 있는 경우가 있고
이것이 유의미한 식인지 구분이 안갈때가 있어
그 둘 모두를 만족한다면
유의미한 식을 나타낸다고 보는 것입니다.
이해가 잘 안가더라도
앞으로 학습을 진행하면서
이해하면 될 것 같네요^^

더불어서 효율적인 알고리즘을 작성할 때는

개개의 연산 내용과

그 절차상의 개선만으로는

곧 한게점에 도달하게 되는데

이 때 필요한 것이

데이터를 컴퓨터 내부에서

어떻게 표현할 것인가를 나타내는

자료구조(data structure)입니다
자료구조에 대해서는
따로 학습을 할 필요가 있을 것 같네요~

아무튼 오늘은 알고리즘 학습

첫 시간으로

간단히 몇 가지 용어들과

대략적인 개념만 보았습니다

앞으로 학습을 진행하면서

필요한 내용을 채워보겠습니다

이것으로

오늘의 학습을 마치겠습니다

그럼 이만-_-