📌 어제 알고리즘 문제를 페어와 함께 푸는 시간이었는데 1~3번인 그리디, 구현 문제는 풀었으나 4번인 DP 문제를 풀지 못하였다 조금만 더 생각했으면 풀었겠지라는 생각도 들었으나 그것은 코딩테스트로 따질때 시간이 많이 걸렸기 때문에 1솔 정도의 풀이가 되진 못했을 것 같다. 앞으로 JS로 알고리즘을 더욱 많이 풀어야 겠다는 생각을 하게되었던 하루였다. 그래서 오늘은 꼭 모든 문제를 페어와 같이 해결할 수 있었으면 좋겠다는 생각을 했다.
📗 오늘 학습한 내용
순열 (Permutaion)
- 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며, 이는 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
조합 (Combination)
- 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관없게 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 같다.
GCD (최대공약수, Greatest Common Divisor)
- 두 수 이상의 여러 수 중 공통된 *약수를 의미한다.
- *약수: 어떤 수를 나누어 떨어지게 하는 수를 의미한다.
- 예시
- 6의 약수: 1, 2, 3, 6
- 9의 약수: 1, 3, 9
- 공약수: 1, 3
- 최대 공약수: 3
LCM (최소공배수, Lowest Common Multiple)
- 공배수는 두 수 이상의 여러 수 중 공통된 배수를 의미한다.
- *배수: 하나의 수에 정수를 곱한 수 이다.
- 예시
- 12의 배수: 12, 24, 36, 48, 60, 72, 84, 96 ...
- 18의 배수: 18, 36, 54, 72, 90 ...
- 최소 공배수: 36
GCD/LCM 구하는 공식
- 유클리드 호제법
- 최대 공약수와 관련이 깊은 공식이다. 2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다는 이론이다.
- b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수이다.
let getGCD = (num1, num2) => {
let gcd = 1;
for (let i = 2; i <= Math.min(num1, num2); i++){
if(num1 % i === 0 && num2 % i === 0){
gdc = i;
}
}
}
/*----------------------------------------------*/
let gcd=(a,b) => {
return a%b ? gcd(b, a%b) : b
}- 최대 공약수(GCD)
- 두 수 A와 B의 공통된 약수 중에 가장 큰 정수
- 2부터 min(A, B)까지 모든 정수로 나누어보는 방법
let getGCD = (num1, num2) => {
let gcd = 1;
for (let i = 2; i <= Math.min(num1, num2); i++){
if(num1 % i === 0 && num2 % i === 0){
gdc = i;
}
}
return gcd
}- 최소 공배수(LCM)
- 두 수, 그 이상의 여러 수의 공통인 배수 중 가장 작은 수
- LCM을 1부터 시작하여 점차 lcm++ 하면서 각각의 두 수를 LCM으로 나누었을 때 나머지 값이 0인 지를 비교한다.
- A*B/GCD
let getLCM = (num1, num2) =>{
let lcm = 1;
while(true){
if((lcm % num1 == 0) && (lcm % num2 == 0)){
break;
}
lcm++;
}
return lcm
}멱집합
- 집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개입니다. 그리고 이 모든 부분집합을 통틀어 멱집합이라고 한다.
- 어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합이라고 한다.
📘 추가로 공부할 내용
Study원과 함께 진행중인 프로젝트 구현
- 로그인 한 회원의 정보 가져오기
나만의 포트폴리오 사이트 구현 해보기
- Figma를 사용하여 디자인 해보기
📝 중요한 내용
- 순열
- 조합
- 최대공약수
- 최소공배수
- 멱집합
'Daily > Today I Learned' 카테고리의 다른 글
| 22.08.16_TIL (0) | 2022.08.16 |
|---|---|
| 22.08.12_TIL (0) | 2022.08.12 |
| 22.08.10_TIL (0) | 2022.08.09 |
| 22.08.09_TIL (0) | 2022.08.09 |
| 22.08.08_TIL (0) | 2022.08.08 |
