[Java]goorm test(구름TEST) 유클리드 호제법

세상 개발/Java(SpringFramework)

[Java]goorm test(구름TEST) 유클리드 호제법

jinhongstar 2019. 8. 30. 14:27

728x90

안녕하세요 Leo 입니다.

이번 소개해줄 알고리즘 사이트는 구름TEST 라는 사이트 인데요,

NHN에서 투자 받아 개발한 알고리즘 사이트 입니다.

회사면접 코딩테스트를 하는 유명한 사이트죠...

저는 IOS (Object-c , Swift) 위주로 개발을 하고 가끔 안드로이드 개발을 하는데요...

회사에서 Java 로 코딩테스트를 하라고 해서 ... 하라면 해야죠... 풀어봤습니다.

제가 20문제 이상 푼것 같은데 이걸 공유 해드리도록 하죠...

이 글이 누군가에겐 "약"이 되고 누군가에겐 "독"이 될 것이다.

개발자라면 적어도 기본 알고리즘 정도는 스스로 학습하여 풀어봐야 한다.참고로 코딩테스트 문제를 제출 한 심사위원 분도제 블로그에서 답을 확인 한다는 것을 역으로 알아두고 보세요!! ㅎㅎ

알고리즘 문제

문제 : 유클리드 호제법은 a, b, q, r 이 정수라고 가정할 때

a = b * q + r => gcd(a,b) = gcd(b,r)

a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 원리를 이용하여 최대공약수를 구합니다.

gcd(a, b)에서 만약 b가 0이 되면 a가 처음에 주어진 수의 최대공약수가 됩니다.

예를 들어 108 과 72 의 최대공약수를 구한다면

gcd(108, 80) = gcd(80, 28) = gcd(28, 24) = gcd(24, 4) = gcd(4, 0)

이므로 최대공약수는 4가 됩니다.

두 수를 입력하였을 때 유클리드 호제법을 이용하여 최대 공약수를 출력하는 프로그램을 작성하십시오.

입력

두 양의 정수

출력

두 양의 정수의 최대 공약수

입/출력 예시
⋇ 입출력 형식을 잘 지켜주세요.
␣ : 공백
↵ : 줄바꿈
−⇥ : 탭
보기 입력 1
12 18
출력 1
6

보기 입력 2
6 8
출력 2
2

======================================================================================================

풀이

======================================================================================================

//Please don't change class name 'Main'
import java.util.Scanner;
/**

	어려운 문제는 무조건 이해하고 넘어가야한다.
	유클리드 알고리즘 최대공약수를 구하는 공식
	최대공약수는 두수의 공약수 중에서 최대인 수


	이건 문제가 이해가 너무 어렵다.
	
	내가 해석한 내용은
	더 단순한데 a b 의 큰값을 찾아서 큰값 에서 작은 값을 뺀다 
	작은값보 다 작아지면
	a b 둘중 큰값을 찾아 치완한다. b가 더 크다면
	다시 a b 의 작은 값 보다 작아질때 까지 빼다 보면 0이된다
	그러면 a b 둘중 0이 아닌 다른 값이 정답.
	

*/


class Main {

  public static void main(String[] args) {

		String number;
		Scanner scan = new Scanner(System.in);
		
		number = scan.nextLine();
		
		String[] numArr =	number.split(" ");
		
		int a = Integer.parseInt(numArr[0]);
		int b = Integer.parseInt(numArr[1]);

		int temp;
			
		while(a != 0){
				
			if( a < b){
					temp = a;
					a = b;
					b = temp;
					
			}
			
			a = a - b;
			
		}
		
		
		System.out.print(b);			
		
  }
}

참고로 저는 알고리즘 풀이 점수는 높은 점수는 아닙니다.

일단 푸는 거에 집중했습니다. 알고리즘에 정답은 없습니다.

더 좋은 알고리즘을 만들어 내는게 목표 입니다.

알고리즘에 대하여 더 이야기 하실분은 댓글남겨주세요!

구름TEST 화면