[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 화면
구름TEST - 개발자 채용을 위한 코딩 테스트, 프로그래밍 시험
구름TEST는 LG전자, 라인, NHN, 스마일게이트 등에서 활용 중인 온라인 코딩 테스트 서비스입니다. 부서별, 직군별 시험 관리부터 문제 제작, 관리 기능과 응시자 초대 기능 등 개발자 채용을 위한 모든 기능을 제공합니다.
codingtest.goorm.io
구름테스트, 구름TEST 가 지원하는 프로그래밍 언어
그 외 Scala, Pascal, Lua, Objective-C, Rust, Cobol, Clojure, Smalltalk, Dart, Haskell, Perl, Common Lisp, D, Erlang 등
구름테스트, 구름TEST 를 2019년 현재 적용중인 회사