프로그래밍 기술/IT 이야기

알고리즘 이야기

언제나휴일 2016. 5. 1. 21:36
반응형

안녕하세요. 언제나 휴일, 언휴예요.
이번에는 알고리즘에 관한 이야기를 해 볼게요.


알고리즘은 9세기 페르시아 수학자 알콰리즈미(al khowarazmi)에서 시작하였다고 하네요. 알콰리즈미는 숫자를 상호 관계적인 개념으로 해석하면서 대수학의 아버지로 불리는 인물입니다.

그리고 본격적인 알고리즘은 유클리드(Euclid)의 호제법에서 출발했다고 합니다.

유클리드의 호제법은 다음과 같은 이론이예요.
자연수 a와 b가 있고 a  b이고 a%b = r일 때
r이 자연수이면 GCD(a,b) = GCD(b,r) 이고 r이 0이면 GCD(a,b) = b 이다. ( GCD, Greatest Common Divisor)

예를 들어 a가 36, b가 24일 때
36 % 24 = 12
GCD(36, 24) = GCD(24, 12)
24 % 12 = 0
GCD(24, 12) = 12
따라서 GCD(36, 24) = 12 라는 것을 말합니다.

이를 증명하는 것은 위키백과나 다른 자료를 참고하세요.

C언어로 작성하면 다음과 같아요.
int gcd(int a,int b)
{
    if(b)
    {
        return gcd(b, a%b);
    }
    return a;
}


P - NP 문제

인간의 뇌와 슈퍼 컴퓨터

지능형 에이전트(Intelligent agent)


반응형