가방끈이 짧다는 건 핑계다.
오늘 알고리즘 문제를 풀면서 느꼈다.
우리가 살아가는 지금 이 세상은 컴퓨터와 인터넷만 있다면 원하는 것을 어떤 분야든지 찾아보고 배워나갈 수 있는 환경이 됐다는 걸 새삼 느꼈다.
배우려고 노력하면 배울 수 있다는 게 많다는 걸 알았다.
필요하지 않아서, 배우기 싫어서, 다른 할 것이 많아서라는 이유만으로는 더이상 핑곗거리가 되지 않는다.
이젠 필요한 모든 것을 배워서 쓸 줄 알아야 하는 때가 왔다.
갑자기 뜬금없지만 이런 얘기를 하는 이유는 오늘 배운 이것 때문이다.
'유클리드 호제법'
간단하지만 나에겐 생소했다.
최대공약수와 최소공배수를 이렇게 쉽게 찾을 수 있다고?
이런 방법을 왜 이제야 알았지?
하긴, 지금까지 살아오면서 이렇게 써먹을 데가 없었으니까!
두 수의 최대공약수를 구하는 문제를 풀기 위해 나는 처음에
두 수들의 모든 약수를 구해서 배열에 나열한 후
배열의 값들을 하나하나 비교해가며 찾으려고 했다.
답은 나올 수 있었지만 너무너무너무너무 비효율적이었다.
그래서 효율적인 방법을 생각해보려고 했는데 쉽지 않았다.
검색을 해보니 '유클리드 호제법'을 찾아냈다.
유클리드 호제법은 서로소라는 개념을 알고 있어야한다.
간단하게, 서로가 공통된 약수가 없는 소수인 관계를 서로소라고 한다.
이 서로소 개념을 통해 최대공약수를 찾는 유클리드 호제법이 증명될 수 있었다.
이것까지 설명할 필요는 없어보이니 본론으로 넘어가자면,
큰 수 A에서 작은 수 B를 나눴을 때의 나머지 R이 있다고 치자.
그림 발퀄로 직접 그렸음...
이 때, A & B 의 최대공약수는 B & R 의 최대공약수와 같다는 성질을 갖는다.
이 성질을 이용하면, B를 큰수로, 나머지 R을 작은 수로 취급하면서 재귀함수의 흐름처럼
나머지가 0이 되었을 때 그 몫이 최대공약수가 된다.
이걸 이용해서 이렇게 코드를 작성할 수 있게 되었다.
let a = 144;
let b = 280;
function solution1(a, b) {
let r; //나머지 r
while((a % b) > 0){ //나머지가 0보다 크다면 나눌 수 있으므로
r = a % b; // 다음 계산 때 b에 넣어줄 나머지 r
a = b; // 다음 계산 때 a에 넣어줄 b
b = r;
}
return b;
}
function solution2(a,b){
return a * b / solution1(a,b);
}
console.log(solution1(a,b)); // 8; a와 b 사이의 최대공약수 출력됨
console.log(solution2(a,b)); // 5040; a와 b 사이의 최소공배수 출력됨알고리즘 문제들을 차근차근 하나씩 풀다보니 점점 수학에 대한 중요성을 느끼게 되었다.
내일부터는 수학공부 좀 같이 병행해야 할 것 같다.
Math 함수에 들어있는 메서드들을 자주 사용할 것 같아 오늘 쓰면서 익혔던 것들을 정리해보려고 한다.
Math.ceil(x) : x의 올림값 반환
Math.floor(x) : x의 내림값 반환
Math.round(x) : x의 반올림값 반환
Math.pow(base, exponent) : base^exponent 제곱수 반환
-> ( Math.pow(b,e)는 b**e로도 쓸 수 있다. )
아스키코드값으로 변환하고 다시 문자로 변환하는 메서드도 배웠다.
let char; char.charCodeAt() : char의 아스키 코드값을 반환
String.fromCharCode(number) : 아스키 코드값 number에 해당하는 문자 반환
String.fromCharCode(num, num, num, 0x61) : 10진수,16진수를 이용해 문자열을 만들 수 있다.
-> (0 ~ 0xFFFF(65535)까지)
문자열을 잘라내거나 필요한 부분만 골라쓰거나 배열로 변환하거나 다시 문자열로 변환하는 메서드들도 익숙해지기 위해 공부하면서 사용했다.
string.split("str") : 해당 string을 "str"마다 쪼개어 배열로 반환한다.
array.reverse() : 해당 array배열의 요소들을 반전시킨 배열을 반환한다.
(요소마다 해당 인덱스가 앞 뒤로 반전됨)
let arr = [1, 2, 3, 5, 6];
arr = arr.reverse();
console.log(arr); // [6, 5, 3, 2, 1]array.join("str") : 문자열이 담긴 해당 array배열의 요소들을 str로 묶어서 문자열로 반환해준다.
let strArr = ['a', 'p', 'p', 'l', 'e'];
strArr = strArr.join("-");
console.log(strArr); // a-p-p-l-e한 두 번씩 배웠던 것들도 다시 배우면 잊어먹었다가 생각이 나는 경우가 있다.
열심히 해보자.
