곱셈_1629

문제 설명

문제 링크

풀이와 설명

풀이와 설명 블로그 링크

const fs = require("fs");
const [A, B, C] = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split(" ")
  .map(BigInt);

function Power(x, y) {
  if (y === BigInt(0)) return BigInt(1); 
  // y의 값이 0일 경우 1을 리턴

  let pow = Power(x, BigInt(parseInt(y / BigInt(2)))); 
// 2^2 => (2^1)x(2^1) 패턴을 재귀 (parseInt로 소수점 처리 후, 다시 BigInt로 변경)
  if (y % BigInt(2) === BigInt(0)) {
    return (pow * pow) % C; // 짝수 일 경우
  } else {
    return (pow * pow * x) % C; // 홀수 일 경우
  }
}
console.log(parseInt(Power(A, B))); // BigInt => Number

하노이 탑 순서_11729

문제 설명

문제 링크

하노이 탑이란?

• 지정된 기둥으로 모든 원반을 옮겨야 한다.
• 작은 원반보다 큰 원반이 작은 원반 위에 올라갈 수 없다.
• 한 번에 하나씩만 옮겨야 된다.
• 맨 마지막 원을 옮기기 위해서는 나머지 원반들을 다른 기둥으로 옮겨야하는 한다. (재귀 패턴)

문제

입력 값으로 원판의 개수를 받아 원판이 옮겨지는 횟수와 어디서 어디로 옮겨지는지 출력하시오,

• Input:
  1 < 3 <= 20

3

• Output:

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split(" ");
let leng = Number(input.shift());
let ans = [];
function quad(n, from, to, other) {
  if (n === 0) return;
  quad(n - 1, from, other, to); 
  // 가장 큰 원반을 제외한 나머지 원반을 목적지가 아닌 다른 기둥으로 옮기는 작업
  ans.push(`${from} ${to}`);
  // 옮길 때 마다 원반이 어디서 어디로 옮겨지는지 출력 배열에 push
  quad(n - 1, other, to, from);
  // 가장 큰 원반을 목적지 원반으로 옮겨지는 재귀
  
}

quad(leng, 1, 3, 2);

console.log(ans.length + "\n" + ans.join("\n"));

참고
유투브 영상

Z_1074

문제 설명

문제 링크
2^N x 2^N인 2차원 배열을 z모양으로 탐색 (왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문) N > 1인 경우, 배열의 크기가 2^N-1 x 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문 (1사분면 -> 2사분면 -> 3사분면 -> 4사분면 순으로 방문)

• Input:
  N, r, c 순

- 2 3 1
- 3 7 7
- 10 512 512
- 1 0 0

• Output:

- 11
- 63
- 786432
- 0

풀이

• 먼저 z모양으로 방문 할 때 총 4등분으로 한다. 여기서 4등분으로한 각 면의 첫 방문 값을 보면 각각 2^N으로 반복되는 현상을 볼 수 있다. 이 부분을 재귀로 사용한다.
  (1사분면 => 2^Nx0, 2사분면 => 2^Nx1, 3사분면 => 2^Nx2, 4사분면 => 2^Nx3)
• 전체 면에서 2x2까지 재귀를 통해서 계속 나누어 나간다. 여기서 r,c가 (2^N)/2의 값을 통해서 몇 사분면에 속해져있는지 확인하면서 2^N/2의 값과 r,c값을 내려준다.

풀이 예시

leng : 2^2 r: 0 c: 2
((leng/2 * leng/2) * 1) + ((leng/2/2 * leng/2/2) + 0) = 4
(2*2)의 면적 * 2사분면 + (1*1) * 1사분면 = z의 순

const fs = require("fs");
const [N, R, C] = fs
  .readFileSync("../input.txt")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

let leng = 2 ** N;
let ans = 0;

function zFunc(num, r, c) {
  if (num <= 0) return;
  let part = 0; // 각 사분면 마다의 곱셈을 하기 위한 변수
  if (r < num / 2 && c < num / 2) { // 1사분면 
    part = 0;
  } else if (r < num / 2 && c >= num / 2) { // 2사분면 
    part = 1;
    c = c - num / 2;
  } else if (r >= num / 2 && c < num / 2) { // 3사분면
    part = 2;
    r = r - num / 2;
  } else { // 4사분면
    part = 3;
    r = r - num / 2;
    c = c - num / 2;
  }

  zFunc(num / 2, r, c);

  ans = ans + (num / 2) * (num / 2) * part; // 각 사분 면의 크기 * n사 분면
}

