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

안녕하세요 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 화면

 

 

 

 

https://codingtest.goorm.io/

구름TEST - 개발자 채용을 위한 코딩 테스트, 프로그래밍 시험

 

구름테스트, 구름TEST 가 지원하는 프로그래밍 언어

 

그 외 Scala, Pascal, Lua, Objective-C, Rust, Cobol, Clojure, Smalltalk, Dart, Haskell, Perl, Common Lisp, D, Erlang 등 

 

 

 

구름테스트, 구름TEST 를 2019년 현재 적용중인 회사