알고리즘 문제 연습
[프로그래머스,Java] 최대공약수와 최대공배수(유클리드 호제법)
codi-3
2024. 7. 29. 16:00
이문제를 풀기 위해 유클리드 호제법을 사용했다.
유클리드 호제법의 따르면 최대 공약수(Greatest Common Divisor):
- 임의의 다른 두 자연수 Max & Min 가존제하고 Max> Min 일 때
- Max / Min의 나머지 값 즉 Max % Min을 R(remainder) 로정의하고
- 그 과정을 Min = 0 이 될 때까지 반복하며 Max와 Min 값을 업데이트해 준다
- Min = Max로 먼저 업데이트되며 Min = 나머지 값 R(remainder)로 업데이트해 준다.
최대공배수 (Greatest Common Multiple) 을구할때에는:
- 두자연수 Max와 Min 을곱한값을 위에 계산한 최소공약수로 나누어준다. (Max * Min) / GCD(Max, Min).

✏️작성 코드
- Min과 Max의 값을 Math.min 과 Math.max를 사용하여 정의 한뒤 위의 공식을 While반복문을 사용하여 풀어보았다.
class Solution {
public int[] solution(int n, int m) {
int[] answer = {n,m};
int min = Math.min(n, m);;
int max =Math.max(n,m);
//유클리드 호재
while(min != 0){
int r = max % min;
max = min;
min = r;
}
answer[0] = max;
answer[1] = (n * m) / max;
return answer;
}
}
이번문제는 어려운 문제는 아니었지만, 유클리드 호제법을 잘 알지 못한 상태였다면 난감했을 것 같다. 처음 문제를 봤을 때 어떤 로직을 사용할지 애를 먹었는데 구글링으로 유클리드 호제법을 찾아서 구현해 보니 쉽게 풀 수 있었다. 앞으로 나올 문제들 중 최대 공약수와 공배수가 적용되는 문제에 유용하게 사용할수있슬꺼같다.