이머시브 과정 3주차 2째날이다.
오늘은 어제 배운 알고리즘 파트를 이어서 배우는 날이었다.
오늘 배운것도 블로깅 하면서 다시 되짚어 보는 시간을 가지자 !
🔥Today Lesson🔥
- Algorithm with Math - GCD / LCM
- Algorithm with Math - 순열 / 조합
- Algorithm with Math - 멱집합
GCD / LCM 🐬
GCD와 LCM은 우리가 학교에서 자주 사용하던 최대공약수(GCD)와 최소공배수(LCM)을 말한다.
유클리드 호제법을 사용하여 자바스크립트로 GCD와LCM을 구현 해보자
유클리드 호제법이란?
"2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다."
최대공약수(GCD)
예를들어서 a = 648, b = 232로 가정해보자
1. 648 % 232 = 184
(232는 184로 나누어 떨어지지 않음 다시 나눔)
2. 232 % 184 = 48
184은 48로 나누어 떨어지지 않음 다시 나눔
3. 184 % 48 = 40
48은 40으로 나누어 떨어지지 않음 다시 나눔
4. 48 % 40 = 8
40은 8로 나누어 떨어진다.
최종적으로 r = 0이 되므로 계산이 종료가되어 최소공배수는 8이된다.
// 위에 예를 코드로 구현해보자
function gcd(a, b) {
let r = 0;
while (b !== 0) {
r = a % b
a = b
b = r
}
return a
}최소공배수(LCM)
비교적 적은 최소공배수의 성질중에 두수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈것과 같은 성질이 있다.
그럼 위에 최대공약수를 구현한 식에 몇가지만 추가해준다면 최소공배수를 쉽게 구할수 있을것이다.
// 최소공배수 구하는 식
function lcm(a, b) {
return (a * b) / gcd(a, b)
}
function gcd(a, b) {
let r = 0;
while (b !== 0) {
r = a % b
a = b
b = r
}
return a
}순열 / 조합 🐬
순열이란?
서로 다른 n개의 물건 중에서 r개를 택하여 한 줄로 배열하는 것을 n개의 물건에서 r개 택하는 순열이라 한다.
조합이란?
서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합이라 한다.
순열과 조합의 차이
순서를 생각하며 나열한다면 순열이고, 순서를 생각하지 않는다면 조합이다.
이제 순열과 조합을 구하는 코드를 구현해보자.
// 순열
function permutation(arr, selectNum) {
let result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixer = v;
const restArr = arr.filter((_, index) => index !== idx);
const permuationArr = permutation(restArr, selectNum - 1);
const combineFixer = permuationArr.map((v) => [fixer, ...v]);
result.push(...combineFixer);
});
return result;
}
// 조합
function combination(arr, selectNum) {
const result = [];
if (selectNum === 1) return arr.map((v) => [v]);
arr.forEach((v, idx, arr) => {
const fixed = v;
const restArr = arr.slice(idx + 1);
const combinationArr = combination(restArr, selectNum - 1);
const combineFix = combinationArr.map((v) => [fixed, ...v]);
result.push(...combineFix);
});
return result;
}멱집합 🐬
멱집합이란?
주어진 집합의 모든 부분집합을 멱집합이라고 한다.
만약 [1, 2, 3]의 모든 부분집합을 구해보면 아래와 같을 것이다.
- []
- [1]
- [2]
- [3]
- [1,2]
- [1,3]
- [2,3]
- [1,2,3]
이제 멱집합을 구하는 코드를 구현해보자
function powerSet(arr) {
//check표시 해줄 배열
let check = new Array(arr.length).fill(0);
//모든 부분집합이 담길 배열이다.
let powerSetArr = [];
const dfs = (depth) => {
//check에 1인 index와 같은 index에 있는 arr만 filter해서 넣어준다.
if (depth === check.length) {
powerSetArr.push(arr.filter((v, idx) => check[idx]));
} else {
//포함되는 경우
check[depth] = 1;
dfs(depth + 1);
//포함되지 않는 경우
check[depth] = 0;
dfs(depth + 1);
}
};
dfs(0);
return powerSetArr;
}하루를 마치며👋
오늘은 Algorithm with Math 부분을 학습하고 페어와 같이 코플릿을 진행하였다. 지금 과정이 나에게 있어서 너무 어렵고 부담이 가지만 페어분에 도움을 받아서 어느정도 이해하며 문제를 풀수있었다. 그렇다고 이번 부분이 쉬웠던거 아니였지만 비교적 이전 시간에 배웠던 부분보다는 이해하기 쉬워서 다행이였다... 오늘 배운것이 완벽히 내것이 될수있도록 더 공부해 봐야겠다 ! 그리고 내일 있을 ha테스트 준비도 열심히 해야겠다.... 💪💪💪
