Goni's dev_log

문제

https://www.acmicpc.net/problem/15650

코드

//실버3 N과 M(2)
//https://www.acmicpc.net/problem/15650
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
function getPermutation(arr, selectNumber) {
  const result = []; //결과를 담을 배열
  if (selectNumber === 1) {
    return arr.map((value) => [value]); //1개 선택은 모든 원소를 그대로 return
  }
 
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(index + 1)]; //해당하는 fixed를 제외한 나머지 배열
    const permutations = getPermutation(rest, selectNumber - 1); //나머지에 대한 순열을 구하기
    const attached = permutations.map((permutation) => [fixed, ...permutation]); //돌아온 순열에 떼 놓은 fixed값 붙이기
 
    result.push(...attached);
  });
 
  return result;
}
 
const N = Number(input[0].split(" ")[0]);
const M = Number(input[0].split(" ")[1]);
const numbers = [];
for (let i = 1; i <= N; i++) numbers.push(i); //1부터 N까지의 수를 담은 배열
const result = getPermutation(numbers, M); //numbers와 M으로 순열함수 호출
//result의 각 순열 결과에 대해 한 칸 띄워 출력하기
for (let i = 0; i < result.length; i++) {
  console.log(result[i].join(" "));
}

후기

• N과 M(1)번 문제에 오름차순인 수열만 출력해야하는 조건이 하나 더 붙었다. 그래서 (1)번문제와 달리 이 문제는 조합을 이용하여 풀었다. 순열 말고 조합을 이용하면 중복 값을 제거해주므로 자동으로 오름차순된 수열만 return하는 특징이 있다 

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀

문제

https://www.acmicpc.net/problem/15649

코드

//실버3 N과 M(1)
//https://www.acmicpc.net/problem/15649
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
function getPermutation(arr, selectNumber) {
  const result = []; //결과를 담을 배열
  if (selectNumber === 1) {
    return arr.map((value) => [value]); //1개 선택은 모든 원소를 그대로 return
  }
 
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; //해당하는 fixed를 제외한 나머지 배열
    const permutations = getPermutation(rest, selectNumber - 1); //나머지에 대한 순열을 구하기
    const attached = permutations.map((permutation) => [fixed, ...permutation]); //돌아온 순열에 떼 놓은 fixed값 붙이기
 
    result.push(...attached);
  });
 
  return result;
}
 
const N = Number(input[0].split(" ")[0]);
const M = Number(input[0].split(" ")[1]);
const numbers = [];
for (let i = 1; i <= N; i++) numbers.push(i); //1부터 N까지의 수를 담은 배열
const result = getPermutation(numbers, M); //numbers와 M으로 순열함수 호출
//result의 각 순열 결과에 대해 한 칸 띄워 출력하기
for (let i = 0; i < result.length; i++) {
  console.log(result[i].join(" "));
}

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀

문제

https://www.acmicpc.net/problem/1003

코드

//실버3 피보나치 함수
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
let inputIndex = 0;
let testCase = Number(input[inputIndex++]);
 
while (testCase--) {
  let num = Number(input[inputIndex++]);
  let fibonacci = new Array(num).fill(0); //num개의 원소를 담을 수 있는 배열
  let index = 0;
 
  //fibonacci = [0의 count, 1의 count]
  fibonacci[index++] = [1, 0]; //fibo(0) = 0
  fibonacci[index++] = [0, 1]; //fibo(1) = 1
 
  //fibo(0), fibo(1)은 초기화해두었기 때문에 index=2부터 시작
  for (index = 2; index <= num; index++) {
    //fibonacci[num] = fibonacci[num-1] + fibonacci[num-2] 공식 이용
    fibonacci[index] = [
      fibonacci[index - 1][0] + fibonacci[index - 2][0],
      fibonacci[index - 1][1] + fibonacci[index - 2][1],
    ];
  }
  console.log(fibonacci[num].join(" "));
}

후기

• DP의 기초를 맛보기 위해 피보나치 문제를 풀어보았다. 물론 DP 문제 중에서는 아주 기초중에 기초라지만 재귀의 기초를 이해하는 데 도움이 됐다.
• 그런데 이 문제는 당연히 재귀를 써야만 하는 건줄 알았는데, 다른 분들의 풀이를 보다가 재귀를 사용하지 않고 오직 변수만 사용해서 count++ 하는 식으로 푼 풀이도 있었다. 

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀

문제

https://www.acmicpc.net/problem/1929

코드

//실버2 소수 구하기
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
const M = Number(input[0].split(" ")[0]);
const N = Number(input[0].split(" ")[1]);
const isPrime = Array(N + 1).fill(true); //0~N의 인덱스를 모두 가지는 배열을 만들기위해 크기는 N+1로 설정
isPrime[1] = false; //1은 소수가 아니므로 false
 
