Jeong in Tech

https://www.linkedin.com/feed/update/urn:li:activity:7193850888266866688/

'다신 안할 것' 에서 많은 것을 하고 있었다.

https://velog.io/@yukina1418/%EC%B7%A8%EC%A4%80%EC%83%9D%EC%97%90%EA%B2%8C-%EB%8F%84%EB%A9%94%EC%9D%B8%EC%9D%B4-%EC%A4%91%EC%9A%94%ED%95%9C%EA%B0%80%EC%9A%94

https://ykss.netlify.app/translation/navigating_the_future_of_frontend/?utm_source=substack&utm_medium=email

https://brunch.co.kr/@susubaa/72

문제

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

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

풀이

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/9251
// 제출 시 path : /dev/stdin

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const LCS = (str1, str2) => {
  const m = str1.length;
  const n = str2.length;

  const dp = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  let result = "";
  let i = m,
    j = n;

  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      result = str1[i - 1] + result;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return result;
}

const solution = (input) => {
  const [firstArr, secondArr] = input;
  const answer = LCS(firstArr, secondArr);
  return answer.length;
};

console.log(solution(input));

해설

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

str1 = ACAYKP

str2 = CAPCAK

i=0 -> j=0,1,2,3,4,5,6 다 비교. 

dp[1][1]:

ACAYKP 과 CAPCAK 비교

A !== C 이므로 

dp[1][1]은dp[0][1]과 dp[1][0] 중 최댓값 

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) 

dp[1][2]:

ACAYKP 과 CAPCAK 비교

A === A 이므로 

dp[1][2]은 dp[0][1]+1 

dp[i][j] = dp[i - 1][j - 1] + 1; 

문제

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

접근

1을 빼거나 2나 3을 나누어 1로 만드는데 걸리는 연산 횟수의 최솟값을 구하는 문제입니다.

첫째줄는 1이상 10^6이하의 정수 N이 주어집니다. 수의 범위가 크기 때문에 계산가능한 모든 수를 구하는 완전탐색 등은 이 문제에 어울리지 않은 접근법입니다. 한 번 연산한 값을 기억해 두고 문제를 풀 수 있는 DP가 적절해 보입니다.

DP의 인덱스는 숫자를 뜻합니다.

D[N-1]: N에서 1을 빼서 1을 만드는 연산 횟수

D[N/2]: N에서 2를 나눠 1을 만드는 연산 횟수

D[N/3]: N에서 3을 나눠 1을 만드는 연산 횟수

D[N]은 숫자 N이 1이 되는데 걸리는 최소한의 연산 횟수를 저장합니다.

N이 2로 나눠진다면 D[N] = D[N-1] + 1 과 D[N/2] + 1 중 더 작은 값, N이 3으로 나눠진다면 D[N] = D[N-1] + 1 과 D[N/3] + 1 중 더 작은 값이 됩니다.

각 경우의 수 뒤에 +1 이 되는 이유는 D[N-1],D[N/2],D[N/3] 이 각 N을 구하기 이전의 연산횟수를 나타내기 때문입니다.

예를 한 번 들어볼까요?

D[N-1] + 1 :

4를 1을 빼서 1로 만드는 연산 횟수는 3입니다. 4-1-1-1=1

3을 1을 빼서 1로 만드는 연산 횟수는 2입니다. 3-1-1=1

2를 1을 빼서 1로 만드는 연산 횟수는 1입니다. 2-1=1

이를 뒤집어보면 숫자 N을 1을 만들 때까지 1을 빼는 연산의 횟수는 N-1을 1을 만들 때까지 1을 빼는 연산의 횟수 +1 임을 알 수 있습니다. 

D[N/2] + 1 : 

2를 2로 나눠서 1로 만드는 연산 횟수는 1입니다. 2/2 = 1

4를 2로 나눠서 1로 만드는 연산 횟수는 2입니다. 4/2 = 2, 2/2 =1 

8을 2로 나눠서 1로 만드는 연산 횟수는 3입니다. 8/2 = 4, 4/2 = 2, 2/2 = 1

이를 뒤집어보면 숫자 N을 1을 만들 때까지 2를 나누는 연산의 횟수는 N-1을 1을 만들 때까지 N을 나누는 연산의 횟수 +1 임을 알 수 있습니다.

D[N/3] + 1도 위와 D[N/2] + 1의 경우와 마찬가지입니다.

문제를 한 번 풀어볼까요? N=4 로 예를 들어봅시다.

우선 D[0]은 문제 범위 밖이므로 0으로 처리해 줍니다. 

D[1] = 0 입니다. 1을 1로 만들 수 있는 연산의 횟수는 0회이기 때문입니다.

D[4] = Math.min( D[3] + 1 , D[4/2] +1) = Math.min( 1 + 1, 2 + 1 ) = Math.min(2, 3) = 2 가 됩니다.

이를 코드로 풀어보면 아래와 같습니다.

풀이

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));
const solution = (input) => {
  const N = +input;
  const DP = Array.from({ length: N + 1 }, () => 0);

  for (let i = 2; i < N + 1; i++) {
    DP[i] = DP[i - 1] + 1; // 1을 빼서 1로 만드는 연산의 횟수로 우선 설정

    if (i % 2 === 0) {
      // 2로 나눠진다면,
      DP[i] = Math.min(DP[i], DP[i / 2] + 1); // 1을 빼서 1로 만드는 연산의 횟수와  2로 나눠 1로 만드는 횟수 중 더 작은 경우로 선택.
    }

    if (i % 3 === 0) {
      DP[i] = Math.min(DP[i], DP[i / 3] + 1);
    }
  }

  return DP[N];
};

