Link6603번 - 로또 문제풀이(1)// let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let input = require("fs") .readFileSync("4. Backtracking/inputs/s2-6603.txt") .toString() .split("\r\n");let idx = 0;let curr = input[idx++].split(" ").map(Number);while (curr[0] !== 0) { const k = curr[0]; const arr = curr.splice(1); const bt = (depth, start, trr) => { if (depth ..

Link1182번 - 부분 수열의 합 문제풀이(1)let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");const [N, S] = input[0].split(" ").map(Number);const nums = input[1].split(" ").map(Number);let answer = 0;const bt = (sum, start) => { if (sum === S) { answer += 1; return; } for (let i = start; i (2)// let input = require("fs").readFileSync("/dev/stdin").toString().trim().spl..

Backtracking, 백트래킹백트래킹이란?백트래킹은 DFS (깊이 우선 탐색) 의 한 형태로, 모든 후보 해를 탐색하되, 해답이 될 수 없는 부분은 미리 가지치기하여 탐색 범위를 줄이는 기법입니다. 예를 들어, 특정 조건을 만족해야 하는 조합, 순열, 그래프의 경로 문제에서 자주 활용됩니다.핵심 아이디어는 다음과 같습니다:해단 노드(상태)가 유효한지 검사한다.만약 유효하지 않다면(조건을 만족하지 않는다면) 바로 백트래킹(Backtracking)하여 이전 단계로 돌아간다.유효하다면 다음 노드(상태)로 이동하여 탐색을 이어간다.목표 조건(해를 찾았는지 or 모든 후보를 탐색했는지) 달성 시까지 1~3번 과정을 반복한다. 핵심 개념과 동작 원리상태(state)상태는 현재까지 내린 결정(선택)들의 집합을 ..

Link15649번 - N과 M (1) 문제풀이(1)// let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let input = require("fs") .readFileSync("4. Backtracking/inputs/s3-15649.txt") .toString() .split("\r\n");const [N, M] = input[0].split(" ").map(Number);const isUsed = Array.from({ length: N + 1 }, () => false);const answers = [];const path = Array.from({ length: M }, () => 0);co..

Link12865번 - 평범한 배낭 문제풀이(1)let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");const [N, K] = input[0].split(" ").map(Number);const dp = new Array(K + 1).fill(0);for (let i = 1; i = w; j--) { dp[j] = Math.max(dp[j], dp[j - w] + v); }}console.log(dp[K]);

Link1932번 - 정수 삼각형 문제풀이(1)let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const n = Number(input[idx++]);const triangle = [];for (let i = 1; i = 0; i--) { for (let j = 0; j

Link11053번 - 가장 긴 증가하는 부분 수열 문제풀이(1)let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");const N = input[0];const arr = input[1].split(" ").map(Number);const dp = Array.from({ length: N }, () => 1);for (let i = 0; i arr[j]) { // 조건 (1) dp[i] = Math.max(dp[i], dp[j] + 1); // 조건 (2) } }}console.log(Math.max(...dp));

Link2579번 - 계단 오르기 문제풀이(1) DP - top downlet input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const N = Number(input[idx++]);const stair = Array.from({ length: N }, () => Number(input[idx++]));const memo = {}const topDown = (n) => { if (n === 0) return stair[0]; if (n === 1) return stair[0] + stair[1] if (n === 2) return Math.max(stair[0], stair[1]) + ..

Link1003번 - 피보나치 함수 문제풀이(1)let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");let idx = 0;const T = Number(input[idx++]);const dp = [];dp.push([1, 0]);dp.push([0, 1]);dp.push([1, 1]);for (let i = 3; i

Link11726번 - 2xN 타일링 문제풀이(1) DPlet input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");const N = Number(input[0]);const dp = Array.from({ length: N + 1 }, () => Infinity);dp[1] = 1;dp[2] = 2;for (let i = 3; i