유클리드 호재법
78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 ＋ 0
최대 공약수는 36이다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
a와 b의 최대 공약수와 최소 공배수의 특징
최대 공약수 x 최소 공배수 = a x b;
while 안의 조건이 성립할때까지 한다.
루트를 이용하여 소수를 판별한다.
for (let j = 2; j <= Math.floor(Math.sqrt(num)); j++) {
if (num % j === 0) {
count[i] = false;
break;
}
Array.from을 이용하면 배열 만들기 수월하다
예시
let arr = Array.from(Array(100), () => Array(100).fill(0));
100x100개의 0을 채운 배열을 만들 수 있다.
sort 오름차순 내림차순
[1,3,2].sort((a, b) => {
return a - b;
});
//1,2,3개발자 도구로 확인해보면 아래와 같은 결과를 출력한다.
[1,3,2].sort((a, b) => {
return b - a;
});
//3,2,1
개발자 도구로 확인해보면 아래와 같은 결과를 출력한다.
sort는 const의 배열도 바꿔버린다.
그래서 이를 막기 위해서 slice로 새로운 식별자를 생성함
const input = require("fs")
.readFileSync("20230319/Inflearn/example5.txt")
.toString()
.trim()
.split("\n");
const numArray = input.slice(1)[0].split(" ").map(Number);
let sortArray = numArray.slice().sort((a, b) => b - a);
// let sortArray = numArray.sort((a, b) => a - b);
//sort는 mutable const 뚫음
//슬라이스로 다른 배열 생성
let result = [];
for (let i = 0; i < numArray.length; i++) {
let rank = sortArray.indexOf(numArray[i]);
result[i] = rank + 1;
}
console.log(result);
// let sortArray = numArray.sort((a, b) => a - b);
//sort는 mutable const 뚫음
//슬라이스로 다른 배열 생성
2차원 배열 다루는 법
const input = require("fs")
.readFileSync("20230319/Inflearn/example6.txt")
.toString()
.trim()
.split("\n");
let numArray = input.map((el) => el.split(" ").map(Number));
let n = numArray.splice(0, 1); //1번 값을 뺴버림
let sum1 = (sum2 = 0);
let answer = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
sum1 = sum2 = 0;
for (let j = 0; j < n; j++) {
sum1 += numArray[i][j];
sum2 += numArray[j][i];
}
answer = Math.max(answer, sum1, sum2);
} //일직선 값 계산
sum1 = sum2 = 0;
for (let i = 0; i < n; i++) {
sum1 += numArray[i][i]; //대각선 1
sum2 += numArray[i][n - i - 1]; // 1빼주는 이유는 4부터 시작하기 위함
}
answer = Math.max(answer, sum1, sum2);
console.log(answer);
대각선과 열을 다루는 방법이 인상적이었다.
소인수분해
기존의 소수를 구해서 하려고 하였는데,
그것보다 시간 복잡도가 더 적은 방법은 바로 2부터 시작하는 것이었다.
const input = require("fs")
.readFileSync("20230319/example3.txt")
.toString()
.trim();
var answer = [];
var result = input;
for (var i = 2; i <= input; i++) {
var num = i;
while (result % num === 0) {
answer.push(num);
if (result / num === 1) break;
result = result / num;
}
}
console.log(answer.join("\n").trim());해당 숫자로 나뉘어질때까지 나누고 숫자 하나씩 올려서 푸는 방법이다.
나는 input을 반으로 나누어서 나머지 것들만 하면 될 것이라고 생각했는데,
소수라는 반례가 있어서 그 문제를 해결하지 못하였다.
만약에 쓸거면 소수를 거르고 써야할 것 같다.
x,y좌표 관리하기
x,y좌표 값을 만들어서 관리하는 것이 인상적이었다.
4방위를 추가하였고 이에 따라서 이동하는 좌표에 맞춰서
4방위 체크하는 for문을 추가하여 관리하였다.
또한 범위 밖에 index값을 예측해서 if and 연산자로 막아주는 것이 좋았다.
const input = require("fs")
.readFileSync("20230319/Inflearn/example7.txt")
.toString()
.trim()
.split("\n");
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let count = 0;
for (let i = 0; i < num; i++) {
for (let j = 0; j < num; j++) {
let isHigh = true;
for (let k = 0; k < 4; k++) {
let nx = i + dx[k];
let ny = j + dy[k];
if (
nx >= 0 &&
nx < num &&
ny >= 0 &&
ny < num &&
numArray[i][j] <= numArray[nx][ny]
) {
isHigh = false;
break;
}
}
if (isHigh) {
count++;
}
}
}
console.log(count);에라토스테네스의 체
const input = require("fs")
.readFileSync("20230321/example.txt")
.toString()
.trim()
.split("\n")
.map(Number);
input.shift();
console.log(input);
const MAX = Math.max(...input);
const answer = [];
//배열 생성하고 차후 소수를 판별 위해 트루로 채워줌
let prime = new Array(MAX + 1).fill(true);
//소수와 아닌수를 구한다.
for (let i = 2; i * i <= MAX + 1; i++) {
for (let j = i * i; j <= MAX + 1; j += i) {
prime[j] = false;
}
} //에라토스네의 체
input.forEach((v) => {
for (let i = Math.ceil(v / 2); i > 1; i--) {
if (prime[i] && prime[v - i]) {
console.log(i, v - i);
//소수로만 이루어진 쌍을 찾기위함, 골드바흐의 파티션을 이루는 수를 찾기 위함
answer.push(`${i} ${v - i}`);
break;
}
}
});
반으로 쪼갠 뒤 양쪽으로 퍼지면서 체크하는 것이 인상깊었다.
새로운 것을 배우는 것보다 정리하는 것이 중요하다.