유클리드 호제법 == 나눗셈 알고리즘으로 최대 공약수 구하기
작성자 : 뉴원 (Newon)
유클리드 호제법이란
두 정수 a, bﾠﾠ|ﾠﾠ a 와 b 의 최대공약수 𝒹 ﾠﾠ|ﾠﾠ a / b 했을 때 나오는 나머지 𝛾 ﾠﾠ|ﾠﾠ 이 있을 때
𝒹 = gcd(a, b) = gcd(b, 𝛾)가 성립함을 의미한다.
이때 gcd(a, b) 는 a 와 b 사이의 최대공약수를 뜻한다.
이때 𝒹 = gcd(a, b) = gcd(b, 𝛾) 를 확장해서 𝛾´이 b를 𝛾로 나누었을때의 나머지라고 한다면
𝒹 = gcd(a, b) = gcd(b, 𝛾) = gcd(𝛾, 𝛾´) ... 이 성립하게 된다.
이 성질을 이용해서 알고리즘에서 최대공약수를 구할 때 gcd 를 구하는 함수를 만들고, 이를 for 문이나 재귀함수로 반복해서 푸는 방법이 성립하게 된다.
이를 간단하게 코드로 작성하면 다음과 같이 나타난다.
fun Gcd(a:Int, b:Int):Int {
var r = a % b
if (r == 0)
return b
else
return Gcd(b, r)
}
fun main() {
val br = System.`in`.bufferedReader()
val (a,b) = br.readLine().split(' ').map {it.toInt()}
var gcd = Gcd(a,b)
println(gcd) // a 와 b 의 최대공약수
println(a*b/gcd) // a 와 b 의 최소공배수
/*
* 백준 2609, 최대공약수와 최소공배수 문제이다.
* 코틀린으로 작성되었다.
*/이게 왜 됨?
글의 본문이다. 왜 될까?
a, b, 𝛾(= a와 b의 나머지) 에는 무슨 관계가 있길래 gcd(a,b) 와 gcd(b,𝛾) 과 같고, 𝛾가 𝛾의 나머지(𝛾´) 의 최대공약수, gcd(𝛾, 𝛾´)와 같고
이걸 { ... } 반복해도 성립하게 되는걸까?
이게 왜 되는지 이해해보는 것이 이 글의 목표이다.
두 정수 a, b가 있고 a > b 이면서, 𝒹(최대공약수) 를 지니고 있는 수를 통해 알아보자. ﾠﾠﾠﾠﾠ ﾠﾠﾠﾠﾠ ﾠﾠﾠﾠﾠﾠ대전제 = a 와 b 의 최대공약수 𝒹
우선 우리는 a 와 b 의 최대공약수 𝒹를 알고 있으니, a 와 b 를 다음과 같이 바꿔본다.
a = 𝒹 * ⍺
b = 𝒹 * β
⍺와 β는 𝒹를 곱했을 때 각각 a 와 b 가 나오는 정수
그럼 우린 다음과 같이 쓸 수 있다.
a = q * b + 𝛾ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ//ﾠﾠq 는 a / b 의 목,ﾠ 𝛾 은 나머지이다.
𝒹 * ⍺ = q * 𝒹 * β + 𝛾ﾠﾠﾠﾠﾠﾠﾠﾠﾠ//ﾠﾠa 를 𝒹 ⍺로,ﾠ b 를 𝒹 β 로 치환했다.ﾠﾠﾠﾠ ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ⍺와 β는 조건을 만족하는 임의의 수
𝛾 = 𝒹 (⍺ - q * β)ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ//ﾠﾠ위의 식을 𝛾 과 나머지로 정리하였다.
𝛾 = 𝒹 * (⍺ - q * β)ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ//ﾠﾠ?!ﾠﾠ 𝛾 ﾠ로 정리하였더니,ﾠ 𝒹 (⍺ - q β) 의 형태이므로,ﾠ 𝛾 의 약수에도 𝒹 가 들어감을 알 수 있다 !!
올, 위와 같이 정리하였더니 우리는 𝛾 의 약수에 a 와 b 의 최대공약수인 𝒹가 있음을 알 수 있었다!!
그렇다면, 𝒹는 b 와 𝛾 의 최대공약수이기도 할까?
그렇다, 이것이 이 글의 핵심 주제 ①이다.
𝒹는 a 와 b 와 𝛾의 최대공약수가 참인지 거짓인지 확인하는 것이 오늘 주제의 핵심 주제 중 하나이다.
미리 스포하자면 핵심 주제는 핵심 주제 ② (crazy_𝛾은 언젠가는 0이 될 수 밖에 없다) 까지 있다.
우리는 현재 a 와 b 의 최대공약수가 𝒹 라는 것을 알고 있으며 𝛾 에도 𝒹라는 공약수가 들어간다는 것을 안다.
이때 𝛾 에게 있어서도 𝒹가 최대공약수가 된다면
우리는 a 와 b 와 𝛾 의 최대공약수가 𝒹 로 같다는 것을 알 수 있게 된다 !!
𝛾 의 최대공약수가 a와 b의 최대공약수인 𝒹 와 같다는 동화 .. 가능 ?
인생은 호락호락하지 않다, 그리고 우리는 𝒹가 𝛾의 최대공약수라고 확신할 수 없다.
확신할 수 없으니 𝒹 가 𝛾의 최대공약수가 아님 이라고 가정해보자.ﾠ
대 가정 = 𝒹 가 𝛾의 최대공약수가 아님
𝛾의 최대공약수가 𝒹 가 아니라면, 𝛾 의 최대공약수는 그 어떤 임의의 수 𝒹´ 일 것이다.
잠시 정리해서
- 𝒹 = gcd(a,b) 이고 𝒹´ = gcd(b, 𝛾) 이라면
- 𝒹´ 는 언제나 𝒹 보다 작아야한다.
조건 ① = (𝒹 < 𝒹´)
- 왜?
대 가정에 의해서 𝒹 는 𝛾 의 최대공약수가 아니고, 𝒹´ 가 𝛾 의 최대공약수이어야 하기 때문이다.
현재 우리는 대 가정과 조건 ①를 갖고 있다.
그럼, 𝒹´의 관점에서 b 와 𝛾를 다시 써보자.
b = 𝒹´ b´ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ//ﾠﾠb´은 b = 𝒹´ b´ 를 만족하는 수
𝛾 = 𝒹´ r´ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ//ﾠﾠr´은 𝛾 = 𝒹´ r´를 만족하는 수
이걸 위에서 사용했던 a = q * b + 𝛾ﾠﾠﾠ에 대입해보자.
a = q 𝒹´ b´ﾠ+ 𝒹´ r´ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ// b 와 r 에 𝒹´에서 본 b 와 r 를 넣었다.
a = 𝒹´ (q * b´ + r´)ﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠﾠ// 넣어본 김에 깔끔하게 𝒹´로 정리해보았다.
어 ? a 의 공약수에도 𝒹´가 들어간다.
하지만 알다시피, 대전제로 우리는 a 와 b 의 최대공약수 𝒹 라고 하였으며,
또 따라서 𝒹´는 𝒹 보다 작을 수 밖에 없다 !!
조건 ② = (𝒹´ < 𝒹)
? 조건 ① = (𝒹 < 𝒹´) 과 조건 ② = (𝒹´ < 𝒹) 이 모순된다.
문과인 나도 안다. 어떠한 정수 𝒹가 𝒹´ 보다 작으면서 클 수는 없다
그렇다면 잘못된 건 대 가정 = 𝒹 가 𝛾의 최대공약수가 아님 !!
해당 가정의 결론이 거짓이니, 그 가정의 반대는 참 ! 즉 𝒹 는 𝛾의 최대공약수임
따라서 우리는 a 와 b 와 𝛾 의 최대공약수가 𝒹로 같다. 는 이야기가 동화인 줄 알았지만
사실 팩트기반 실제 사례 기반 수필로써 핵심주제 ① : a 와 b 와 𝛾 의 최대공약수가 𝒹로 같다. 가 True임을 알 수 있었다.
ㅇㅋ, 근데 왜 a 와 b 와 𝛾 의 최대공약수가 같다고 그걸 저렇게 반복해도 성립하는거임?
그렇다, 우리가 핵심 주제 ① : a 와 b 와 𝛾 의 최대공약수가 𝒹로 같다. 라는 팩트를 갖고 있어도
우리는 코틀린 예제로 쓰인 저 코드가 잘 작동하게 되는 이유를 아직 찾지 못했다.
코드를 다시 한번 살펴보자
fun Gcd(a:Int, b:Int):Int {
var r = a % b
if (r == 0)
return b
else
return Gcd(b, r)
}
{ ... }Gcd() 는 나머지 𝛾 이 0이 될 때 모든 연산을 끝내게 된다.
다시 말하면 𝛾 은 유한한 횟수 안에 언젠가 0 된다는 것이다.
언젠가는 나머지가 0이 된다라는걸 확신하는 듯한 저 표정이 거만하기 짝이 없다. 저게 블러핑인지 아닌지 한번 확인해보자.
a / b 의 나머지가 𝛾 이듯, b / 𝛾 의 나머지가 𝛾´ 라고 말해보자.
핵심 주제 ① = 𝒹 는 a와 b 와 𝛾의 최대공약수임 에 따라서 gcd(a, b) = gcd(b, 𝛾) 이듯 gcd(b, 𝛾) 은 gcd(𝛾, 𝛾´) 이다.
..어 왜?
두 정수 a 와 b 를 다시 한번 살펴보자. (a > b), a 와 b 의 최대공약수를 𝒹 라고 할 때
a = q * b + 𝛾
gcd(a, b) = gcd(b, 𝛾)
a 와 b 의 최대공약수 == b 와 𝛾 의 최대공약수
마찬가지로 이번엔 위의 내용과 상관없이 순수하게 두 정수 b 와 r 을 살펴보자. (b > 𝛾)
b = q * 𝛾 + 𝛾´
gcd(b, 𝛾) = gcd (𝛾, 𝛾´)
b 와 𝛾 의 최대공약수 == 𝛾 와 𝛾´의 최대공약수
핵심 주제 ① = a 와 b 와 𝛾 의 최대공약수가 𝒹로 같다.에 따라서
- gcd(a,b) == gcd(b,𝛾) 인데
- gcd(b,𝛾) == gcd(𝛾, 𝛾´) 이니
- gcd(a,b) == gcd(𝛾, 𝛾´) 이다.
오, 그렇다면 𝛾´ 과 𝛾´´ 사이에도 최대공약수는 𝒹 이고 𝛾´´ 과 𝛾´´´ 에도 최대공약수는 𝒹 이고 𝛾´´´ 과 𝛾´´´´ 에도 𝒹 이고 { ... } 에도 𝒹
무한한 나머지와 그 나머지의 최대공약수는 언제나 a 와 b 의 최대공약수와 같다는 건 알겠지만, 혹시 𝛾´´´´´´{...}가 0이 안되면 어떻게 될까??
𝛾´´´´´´{...} 를 이제부터 crazy_𝛾이라고 불러보자.
나머지를 계속하다보면 언젠가는 우린 crazy_𝛾를 만나게 될텐데, 그때의 식은 다음과 같을 것이다.
b > 𝛾 > 𝛾' > 𝛾'' > 𝛾''' ... crazy_r != 0
우리는 기억해내야 한다, b 와 𝛾 도, 그 어떠한 crazy_𝛾 들도 모두 정수 라는 것을.
즉, crazy_𝛾 이 정수고, 0이 아니라면 less_crazy_𝛾과 crazy_𝛾로 나눠서 more_crazy_𝛾´라는 정수를 만들 수 있으니
b > 𝛾 > 𝛾' > 𝛾'' > 𝛾''' ... > lesscrazy𝛾 > crazy𝛾 > more_crazy𝛾 > morecrazy𝛾2 { ... }
가 성립함을 알 수 있고, 여기서 항상 crazy_𝛾은 crazy_𝛾 > more_crazy_𝛾를 성립하게 된다.
왜냐하면 more_crazy_𝛾는 crazy_𝛾의 나머지이니까.
정수가 언제나 앞의 숫자보다 작아진다면, 언젠가는 0에 도달하게 된다. 왜냐고? 그것이 정수이니까 (끄덕)
a > b 일 때, a 와 b 가 정수라면 a 와 b 차이의 최솟값은 1
a > b > b' 는 최소한 1씩 줄어드는 정수이며, 이게 계속해서 반복된다면 언젠가는 0에 도달하게 된다.
따라서 핵심주제 ② = crazy_𝛾은 언젠가는 0이 될 수 밖에 없다 !!
마지막으로 코드를 다시 한번 살펴보면
fun Gcd(a:Int, b:Int):Int {
var r = a % b
if (r == 0)
return b
else
return Gcd(b, r)
}
{ ... }var r 은 재귀함수로 돌아가며 계속해서 𝛾, 𝛾´, 𝛾´´, 𝛾´´´ {...} crazy_𝛾 이 된다 하더라도
핵심주제 ② = crazy_𝛾은 언젠가는 0이 될 수 밖에 없다에 의해서 언젠가는 0이 된다는 걸 할 수 있다.
그렇기 때문에, 위의 코드가 무한히 돌지 않고 유한한 횟수 내에서 나머지가 0인 순간을 찾을 수 있는 것이다.
결론
유클리드 호제법을 통해 우리는 다음과 같이
핵심주제 ① : a 와 b 와 𝛾 의 최대공약수가 𝒹로 같다.핵심주제 ② : crazy_𝛾은 언젠가는 0이 될 수 밖에 없다
가 성립함을 알 수 있었고, 이에 따라 Gcd(최대공약수)를 구하는, 소위 나머지 알고리즘라는 것이 성립함을 알 수 있었다.
즉 정수 a, b, 𝛾 이 있을 때
fun Gcd(a:Int, b:Int):Int {
var r = a % b
if (r == 0)
return b
else
return Gcd(b, r)
}와 같이 a 와 b 를 나눈 나머지 𝛾가 0이 될 때 까지
a = bb = r
을 반복하다보면 언젠가 최대공약수가 나온다는 것을 알게되었다.
Gcd 문제 푸는데 이걸 다 알아야 하냐고?
출처
brain from 감자 4호
알고리즘 공부하면서 알아본 내용입니다, 오류 • 오타 등 알려주시면 정말 감사하겠습니다 :)
