[04강] 유클리드 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 유클리드 알고리즘에 대해 알아보겠습니다.

 

목차

1. 유클리드 알고리즘
2. 실제 문제에서 유클리드 알고리즘

 

 

유클리드 알고리즘

유클리드 알고리즘은 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘입니다.

유클리드 알고리즘은 유클리드 호제법을 코드로 구현했다고 생각하면 됨.

유클리드 알고리즘 Logic

자연수 A, B (A > B) 에 대해 아래의 과정을 반복합니다.

 

ㆍ tmp 에 A 를 B 로 나눈 나머지를 할당합니다.

ㆍ A 에 B 를 할당합니다.

ㆍ B 에 tmp 를 할당합니다.

 

ㆍ 만약, B 가 0 이면 A 를 최대공약수로 하고 프로그램을 종료합니다.

 

 

[A=32, B=6 인 경우]

step1)
ㆍ tmp 에 A(32) 를 B(6) 로 나눈 나머지(2)를 할당합니다.
ㆍ A 에 B(6) 를 할당합니다.
ㆍ B 에 tmp(2) 를 할당합니다.
ㆍ B(2) 는 0 이 아니므로 종료하지 않고 step2로 이어갑니다.

현재 상태 : A=6, B=2

step2)
ㆍ tmp 에 A(6) 를 B(2) 로 나눈 나머지(0)를 할당합니다.
ㆍ A 에 B(2) 를 할당합니다.
ㆍ B 에 tmp(0) 를 할당합니다.
ㆍ B(0) 는 0 이므로 A(2) 를 최대공약수로 하고 프로그램을 종료합니다.

따라서, 32와 6의 공약수는 2이다.

 

위의 'Example 보기'에서 나온 예시를 코드로 구현하면 다음과 같습니다.

 

 

유클리드 알고리즘의 시간 복잡도는 $O(log \ N)$으로 매우 짧음.

 

 

 

실제 문제에서 유클리드 알고리즘

실제 문제에서 유클리드 알고리즘이 쓰이는 경우는 최대공약수(GCD)를 구할 때 쓰면 됩니다.

유클리드 알고리즘을 써야 하는 상황의 카테고리를 다음과 같이 3가지로 나누어 설명하겠습니다.

 

ㆍ 최대공약수(GCD)

ㆍ 최대공약수(GCD)의 성질

ㆍ 알고 보니 최대공약수(GCD)

 

최대공약수(GCD)

단순하게 최대공약수를 구하는 문제에 해당합니다.

[관련 문제] 백준 : 최대공약수 (1850번)

 

최대공약수(GCD)의 성질

최대공약수의 성질을 이용하는 문제입니다.

최대공약수의 성질은 크게 최소공배수(LCM)와의 관계와 재귀적 성질로 나눌 수 있습니다.

 

[최소공배수(LCM)와의 관계]

자연수 A, B 에 대해, 두 수의 최대공약수 G 와 최소공배수 L 은 다음 식을 만족합니다.

A x B = G x L

따라서, 최대공약수를 알면 최소공배수를 구할 수 있음.

[관련 문제] 백준 : 최소공배수 (13241번)

 

[재귀적 성질]

자연수 A, B, C 에 대해서 다음식이 성립합니다.

gcd(A, B, C) = gcd(gcd(A, B), C)

gcd(A, B, C) : A, B, C의 최대공약수를 의미

 

이러한 특성을 이용하면, N 개의 자연수들의 최대공약수를 N-1 번의 최대공약수를 구하는 과정을 통해 구할 수 있음.

[관련 문제] 백준 : 검문 (2981번)

 

알고 보니 최대공약수(GCD)

이 경우는 문제가 최대공약수(GCD)를 구해서 풀리는 것뿐이지,

문제를 푸는 데에 있어 핵심은 최대공약수(GCD) 문제라는 것을 인지하는 데에 있습니다.

 

이러한 문제는 문제를 재해석하는 사고력이 필요하며,

문제마다 요구하는 사고력의 수준이 천차만별이기 때문에 문제의 난이도 차이가 심합니다.

 

이러한 문제를 풀기 위해서는 문제해결력을 키우는 것이 좋음.

[관련 문제] 백준 : 숨바꼭질 6 (17087번)

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7