안녕하세요! ryanhan입니다.
오늘은 최대공약수를 구하는 알고리즘인
유클리드 호제법에 대하여 이야기해보려고 합니다.
최대공약수는 초등학생때부터 배우는 아주 중요한 개념입니다.
최대공약수를 정의하자면,
0이 아닌 두 수가 있을 때, 둘을 동시에 나누는 최대의 수라고 할 수 있습니다.
이 최대공약수를 구하는 방법은 다음과 같습니다.
예를 들어, 105와 63이 있을 때,
두 개의 수를 동시에 나누는 수를 찾아 나눠봅니다.
위의 표처럼, 3과 7이 있다는 것을 알 수 있습니다.
그렇게 두 수를 동시에 나눈 3과 7의 곱인 21이 최대공약수가 됩니다.
그런데, 숫자가 매우 커지면 최대공약수를 구하기 굉장히 힘듭니다.
예를 들어, 7007과 2457의 최대공약수를 구하는 것은 힘듭니다.
두 수를 동시에 나눌 수 있는 수를 찾기 위한 과정이 복잡하기 때문입니다.
이럴 때는 유클리드 호제법을 이용하면 간단합니다.
유클리드 호제법은 7007과 2457을 동시에 나누는 수를 찾지 않습니다.
대신에, 두 수를 빼 봅니다.
이걸 수식으로 나타내면, 7007 – 2457 = 4550 이 됩니다.
여기서 생각해봅니다.
7007과 2457을 동시에 나누는 수는 4550도 동시에 나눠야만 합니다.
3의 배수끼리 빼면, 그 결과도 3의 배수인 것과 같은 원리입니다.
결국 이 논리를 이용하여,
(7007과 2457의 최대 공약수)=(4550과 2457의 최대 공약수)=
(2457과 2093의 최대공약수)= … = (182와 91의 최대 공약수) = 91이 됩니다.
이런 방식으로 최대공약수를 구하는 것이 유클리드 호제법입니다.
유클리드 호제법은 큰 수의 최대 공약수를 쉽게 구할 수 있게 만들어주었습니다.
이런 알고리즘은 어떻게 탄생할 수 있었을까요?
저는 ‘정의에 얽매이지 않는 것’이 핵심이었다고 생각합니다.
최대 공약수의 정의는 앞에서 소개 했듯이
‘두 수를 동시에 나누는 최대의 숫자’ 입니다.
이 정의에 얽매여 있었다면, ‘두 수’를 동시에 나누는 숫자만 찾고 있었을 것입니다.
유클리드 호제법은 ‘두 수’라는 정의에서 벗어나
‘두 숫자의 차이’를 생각해냈기에 탄생할 수 있었다고 생각합니다.
감히 말씀드려보자면, 스팀잇에서는 어떨까요?
스팀잇의 정의는 ‘생각의 가치’를 보장하는 커뮤니티라고 할 수 있겠습니다.
생각의 가치에 집중하는 것은 물론 중요합니다.
그것이 스팀잇이 추구하는 방향이니까요.
하지만, 스팀잇의 규모가 커지고, 글이 많아지면
생각의 가치를 보장하는 것은 점점 어려워질 것입니다.
이미 지금도 많이 어려워졌지요.
숫자로 치면 63과 105를 풀다가 7007과 2457을 만난 느낌입니다.
이럴 때일수록, 정의에 얽매이지 않고
약간 떨어져서 지켜보는 것이 필요하다고 생각합니다.
혹시, 더 합리적이고 간단한 방법이 있을지도 모르니까요.
오늘은 유클리드 호제법을 다뤄봤습니다.
긴 글 읽어주셔서 너무 감사합니다.
ryanhan이었습니다!
