Search
Duplicate
🤔

[개잡다] 최초의 알고리즘은 무엇일까?

간단소개
개발 잡학을 다룹니다.
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
개발지식
잡지식
태그
개발지식
잡지식
Scrap
8 more properties

[개잡다 : 개발 잡학을 다룹니다]

2. “최초의 알고리즘은 무엇일까요?”

사실 이 질문에 대한 답은 명확할 수 없습니다. 질문이 모호하니까요.
‘어떤 것을 알고리즘으로 볼 것인지’에 대해서는 조금 뒤로 하고 고대 이집트와 나일강 얘기를 해보려고 합니다.
△ 크고 아름다운 나일강의 범람원!
고대 이집트에서는 나일강의 주기적인 범람으로 인해 수해가 이만저만이 아니었습니다.
이집트인들은 나일강의 범람에 대한 피해를 최소화하기 위해 나일강이 얼마정도 범람하는 지를 예측하고 측량하기 시작했습니다. (역설적이게도 수해 덕분에 고대 이집트에서는 수학과 기하학이 발달하게 됐죠)

나일강의 범람과 같이 보는 고대 이집트의 수학, 과학

 첫째 | 이집트인들에게는 나일강의 범람 시기를 정확히 알아내 미리 준비하고 피해를 줄이는 것이 일이었습니다. 그래서 그로 인해 역학이 발달하여 일찍부터 달력을 사용하기 시작했습니다.
 둘째 | 나일강을 잘 다스려 생활에 도움이 되도록 여러 가지 기술을 정비할 필요가 있었습니다. 운하를 파서 수문을 만들고 범람에 대비해 제방과 둑을 쌓아야 했기 때문에 토목 관련 일도 활발하게 진행되었습니다. 그리하여 나중에는 피라미드까지 건설하게 되었습니다. 이집트 사람들은 각뿔대와 피라미드의 부피를 계산하는 방법을 알고 건축에 적용할 수 있는 탁월한 능력을 갖추기까지 했습니다.
 셋째 | 나일강의 범람 이후 농토를 정리하고 세금을 징수하는데 토지 넓이를 측량하는 기술이 발달하였습니다.
(출처 : 수학과 기하학, 이집트 피라미드와의 만남(링크))
따라서 알고리즘의 뜻을 ‘문제를 해결하기 위한 규칙과 방식'으로 확장한다면, 나일강의 범람이라는 문제를 해결하기 위해 나일강이 범람하는 넓이를 계산하는 이집트인들의 수학과 기하학은 알고리즘으로 볼 수 있겠죠?
그렇지만, 보통 ‘최초의 알고리즘’으로 자주 언급되는 알고리즘은 ‘유클리드 호제법’이라는 알고리즘입니다.
참고로 유클리드는 기원전 4세기 중반에 태어난 고대 그리스 수학자입니다. 피라미드가 지어진 시기가 기원 전 2600년이니, 잠깐 시간을 2천년 후로 돌려봅시다.
라파엘로의 <아테네 학당>
위의 그림에서 우측 하단에 있는 대머리 아저씨가 유클리드입니다.
확대해서 보면 삼각형 두 개가 그려진 흑판과 콤파스로 제자들에게 무언가를 가르치고 있네요.
이 유클리드라는 대머리 아저씨는 ‘유클리드 기하학’이라는 이름으로 유명합니다. ‘기하학(geometry)’이라는 단어는 ‘땅(geo)을 측정하다(metrein)’에서 어원을 찾을 수 있고, 기하학은 앞서 말씀드린 이집트 범람원 측정과 밀접한 관계가 있습니다.

그래서 최초의 알고리즘으로 불리는 유클리드 호제법은?

유클리드 호제법을 간단히 설명하면 ‘어떤 수들의 최대공약수(Greatest Common Divisor, a.k.a. GCD)를 구하는 방법’입니다.
요는 이렇습니다.
1. 최대공약수를 구하고 싶은 수의 나머지 연산(mod, %)을 하고,
2. 나머지가 0이면 나머지 연산을 한 나눗수가 최대공약수
3. 아니라면 계속!(수들이 서로소라면 1이 남음)
놂에 절여진 코드
이렇게 C로 간단하게 구현할 수 있습니다!

이미지로 보는 유클리드 호제법의 원리

알고리즘이라고 말하기도 거창할 정도로 간단합니다. 그래서 이게 무슨 도움이 될까요?
유클리드의 일화를 인용하겠습니다.
어느 날, 유클리드의 제자가 유클리드에게 물었습니다.
"이렇게 딱딱한 정리들을 배워서 무엇을 얻을 수 있습니까?"
그러자 유클리드는 노예 한 명을 불러서 이렇게 말했습니다.
"저자에게 동전 한 닢을 던져 주어라. 저놈은 자신이 배운 것으로부터 반드시 본전을 찾으려는 놈이다."
저 대머리 아저씨는 저렇게 얘기했지만, 우리 역시 취직이라는 문제를 해결하기 위해 알고리즘을 공부하니, 우리의 알고리즘 공부 역시 ‘먹고 삶이란 문제를 해결하기 위한 알고리즘'이 아닐까요?

결론