zFunc(leng, R, C);

console.log(ans);

쿼드트리_1992

문제 설명

문제 링크

• N x N으로 이루어진 데이터 구조로 퀴드 트리를 하는데 이 때 모두 0으로 이루어졌을 때 0으로 표시가 가능하고 모두 1로 이루어져있을 때 1로 출력이 가능하다. 만일 전체를 한 번에 표시 못할 경우 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 4등분 하여 다시 0,1로 같은 숫자로 이루어져있는지 확인하여 출력할 수 있다. N x N에 데이터 구조를 퀴드 트리로 출력하시오.

• Input:
  첫 줄: N, 나머지 줄: 데이터 구조

- 8
  11110000
  11110000
  00011100
  00011100
  11110000
  11110000
  11110011
  11110011

- 4
  1111
  1111
  1111
  1111

• Output:

- ((110(0101))(0010)1(0001))
- 1

풀이

• 데이터 구조를 2차원 배열로 봤을 때, 모든 원소들을 확인하고 모든 수가 같은 지 확인한다.
• 수가 각각 다 다를 경우, 2차원 배열을 4등분을 하여 각 4등분의 2차원 배열을 확인한다.
• 위와 같은 작업을 재귀를 통해 반복하고, 모든 원소들이 같지 않을 경우 (를 통해 나누어 준다.

const fs = require("fs");
const input = fs.readFileSync("../input.txt").toString().trim().split("\n");
const leng = Number(input.shift());
let ans = "";

function Quad(arr, n) { // 4등분 해주는 함수
  let [arr1, arr2, arr3, arr4] = [[], [], [], []];

  if (n === leng) { // 처음 들어왔을때의 2차원 배열은 원소가 같은지 판별이 되기 전이기 때문에 전체를 return 해준다.
    return { arr1: arr };
  }
  for (let i = 0; i < n; i++) {
    arr1 = [...arr1, arr[i].slice(0, n)];
    arr2 = [...arr2, arr[i].slice(n, n * 2)];
    arr3 = [...arr3, arr[i + n].slice(0, n)];
    arr4 = [...arr4, arr[i + n].slice(n, n * 2)];
  }

  return { arr1, arr2, arr3, arr4 };
}

function QuadTree(arr, n) {
  let quad = 1;
  let quadObj = Quad(arr, n); // n사분면으로 나뉘어진 데이터들의 객체
  let trigger = true; // 모든 원소가 같은지 판별해주는 boolean타입 변수

  while (quad < 5 && quadObj[`arr${quad}`]) {
    trigger = true;
    for (let i = 0; i < n; i++) { // 첫 원소와 확인하고 있는 원소가 다를 경우 trigger변수를 false로 바꾸어주고 반복문을 멈춘다.
      for (let j = 0; j < n; j++) {
        if (quadObj[`arr${quad}`][i][j] !== quadObj[`arr${quad}`][0][0]) {
          trigger = false;
          break;
        }
      }
    }
    if (trigger) ans = ans + quadObj[`arr${quad}`][0][0]; // 모든 원소가 맞을 경우 
    else { // 원소가 다를 경우 n사분면의 데이터 구조들을 재귀하고, n사분면의 구조는 전체 면적의 n/2이기 때문에 n/2을 재귀해준다.
      ans = ans + "(";
      QuadTree(quadObj[`arr${quad}`], n / 2);
      ans = ans + ")";
    }
    quad++; // n사분면의 n증가 ex) arr1(1사분면) -> arr2(2사분면)
  }
}

QuadTree(input, leng);
console.log(ans.trim());

별 찍기-10_2447

문제 설명

문제 링크

풀이와 설명

풀이와 설명 블로그 링크

let fs = require("fs");
let input = Number(fs.readFileSync("../input.txt").toString());
let str = "";

function star(i, j) {
  if (i % 3 === 1 && j % 3 === 1) {
    str += " ";
  } else {
    if (Math.floor(i / 3) === 0 && Math.floor(j / 3) === 0) {
      str += "*";
    } else {
      star(Math.floor(i / 3), Math.floor(j / 3));
    }
  }
}

for (let i = 0; i < input; i++) {
  for (let j = 0; j < input; j++) {
    star(i, j);
  }

  str += "\n";
}
console.log(str.trim());