[C 언어] 최초의 알고리즘

 

 

 

최초의 알고리즘으로 가장 오래된 알고리즘으로 자주 언급되는 것은 기원전 300년경에 만들어진 유클리드의 '최대공약수를 찾는 알고리즘'입니다. 최대 공약수는 2개 이상의 자연수의 공약수 중에서 가장 큰 수를 말합니다.

 

유클리드는 2개 자연수의 최대 공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대 공약수와 같다는 성질을 이용하여 최대 공약수를 찾는 알고리즘을 만들었습니다.

​

예를 들어 24와 14의 최대 공약수는 큰 수에서 작은 수를 뺀 10(=24-14)과 14와의 최대공약수와 동일합니다. 단, 0과 어떤 수 n의 최대공약수는 n이 됩니다.

​

 

최대공약수 (24,14)

= 최대공약수 (24, -14, 14) = 최대공약수(10, 14)

= 최대공약수 (14, -10, 10) = 최대공약수(4, 10)

= 최대공약수 (10 - 4, 4) = 최대공약수(6, 4)

= 최대공약수 (6 - 4, 4) = 최대공약수(2, 4)

= 최대공약수 (4 - 2, 2) = 최대공약수(2, 2)

= 최대공약수 (2 - 2, 2) = 최대공약수(0, 2)

= 2

​

---

 

 

이 포스트는 학부에서 제공하는 기본적인 컴퓨터 공학 강의와 책들을 토대로 알기 쉽게 내용을 작성하였습니다. 하지만 계속 더 유익하고 논문 및 전문 서적을 읽어가며 더 추가돼야 할 내용이 있으면 C 언어 프로그래밍 포스트와 콘텐츠들을 계속 고도화하는 방식으로 진행하려고 합니다.

​

#컴퓨터공학 #C언어 #C언어프로그래밍 #프로그램 #알고리즘 #컴퓨터의문제해결 #프로그래밍언어 #공대공부 #유클리드알고리즘 #최대공약수찾는알고리즘