320x100
알고리즘은 보다 나은 회사로 가기위한 방법으로 오늘부터 공부하기로 했다.
그리고 첫 강의때 배우게 된 것이 "유클리드 최대공약수 구하기"인데
이것을 배우면서 의문이 생겼다.
#1 개요
선생님이 알려주기로는 유클리드 최대공약수를 풀때
32, 24라는 두개의 숫자가 있으면
큰수에서 작은수를 빼주되 유동적으로 빼주고
어느 한 쪽이 0이 되면 그 바로 전의 숫자가 최대공약수다. 라는 식으로 알려주셨다.
과정은
1)
32, 24
2)
(32-24), 24 -> 8, 24
3)
(24-8), 8 -> 16, 8
4)
(16-8), 8 -> 8, 8
5)
(8-8), 8 -> 0,8
이 되기때문에 8이 최대공약수라고 한다.
#2 의문
그렇지만 내가 설정한 두 수가 29, 19라고 하면
1)
(29-19), 19 -> 10, 19
2)
(19-10), 10 -> 9, 10
3)
(10-9), 9 -> 1,9
4)
(9-1), 1 -> 8, 1
여기서부터 계속 1단위로 좁혀가면서 결국은 1,0이 된다.
그러면 29와 19의 최대공배수는 1인가? 뭐... 맞는말이긴 하다.
최대공배수가 2이상인 수여야지 우리가 아는 최대공약수로써의 의미가 있는 것이고
사실 따지고 보면 1도 최대공약수가 되는게 맞긴하지
음.. 결론적인 해답은 얻었으나 뭔가 찜찜한 느낌.. 인것같다
300x250