[220110] Lv.1 / 최소공배수, 최대공약수 구하기

문제 사이트 링크 : https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

 

---

문제인식 : 이건 뭐 어디 에?

종이랑 펜을 주면 풀 수 있고, 간단한건 암산으로도 풀 줄 아는데 막상 컴퓨터한테 설명하려니 머리가 터질거같았다. 최대공약수 개념을 학교에서 배운대로 작성하자니, 인간은 나누다가 어느정도 되면 멈추는데 컴퓨터는 멈추지 않잖아??? 이거 뭐 어케해야...????

그래서 인간의 방법을 포기하고 숫자를 무지성으로 때려박기로 했다. 구글링을 하다 찾은 좋은 함수.

 

새로 알게된 것들

Math.min() : 인자로 들어온 값 중에서 가장 작은 값 반환

Math.max() : 인자로 들어온 값 중에서 가장 큰 값 반환

Math.max.apply(null, num)은 Math.max(num[0], num[1]..)과 같다

 

드디어 입력창을 만드는 법을 알았다.

let arr = prompt('입력창 메세지')

 

apply : 이미 존재하는 함수를 호출할 때 다른 this 객체를 할당할 수 있습니다. this 는 현재 객체, 호출하는 객체를 참조합니다. apply 를 사용해, 새로운 객체마다 메소드를 재작성할 필요없이 한 번만 작성해 다른 객체에 상속시킬 수 있습니다.

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Function/apply#apply_%EC%99%80_%EB%82%B4%EC%9E%A5%ED%95%A8%EC%88%98_%EC%82%AC%EC%9A%A9

Function.prototype.apply() - JavaScript | MDN

 

---

내 풀이

function solution(n, m) {
	let gcd=0; //최대공약수 영어 줄임말
	for(let i=0; i<=n; i++){
		if((n%i==0)&&(m%i==0)) gcd=i;
        //동시에 0으로 나눠지면 gcd에 저장
        //가장 큰 수를 찾아야하니 마지막에 저장된 수를 들고 감
	}

	let lcm = 1; //최소공배수 영어 줄임말
	while(true){
		if((lcm % n == 0) && (lcm % m == 0)){
        //동시에 나눠서 나머지가 0이 되는 최소의 수를 찾음
		break;
		}
		lcm++;
	}

	let answer=[];
	answer[0]=gcd; answer[1]=lcm;
	return answer;
}

 

---

유클리드 호제법

2개의 자연수(또는 정식) a, b에 대해서

a를 b로 나눈 나머지를 r이라 하면(단, a>b)

a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

b를 r로 나눈 나머지 r'를 구하고

다시 r을 r'로 나눈 나머지를 구하는 과정을 반복

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

a와 b의 곱 / 최대공약수 = 최소공배수

이건 유클리드 호제법으로 푼 해결법이라고하는데 나는 아직 이해를 못 함. 좀 더 배우고 보면 이해하지 않을까 싶어서 우선 넣어놓겠다.

function gcd(a, b) {return b ? gcd(b, a % b) : Math.abs(a);}
//Math.abs() 주어진 숫자의 절대값 반환
function lcm(a, b) {return (a * b) / gcd(a, b);}
function gcdlcm(a, b) {
    return [gcd(a, b),lcm(a, b)];
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(gcdlcm(3,12));