관리 메뉴
목록2025/08/29 (1)
개발자공부일기
유클리드 호제법
백준 https://www.acmicpc.net/problem/1934를 유클리드 호제법으로 풀던 와중 코드를 잘 썼다고 생각했는데 정상작동하지 않았습니다.그래서 유클리드 호제법에 대해 다시 정리하며 제가 실수한 부분을 다시 살펴보려 합니다. 두 정수 a, b의 최소공배수(LCM)를 구하려면 보통 최대공약수(GCD)를 먼저 구한 뒤LCM(a, b) = a × b / GCD(a, b) 공식을 씁니다.이때 핵심이 되는 게 유클리드 호제법이고, 재귀식은 다음 한 줄로 요약됩니다.gcd(a, b) → gcd(b, a % b) 유클리드 호제법의 이론1.큰 수를 작은 수로 나누는 MOD 연산을 수행한다.2.앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD연산을 수행한다.3.2를 반복하며 MOD연산의 결과가 0..
코딩테스트/알고리즘
2025. 8. 29. 16:54