Jeong in Tech

문제

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

풀이

해설

sequence = [ 10, 20, 10, 30, 20, 50 ]

문제

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/12865

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

4 7 // N K
6 13 // W V
4 8 // W V
3 6 // W V
5 12 // W V

접근

배낭 문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭 문제를 분할 가능 배낭 문제(Fractional) -Greedy 문제 , 짐을 쪼갤 수 없는 경우의 배낭 문제를 0-1 배낭 문제(0-1 Knapsack) - DP문제 라 부른다. - 위키백과

해당 문제는 0-1 배낭 문제(0-1 Knapsack)로 DP로 접근한다.

DP문제는 문제의 답을 구하는 규칙성(점화식)을 빨리 찾는게 관건이다.(개인생각, 2023.02.022)

결론부터 말하면 문제의 점화식은 아래와 같다: 

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);

풀이

const fs = require("fs");

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

const input = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));

const solution = (input) => {
  const [N, K] = input.shift();
  const weight = input.flat().filter((val, idx) => idx % 2 === 0);
  const value = input.flat().filter((val, idx) => idx % 2 !== 0);
  const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0));

  // 점화식: dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= K; i++) {
      if (j - weight[i] >= 0)
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      dp[i][j] = dp[i - 1][j];
    }
  }

  return dp[N][K];
};
console.log(solution(input));

해설

왜 DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]); 인가?

인덱스 문제 때문에 arr[0] 부분을 형식상 채워준다.

row: 아이템1, 2, 3, 4

col: 현재 배낭의 무게

문제풀이는 이해가 가는데 계속 런타임 에러가 나는 이유를 모르겠다. 내일은 아래 보면서 이부분 디버깅 해봐야겠음.

let fs = require("fs");
let knapsack = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(knapsack[0].split(" ")[0]);
const K = Number(knapsack[0].split(" ")[1]);
knapsack = knapsack.map((element) =>
  element
    .trim()
    .split(" ")
    .map((value) => Number(value))
);
const weight = [];
const value = [];
for (let n = 0; n <= N; n++) {
  weight.push(knapsack[n][0]);
  value.push(knapsack[n][1]);
}

const dp = Array.from(new Array(N + 1), () => new Array(K + 1));

for (let i = 0; i <= N; i++) {
  dp[i][0] = 0;
}
for (let j = 0; j <= K; j++) {
  dp[0][j] = 0;
}
for (let j = 1; j <= K; j++) {
  if (knapsack[1][0] <= j) {
    dp[1][j] = knapsack[1][1];
  } else {
    dp[1][j] = 0;
  }
}

for (let i = 2; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    if (j < weight[i]) {
      dp[i][j] = dp[i - 1][j];
    } else {
      // 현재 물건을 포함하지 않는 경우 : dp[i - 1][j]
      // 현재 물건을 포함하는 경우: dp[i-1][j - weight[i]] + value[i]
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
  }
}
console.log(dp[N][K]);

문제

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/10026

접근

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

적록색맹인 경우와 적록색맹이 아닌 경우로 visited 배열을 따로 만들어 계산한다.

풀이

참조(https://zzang9ha.tistory.com/227)

시도1: 우선 notRBG부터 구하기 

expected: 4

result: 2

debugging: visited 의 문제였다.

const wrongVisited = Array(N).fill(Array(N).fill(false));

  const rightVisited = Array.from(Array(N), () => Array(N).fill(false));

이유는 모르겠지만, x=0, y=0 일때, visited[x][y] = true 를 진행했을 때 전자는 이렇게 y=0 부분이 전부 true 로 바뀐 걸 볼 수 있다. 

후자는 예상했던 것처럼 딱 visitied[0][0]부분만 true 로 표시된 걸 알 수 있다.

근데 웃긴건 전자 후자 모두 맨 처음 상태 콘솔찍어보면 같은 모양이다. 

 이유는 모르겠지만, 이런 개떡같은 이유로 40분을 날린 것이 원통하다. 우선은 문제 풀이에 필요한 기본 논리는 파악한 것에 만족하고 넘어가자. 앞으로는 절대 visited 후자로만 쓸 것이다.

const solution = (input) => {
  const N = +input.shift();
  const graph = input.map((v) => v.split(""));

  const dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];
  const visited = Array(N).fill(Array(N).fill(false));
  let cnt = 0;

  const isInRange = (nx, ny) => {
    if (nx >= 0 && ny >= 0 && nx < N && ny < N) return true;
    return false;
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
     
     const dfs = (x, y) => {
        visited[x][y] = true;

        for (let k = 0; k < dx.length; k++) {
          const nx = x + dx[k];
          const ny = y + dy[k];

          if (
            isInRange(nx, ny) &&
            !visited[nx][ny] &&
            graph[nx][ny] === graph[x][y]
          ) {
            dfs(nx, ny);
          }
        }
      };

      if (!visited[i][j]) {
        dfs(i, j);
        cnt++;
      }
    }
  }
  return cnt;
};

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49994

접근

게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하는 문제이다.

- 그래프탐색

- 중복배열체크 -> 중복에 있다면 바로 그때까지의 결과 return

- 주의사항: 그래프를 벗어나는 이동은 무시한다.

