백준, 인프런 알고리즘 문제 오답노트

camel·2023년 3월 19일

유클리드 호재법

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;
    }
  }
});