[1일 1 알고리즘] D+2 - 유클리드 호제법

프로그래머스 문제

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

프로그래머스

---

과정

아래에는 문제 스포가 있을 수 있습니다.

 

프로그래머스 문제

처음 문제를 읽고 배열 방식으로 해야겠다. 분수니까.. 라는 생각이 처음으로 들었다.

 

이때까지만해도 아직 문제의 방향성이 갑자기 막 떠오르진 않았다.

 

1. 너무나도 정석대로 numer1/denom1 * numer2/denom2 를 실행했다.

    당연하게도... 값은 나오지만 기약분수처리가 되지 않는 상황이 발생..!

 

2. 기약분수 처리를 위해서 대표적으로 나눠지는 "최대 공약수를 구해야겠다!" 라는 생각이 들었다.

    그렇게 머리속에 스쳐가는 2, 3, 5, 7, 11, 13 인 서로소들이 스쳐지나갔다. 이녀석들이 1000까지 총 몇개가 있을까..?

    이건 이렇게 접근하면 안된다...

 

3. 기약분수 처리까지는 확고하다는 생각이 들었고, 제일 먼저 내가 모르는 JS에서 최대공약수 또는 Math 함수가 있는가를 검색해서 찾아보았다. 당연하게도 없었고, 어쩌다보니 유클리드 호제법을 알게되었다.

 

---

유클리드 호제법

- 두 수의 최대공약수를 찾는 가장 간단하고 효율적인 방법이다.

 

이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라고 한다.. ㄷ

 

function gcd(numer, denom) {
        while (denom != 0) {
            let r = numer % denom;
            numer = denom;
            denom = r;
        }
        return numer;
    }

위의 코드는 반복문을 사용한 유클리드 호제법이다.

 

분모와 분자를 하나의 인자로 삼아 반복문에 넣는다. 이때 임의의 r은 둘의 나머지값을 저장한다.

이후 분자 변수에 분모값을 저장한다. 그런 뒤에 아까 나머지인 r 변수의 값을 분모 변수에 저장한다.

numer = 400
denom = 150
이라고 가정할때,

첫번째 시작 반복에서
r = 100
numer = 150
denom = r = 100

두번째 반복
r = 50
numer = denom = 100
denom = r = 50

세번째 반복
r = 0
numer = 50
denom = r = 0

네번째 반복
denom이 0값이니까 반복문 종료
numer = 50으로 종료되므로 최대공약수는 50이다.

 

위와 같이 계속 반복하여 최대 공약수를 구할 수 있다.