/* 에라토스테네스의 체 */
//2부터 N까지의 수 중에서 (1은 이미 소수가 아님) 루트N 이하의 수들에 대해
for (let i = 2; i * i <= N; i++) {
  //각 i에 대한 배수들을 판단해 해당 수는 소수가 아니므로 false로 만들기
  for (let j = i * i; j <= N; j += i) isPrime[j] = false;
}
 
//isPrime 배열에서 M~N의 범위의 수들 중에서 소수가 아닌 수(true)만 출력
for (let i = M; i <= N; i++) {
  if (isPrime[i] === true) console.log(i);
}

후기

• 에라토스테네스의 체를 이용하여 푸는 소수 문제이다. 

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀

문제

https://www.acmicpc.net/problem/2108

코드

//실버4 통계학
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
/* 전역변수 선언 */
let map = {}; //최빈값을 구하기 위한 map 선언
let array = []; //최빈값을 구하기 위한 배열 선언
let most = 0; //최빈값 변수
 
let N = Number(input.shift());
let numbers = input.map((i) => Number(i)).sort((a, b) => a - b); //숫자배열 오름차순 정렬
 
//각 숫자들에 대해 map에 {'숫자' : 빈도} 입력
for (let num of numbers) {
  //이미 map의 key에 해당 숫자가 있다면
  if (map[num]) map[num] = map[num] + 1;
  else map[num] = 1;
}
 
let mostFrequency = Math.max(...Object.values(map)); //map의 value(빈도) 중 최대값 받기
 
//map의 각 key(숫자들)에 대해
for (let key in map) {
  //value가 최대빈도라면 array에 해당 key 넣기
  if (map[key] === mostFrequency) array.push(key);
}
//최빈값인 숫자가 여러개라면
if (array.length > 1) {
  array = array.sort((a, b) => a - b); //오름차순 정렬하여
  most = array[1]; //1번째 인덱스 수를 최빈값 변수에 넣기(두번째로 작은 수 출력)
} else most = array[0]; //최빈값인 수가 하나라면 바로 해당 수 최빈값 변수에 넣기
 
//산술평균
let average = Math.round(
  numbers.reduce((acc, cur) => {
    return acc + cur;
  }, 0) / N
);
let middle = numbers[Math.floor(N / 2)]; //중앙값
let range = numbers[N - 1] - numbers[0]; //범위
 
console.log(`${average}\n${middle}\n${most}\n${range}`); //한번에 출력

후기

• 산술평균, 중앙값, 범위는 쉽게 구했지만 최빈값에서 은근 시간이 걸렸다. map, array 를 이용하면 충분히 구현할 수 있지만 하드코딩한 감이 없지않아 있다.
• 출력은 저번에 백준 문제를 풀다가 시간 단축을 위해 한 번에 console.log() 하는 법을 터득해서 이번에도 한 번에 출력하는 방식으로 해봤다. 

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀

문제

https://www.acmicpc.net/problem/11650

코드

• 처음 시도한 풀이 (시간 초과)

  //실버5 좌표 정렬하기
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
  let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
   
  let N = Number(input.shift());
  let coordinate = [];
   
  for (let i = 0; i < N; i++) {
    coordinate.push(input[i].split(" ").map((i) => Number(i)));
  }
   
  coordinate = coordinate.sort((a, b) => {
    if (a[0] > b[0]) return 1;
    else if (a[0] < b[0]) return -1;
    else {
      if (a[1] > b[1]) return 1;
      else return -1;
    }
  });
  for (let i = 0; i < N; i++) console.log(coordinate[i].join(" "));​

• 다시 시도한 풀이 (성공)

  //실버5 좌표 정렬하기
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
  let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
   
  let N = Number(input.shift());
  let coordinate = input.map((i) => i.split(" ").map((j) => Number(j))); //좌표를 number화 하여 배열에 담기
  let answer = "";
   
  coordinate.sort((a, b) => {
    //각 좌표들을 비교하며 x가 같지않으면 x에 대해 오름차순 정렬하고
    if (a[0] !== b[0]) return a[0] - b[0];
    //그게 아니면 y에 대해 오름차순 정렬하기
    return a[1] - b[1];
  });
  coordinate.forEach((i) => {
    //정렬된 좌표들 각각에 대해 answer에 담기
    answer += `${i[0]} ${i[1]}\n`;
  });
   
  console.log(answer);​

후기

• 쉽게 풀어서 성공! 이라고 생각했는데 시간초과에서 자꾸 막혔던 문제이다. 다른 분의 풀이를 참고해서 sort()를 적용하는 신박한 방법과 console.log()를 1번만 찍는 걸로 코드를 수정했다.
• 다른 분의 풀이를 참고하여 변경한 sort()코드는 가시적으로도 한눈에 더 이해하기 쉬웠고, 여러 if문을 쓰지 않아 더 효율적인 것 같다. 또한 console.log()를 for문으로 반복적으로 찍는 것보다 문자열로 처리하여 한 번에 출력하는 방법이 있단 것도 배우게 됐다! 

  ---

잘못된 내용이나 수정이 필요한 내용이 있으면 언제든 댓글 달아주세요 감사합니다 😀