console.log(solution(input)); // 3

문제

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

접근

2가지 방법이 있다: 

- 각 스퀘어를 전부 탐색하며 조건을 찾는다. => n^n 

- 한 행에 하나의 퀸이 온다는 것을 이용해 행별로 탐색 => n (풀이 참조)

2번째의 경우가 훨씬 시간복잡도가 줄기 때문에 두 번째 방법으로 간다

즉, 행이나 열 하나를 잡고 그 행에 첫 퀸을 두었을 때 다음 행이나 열을 돌면서 경우의 수를 탐색한다. 

풀이

const input = require("fs").readFileSync("/dev/stdin").toString();

const solution = (input) => {
  const N = +input;
  const row = Array(N).fill(0);
  let cnt = 0;

  const isPossible = (x) => {
    for (let i = 0; i < x; i++) {
      if (row[x] === row[i]) return false;
      if (x - i === Math.abs(row[x] - row[i])) return false;
    }
    return true;
  };

  const dfs = (x) => {
    if (x === N) {
      cnt++;
      return;
    }

    for (let y = 0; y < N; y++) {
      row[x] = y; 
      if (isPossible(x)) {
        dfs(x + 1); 
      }
    }
  };

  dfs(0);

  return cnt;
};

console.log(solution(input));

문제

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

접근

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

➡️ 어렵게 생각할 것 없이 중복을 허용하는 순서가 상관없는 경우의 수를 구하라는 것이다: 중복순열. 순열 문제였던 백준 15650 N과 N(2) 문제에서 중복체크하는 checked 배열만 없애주면 된다.

풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const [N, M] = input;
const output = [];
let result = "";

function dfs(level, start) {
  if (level === M) {
    result += `${output.join(" ")}\n`;
    return;
  }

  for (let i = start; i < N; i++) {
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
  }
}

dfs(0, 0);

console.log(result);

문제

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

접근

백준 15651 N과 M(1) 과 같이 순열 문제이다.

단, 중복을 허용하기에 check 배열의 기능을 삭제해 주었다.

풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const [N, M] = input;
const output = [];
let result = "";
const checked = Array(N).fill(false);

function dfs(level, start) {

  if (level === M) {
    result += `${output.join(" ")}\n`;
    return;
  }
  
  for (let i = start; i < N; i++) {
    if (checked[i]) continue; // backtracking
    checked[i] = true;
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
    checked[i] = false;
  }
}

dfs(0, 0);

console.log(result);

문제

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

접근

문제 15649 N과 M(1) 과 비교했을 때,

• 고른 수열은 오름차순이어야 한다.

라는 조건이 추가됐다. 즉, [4,3] 의 경우 [3,4] 로 정렬되어 경우의 수 [4,3]와 [3,4]는 같은 것으로 간주된다.

N과 M (1)는 재귀를 위한 for loop에서 index를 항상 맨 처음부터 다시 돌았다면(모든 경우의 수를 위해), 이 문제에서는 지난 숫자는 제외하고 for loop을 진행한다(중복을 피하기 위해)

풀이

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const [N, M] = input;
const output = [];
let result = "";
const checked = Array(N).fill(false);

function dfs(level, start) {

  if (level === M) {
    result += `${output.join(" ")}\n`;
    return;
  }

  for (let i = start; i < N; i++) {
    if (checked[i]) continue;
    
    checked[i] = true;
    output.push(i + 1);
    dfs(level + 1, i);
    output.pop();
    checked[i] = false;
  }
}

dfs(0, 0);

console.log(result);

[공부정리] 순열 vs 조합 vs 중복순열 vs 중복조합 (feat. 백준 N과 M 문제 시리즈)

문제

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

접근

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

➡️ 수의 범위가 작아 완전탐색 으로 접근

중복 없는 수열

➡️ 백트래킹

➡️ 수열 문제니까 조합(combination) 또는 순열(permutation) 인데, 중복이 없다고 했으므로 순열 문제.

풀이

const input = require("fs").readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);

const [n, m] = input;
let result = "";
const output = [];
const checked = Array(n).fill(false);

function dfs(cnt) {
	
    if (cnt === m) {
        result += `${output.join(" ")}\n`;
        return;
    }

    for (let i = 0; i < n; i++) {
        if (checked[i] === true) continue;
        checked[i] = true;
        output.push(i + 1);
        dfs(cnt + 1);
        output.pop();
        checked[i] = false;
    }
}

dfs(0);

console.log(result);

문제

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

접근 

기본적인 그래프 탐색 문제. 

연결된 노드가 몇 개인지를 구하는.

단, 맨 처음 노드 시작을 인덱스 0이 아닌 1로 시작해줘야 한다.

풀이

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split("\n");

function solution(input) {
  const N = +input.shift(); // 노드 수
  const M = +input.shift(); // 간선 수
  const edges = input.map((v) => v.split(" ").map(Number));

  // 그래프 그리기
  const vertices = Array(N + 1)
    .fill(0)
    .map(() => []);
  for (let edge of edges) {
    const [v0, v1] = edge;
    vertices[v0].push(v1);
    vertices[v1].push(v0);
  }

  // 실행
  const seen = new Set();
  let count = 0;
  const dfs = (start) => {
    for (let end of vertices[start]) {
      if (!seen.has(end)) {
        seen.add(end);
        count++;
        dfs(end);
      }
    }
  };
  seen.add(1);
  dfs(1);
  console.log(seen);
  return count;
}

console.log(solution(input));

참조: https://www.acmicpc.net/source/54379165