유클리드 호제법

1. 유클리드 호제법은 언제 쓰는 알고리즘인가

처음 코딩을 시작할 때 최대공약수를 구하는 문제를 푼적이 분명 있다.
2중 for문을 활용해서 2수를 모두 나머지 0으로 나눌 수 있는 가장 큰 값을 구하는 방법이었을 것 이다. 하지만 만약 두 수의 크기가 엄청나게 크다면 O(N2)으로 문제를 해결할 수 없다.

일반적으로 코딩테스트에서 N의 크기가 1,000,000이상이면 문제는 O(N2)으로 풀리지 않는다다. 그럴 때 유클리드 호제법을 사용하면 O((logN)2)의 시간으로 풀 수 있다.

2. 유클리드 호제법 사용법

유클리드 호제법은 다행이도 굉장히 쉬운 알고리즘이다. 단순히 나눈값을 나머지로 나누기만 계속하면 되는 방법으로 예를들어,
10002와 62의 최대공약수를 구한다고 가정했을 때 다음과 같은 순서로 최대공약수를 구할 수 잇다.

• 큰값 10002과 작은값 62 구하기
• 큰값을 작은값으로 나누기 10002 / 62 = 몫 + 20
• 작은값 62을 나머지 20로 나누기 62 / 20 = 몫 + 2
• 작은값 20을 나머지 2로 나누기 20 / 2 = 몫 + 0
• 나머지가 0이 된 순간 나눈값이 최대공약수이다

3. 코드

function gcd(a, b){
	// a가 b보다 큰 값이라고 가정
  	let temp;	
  	while(b){
      	temp = a%b;
    	a = b;
      	b = temp;
  	}
  	return a;
}

4. 유클리드 호제법을 사용해 풀만한 문제

https://school.programmers.co.kr/learn/courses/30/lessons/62048