PS/Programmers
[level1, 유클리드 호제법] 최대공약수와 최소공배수
1. 문제 2. 문제 해결 논리 문제 이해 주어진 것 int n, int m //임의의 두 자연수 요구되는 것 두 수의 최대공약수(GCD) 최소공배수(LCM) 데이터 구조 결정 유클리드 호제법 기본 원리 두 수의 GCD(최대공약수, Greatest Common Divisor)를 찾는 알고리즘 두 양의 정수 a와 b(a > b)가 주어졌을 때, a를 b로 나눈 나머지 r과 b의 GCD는 같다 얻어진 b와 r(b > r)로 b를 r로 나누면 나머지 r2와 r의 GCD는 같다 이와 같은 작업을 반복하여 나머지가 0이 되는 시점에서 나누는 수가 GCD 방법 1. 반복문 사용 방법 2. 재귀 호출 사용 코드가 간결하고 이해하기 쉬움 재귀 호출 횟수가 매우 많아지면 스택 오버플로우가 발생할 가능성이 있음 방법 3...
