[Algorithm] 알고리즘이란?

알고리즘이란?

알고리즘의 개념

• 알고리즘(algorithm) : 주어진 문제를 해결하는 절차(Procedure)
• 각 단계는 기본적인 연산(Operation) 하나로 이루어져 있을 수도 있고, 혹은 다른 부분 문제(Subproblem)에 대한 알고리즘일 수는 있지만 충분히 구체적이어야 한다.

 

알고리즘의 조건

일반적으로 알고리즘은 다음의 두 조건을 반드시 만족해야 한다.

• 종료(termination) : 모든 가능한 입력 사례에 대하여 반드시 끝난다.
• 정확성(correctness) : 모든 가능한 입력 사례에 대하여 옳은 답을 출력한다.

 

좋은 알고리즘

• 자원(Resource)을 적게 쓰는 알고리즘이 좋은 알고리즘이라고 할 수 있다.
  • 가능한 입력에 대하여 항상 종료하고 옳은 답을 출력하면 알고리즘이 되지만, 실행시간이 빠르고 또한 메모리를 적게 쓰는 알고리즘을 선호하게 된다.
• 자원은 주로 실행시간을 말하는 시간 자원과 메모리 사용량을 말하는 공간 자원을 말한다.
  • 시간 자원 : 알고리즘의 실행시간이 얼마나 빠른가?
  • 공간 자원 : 알고리즘이 메모리를 얼마나 필요로 하는가?

 

알고리즘의 예 : 유클리드 알고리즘(유클리드 호제법)

• 최대공약수를 구하는 문제에 대하여 실행시간이 빨라서 효율적인(Efficient) 알고리즘
• 인류 최초의 알고리즘

 

유클리드 정리

• 두 정수 `m, n`에 대하여 만약 `m ≥ n`이고 `m`을 `n`으로 나눈 나머지를 `r (0 ≤ r < n)`이라고 하면 gcd(m, n) = gcd(r, n)이다.
  • 예) 
    • gcd(72, 90) = gcd(72, 18) = gcd(0, 18) = 18
    • gcd(42, 16) = gcd(10, 16) = gcd(10, 6) = gcd(4, 6) = gcd(4, 2) = gcd(0, 2) = 2
  • gcd(n, 0) = n 이라는 사실에 유의한다.

 

구현

#include <stdio.h>

// It is assumed that m <= n. 
int gcd(int m, int n) {
    if (m == 0) return n;
    else return gcd(n % m, m);
}

void main(void) {
    int m, n; 	// positive integers
    int result; // gcd of m and n
    scanf_s("%d", &m);
    scanf_s("%d", &n);
    if (m <= n) result = gcd(m, n);
    else result = gcd(n, m);
    printf("%d\n", result);
}

 

• 라메(Gabriel Lame)의 정리에 따르면, 둘 중 작은 정수를 십진법 표현할 때 필요한 자리수의 5배 이하 단계를 거친다.
  • 알고리즘의 시간 복잡도를 분석한 최초의 사례로 인정되고 있다.
  • 예) `10^{20}` 이하인 두 양의 정수의 최대공약수를 구하는데 `5×20 = 100` 단계가 지나면 끝난다.