- 그래프의 크기는 10*10 정사각형이다.

https://developerm.tistory.com/196

check 배열 쓰는 방식을 굉장히 특이하게 하는 문제더라.

풀이

function solution(input) {
  const dirs = input.split("");
  const visited = new Set();
  const pos = { x: 0, y: 0 };

  for (const dir of dirs) {
    const prevPos = {
      x: pos.x,
      y: pos.y,
    };

    if (dir === "U" && pos.y < 5) pos.y += 1;
    if (dir === "D" && pos.y > -5) pos.y -= 1;
    if (dir === "R" && pos.x < 5) pos.x += 1;
    if (dir === "L" && pos.x > -5) pos.x -= 1;

    const move1 = prevPos.x + "" + prevPos.y + pos.x + pos.y;
    const move2 = pos.x + "" + pos.y + prevPos.x + prevPos.y;

    if (move1 != move2 && !visited.has(move1) && !visited.has(move2)) {
      visited.add(move1);
      visited.add(move2);
    }
  }

  return visited.size / 2;
}

* 마지막에 둘 다 넣어주는 이유:

 (0,0) -> (1,2) 를 지나갔다고 치자. 돌고 돌다보니 다시 (1,0) 지점으로 왔다. 그리고 다시 (1,0) 에서 (0,0) 가는 형태였다. 

이경우 이 길은 지나갔기 때문에 탐색을 멈추고 결과를 도출해야 한다. 

 (0,0) -> (1,0)

 (1,0) -> (0,0) 

를 visited 가 두 경로를 모두 가지고 있지 않으면 아직 방문하지 않은 새로운 경로로 착각해 또 경로 수를 카운팅한다. 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/62048

접근

1. 사각형, 즉 이중배열 -> 그래프 탐색

2. 대각선, 즉 row[x]-row[y] = row[x+1]-row[y+1]

접근 방식이 아예 달랐다. 

https://codingwell.tistory.com/30

솔직히 한 번 푸는 지금은 왜 이런식에 도달하는지 이해가 안간다.

일단은 직사각형의 대각선 문제는 이렇게 접근할 수 있다는 정도만 이해하기로 한다.

직사각형에서 직사각형의 대각선이 지나가는 1*1정사각형의 갯수는 (W+H-최대공약수) 이다.

다시 풀어보면,

1. 최대공약수(GCD) 구하기

2. (W*H) - (W+H-GCD)

풀이

const getGCD = (num1, num2) => {
  let gcd = 1;

  for (let i = 2; i <= Math.min(num1, num2); i++) {
    if (num1 % i === 0 && num2 % i === 0) {
      gcd = i;
    }
  }

  return gcd;
};

function solution(W, H) {
  const GCD = getGCD(W, H);
  return W * H - (W + H - GCD);
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12982

접근

앞서 풀었던 조합 문제와 거의 같다. 

주어진 부서별 예산 n 개의 합이 주어진 예산 m 을 넘지 않을 때까지 합한다.

만약 sum >= m 이면 해당 재귀 종료 준비를 한다.

풀이

접근1. 재귀

결과: 틀렸습니다! 재귀로 풀었는데 계속 다른 두 케이스가 같은 답이 나왔다.

접근2: 그냥 단순하게 접근하기로. 반복문

결과: 틀렸습니다! 답은 맞게 나오는데 테스트 케이스 몇 개에서 걸렸다.

  const N = d.length;
  let answer = 0;
  let sum = 0;

  for (let i = 0; i < N; i++) {
    sum += sortedD[i];
    if (sum > budget) {
      answer = i;
      break;
    }
  }
  if (sum <= budget) answer = d.length;

  return answer;

접근3: sort 추가

결과: 맞았습니다!

  const sortedD = d.sort((a, b) => a - b);
  const N = d.length;
  let answer = 0;
  let sum = 0;

  for (let i = 0; i < N; i++) {
    sum += sortedD[i];
    if (sum > budget) {
      answer = i;
      break;
    }
  }
  if (sum <= budget) answer = d.length;

  return answer;

function solution(d, budget) {
    d.sort((a, b) => a - b);

    while (d.reduce((a, b) => (a + b), 0) > budget) d.pop();

    return d.length;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12977

접근

1) 주어진 수 n(숫자 배열의 길이) 개 중 3개의 수를 골라 합을 만드는 경우의 수 -> 조합문제, dfs

2) 합이 소수인지 확인한다. (아래 isPrime 함수를 이용한다.)

3) 소수라면 경우의 수 +1 을 한다.

풀이

function isPrime(num) {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++) {
    if (num % i === 0) return false;
  }
  return num > 1;
}

function solution(nums) {
  const N = nums.length;
  const M = 3;
  const checked = Array(N).fill(false);
  let sum = 0;
  let answer = 0;

  function dfs(level, start) {
    if (level === M) {
      if (isPrime(sum)) answer++;
      return;
    }

    for (let i = start; i < N; i++) {
      if (checked[i]) continue;

      checked[i] = true;
      sum += nums[i];
      dfs(level + 1, i);
      sum -= nums[i];
      checked[i] = false;
    }
  }

  dfs(0, 0);

  return answer;
}

문제

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