알고리즘이란?

*알고리즘이란?

 

- 알고리즘(algorithm) : 주어진 문제를 해결하는 절차(procedure)

- 각 단계는 기본적인 연산(operation) 하나로 이루어져 있을 수도 있고, 혹은 다른 부분 문제(subproblem)에 대한 알고리즘일 수는 있찌만 충분히 구체적이어야 함.

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

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

- 가능한 입력에 대하여 항상 종료하고 옳은 답을 출력하면 알고리즘이 되지만, 실행시간이 빠르고 또한 메모리를 적게 쓰는 알고리즘을 선호하게 됨.

- 다시 말하면 자원(resource)을 적게 쓰는 알고리즘이 좋은 알고리즘.

- 자원은 주로 실행시간을 말하는 시간 자원과 메모리 사용량을 말하는 공간 자원을 말함.

• 시간 자원 : 알고리즘의 실행시간이 얼마나 빠른가?
• 공간 자원 : 알고리즘이 메모리를 얼마나 필요로 하는가?

- 최대공약수를 구하는 문제에 대하여 실행시간이 빨라서 효율적인(efficient) 알고리즘이 있음. -> 유클리드 알고리즘 (유클리드 호제법)

- 유클리드 알고리즘 : 인류 최초의 알고리즘

(유클리드 정리) 두 정수 m, n에 대하여, 만약 m ≥ n이고 m을 n으로 나눈 나머지를 r(0 ≤ r < n)이라고 하면 gcd(m, n) = gcd(r, n)이다.

 

예)

(a) gcd(72, 90) = gcd(72, 18) = gcd(0, 18) = 18.
(b) gcd(42, 16) = gcd(10, 16) = gcd(10, 6) = gcd(4, 6) = gcd(4, 2) = gcd(0, 2) = 2.

 

// Euclidean algorithm 
 
#include <stdio.h>
 
int gcd(int m, int n) // It is assumed that m <= 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);
}

*gcd(n, 0) = n이라는 사실에 유의!

 

- 라메(Gabriel Lame)의 정리에 따르면, 둘 중 작은 정수를 십진법 표현할 때 필요한 자리수의 5배 이하 단계를 거침.

  -> 알고리즘의 시간 복잡도를 분석한 최초의 사례로 인정되고 있음.

  -> 이하인 두 양의 정수의 최대공약수를 구하는데 5·20 = 100 단계가 지나면 끝남.