안녕하세요! 오늘은 코딩테스트를 준비하는 여러분을 위해 “최대 공약수”를 구하는 알고리즘 문제를 다뤄보겠습니다. 최대 공약수를 적절하게 계산하는 것은 여러 문제에서 필수적으로 필요하며, 특히 수학적 사고와 알고리즘적 사고를 동시에 요구하는 문제입니다. 이번 시간에는 함수형 프로그래밍 기법을 사용할 것이며, Python 언어를 이용해 실습할 것입니다.
문제 설명
두 개의 정수 a, b가 주어질 때, 이 두 수의 최대 공약수를 구하는 프로그램을 작성해 주세요. 최대 공약수(Greatest Common Divisor, GCD)는 두 정수의 공통된 약수 중에서 가장 큰 수를 의미합니다.
입력
- 첫 번째 줄에 두 개의 정수
a,b(1 ≤a,b≤ 109)가 주어진다.
출력
- 정수
GCD(a, b)를 출력한다.
예제
다음은 몇 가지 예제입니다:
예제 1: 입력: 60 48 출력: 12 예제 2: 입력: 101 10 출력: 1 예제 3: 입력: 17 17 출력: 17
문제 해결 방법
최대 공약수를 구하는 방법 중 가장 유명한 방법은 유클리드 호제법입니다. 이 방법은 다음과 같은 원리에 기반합니다:
- 두 수
a와b의 최대 공약수는b와a를b로 나눈 나머지r의 최대 공약수와 같다. 즉,GCD(a, b) = GCD(b, r)이다. - 이 과정을 반복하여
r가 0이 될 때까지 진행하면, 마지막에 남은b가 최대 공약수이다.
유클리드 호제법 구현
이제 이제 유클리드 호제법을 파이썬 코드로 구현해보겠습니다. 아래 코드는 최대 공약수를 계산하는 함수를 정의한 예시입니다:
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
이 함수는 반복문을 사용하여 b가 0이 될 때까지 계속해서 두 수의 값을 교체하며 나머지를 계산합니다. 최종적으로 남는 a가 최대 공약수가 됩니다.
코드 실행 예
입력을 받아 실행하는 메인 코드를 작성하겠습니다:
if __name__ == "__main__":
a, b = map(int, input("두 수를 입력하세요: ").split())
result = gcd(a, b)
print(f"최대 공약수: {result}")
결론
이번 글에서는 최대 공약수를 구하는 문제를 통해 유클리드 호제법의 원리를 배우고, 실제로 파이썬으로 구현해보았습니다. 이 문제는 다양한 응용이 가능하며, 다른 알고리즘 문제를 풀 때도 같은 원리를 적용할 수 있습니다. 알고리즘 문제를 해결하는 과정에서 수학과 프로그래밍의 조화를 경험해 보시길 바랍니다.
꼭 마무리로 말씀드리고 싶은 점은!
코딩테스트 준비의 기본은 다양한 문제를 많이 풀어보는 것입니다. 많은 문제들을 풀어보시고, 복습하시는 과정을 통해 코딩 실력을 한층 더 발전시킬 수 있을 것입니다. 감사합니다!