AI 요약관련 정보

• 문제 정의 및 기본 원리: 두 양의 정수 중 큰 수에서 작은 수를 반복적으로 빼서 한 수가 0이 될 때까지의 연산 횟수를 세는 문제입니다. 🔢
• 종료 조건의 수학적 증명: 모든 양의 정수는 이 연산을 통해 반드시 0에 도달합니다. (귀류법 설명) 숫자가 음수가 될 수 없고 무한히 감소할 수 없으므로, 결국 두 수가 같아지거나 한 수가 0이 됩니다. ♾️
• 효율적인 연산 (모듈로 연산): 반복적인 뺄셈 대신 모듈로(%) 연산을 사용하여 큰 수에서 작은 수를 최대로 뺄 수 있으며, 몫(//) 연산을 통해 해당 뺄셈 횟수를 한 번에 계산하여 연산 횟수를 효율적으로 추가합니다. ⚡
• 알고리즘 구현: 두 수가 모두 0이 아닐 때까지 반복하며, 큰 수에서 작은 수를 모듈로 연산하고 몫을 결과에 더하는 방식으로 진행됩니다. 💻
• 유클리드 호제법과의 연관성: 이 문제의 해결 방식은 두 수의 최대공약수(GCD)를 구하는 유클리드 호제법과 본질적으로 동일합니다. 🤝
• 코드 최적화: num1이 항상 num2보다 크거나 같도록 스왑하는 로직을 추가하여 if/else 분기 없이 코드를 간결하게 만들 수 있습니다. 🔄
• 시간 복잡도: O(log(min(num1, num2)))로, 유클리드 호제법과 동일하게 각 단계에서 숫자가 최소 절반으로 줄어들기 때문에 매우 효율적입니다. ⏱️