1. 문제문자열 word1, word2가 주어질 때, word1을 word2로 만들 수 있는 최소 연산 횟수를 구하라.연산의 종류는문자를 추가한다.문자를 제거한다.문자를 교체한다.2. 해결function minDistance(word1: string, word2: string): number { const m = word1.length; const n = word2.length; // dp 배열 생성 (m+1) x (n+1) 크기 const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // 초기 상태 설정 for (let i = 0; i 일단 못풀었다. 두 문자열로 2차원 배열을 만..

1. 문제날짜 별 주식 가격 prices가 주어지고, 판매 수수료 fee가 주어질 때 최대 수익을 반환하라.단, 주식은 하나 들고 있으면 팔기 전 까지 추가로 매수할 수 없다.2. 해결function maxProfit(prices: number[], fee: number): number { const n = prices.length; const dp: number[][] = Array.from({ length: n }, () => [0, 0]); dp[0][0] = 0; // 0일차: 주식 없음 → 수익 0 dp[0][1] = -prices[0]; // 0일차: 주식 삼 → 마이너스 수익 for (let i = 1; i 일단 풀 지 못했다. 경우의 수를 생각..

1. 문제문자열 text1과 text2가 주어질 때, 순서는 유지하면서 연속되지 않아도 되는 가장 긴 공통 부분 문자열의 길이를 구하라.2. 해결function longestCommonSubsequence(text1: string, text2: string): number { const m = text1.length, n = text2.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i 어찌 저찌 풀려고 해봤는데, 안됐다.이 문제는 LCS 문제로 탐색중인 두 문자가 동일하면, i-1, j-1의 LCS 값 +1을 해주고 다르면 해당 문자 혹은 비교 문자를 포함하지 않은 L..

1. 문제정수 m과 n이 주어질 때, 0,0 좌표에서 시작하여 m-1, n-1 좌표에 도달할 수 있는 고유 경로의 수를 반환하라.2. 해결function uniquePaths(m: number, n: number): number { if(m === 1 && n ===1) return 1; const dp: number[][] = Array.from({length: m}, (_,i) => Array.from({length: n} , (_, j) =>{ if(i === 0 && j === 0) return 0; if(i === 0 || j === 0) return 1; return 0; })) for(let i = 1; i 0,0에서 시작하니까 0으..

1. 문제도미노 타일과 트리미노 타일이 주어질 때, 2xn 크기의 타일을 모두 덮을 수 있는 경우의 수를 구하라.값이 큰 경우 10^9 + 7로 나눈 나머지 값을 반환하라.2. 해결function numTilings(n: number): number { const mod = 10 ** 9 + 7; const dp: number[] = [1, 1, 2]; for (let i = 3; i 일단 이 문제를 완벽하게 이해하지는 못했다.마지막에 두는 타일의 경우의 수로 따져야 하는 것 까진 알겠는데, 점화식을 유도하는 과정이 벽이었다.leetcode solution에 올라온 내용이다.보면, dp[3]과 dp[4]의 점화식에서 dp[n] = dp[n-1] + dp[n-2] + 2*(dp[n-3]+ ... + ..

1. 문제집에 가지고 있는 금액 배열인 nums가 주어진다. 한 집을 털면 양 옆 집은 경찰이 출동하기 때문에 털 수 없다고 할 때, 최대로 털 수 있는 금액을 반환하라.2. 해결function rob(nums: number[]): number { const n = nums.length; if (n === 0) return 0; if (n === 1) return nums[0]; if (n === 2) return Math.max(nums[0], nums[1]); const dp = [nums[0], Math.max(nums[0], nums[1])]; for(let i = 2; i첫 풀이 때 3번째 부터 점화식을 세워서 풀긴 했는데, 그렇게 할 필요가 없었다.우선 ..

1. 문제각 계단을 오르는 비용이 정수 배열 cost로 주어질 때, 정상에 도달할 수 있는 최소 비용을 반환하라.2. 해결function minCostClimbingStairs(cost: number[]): number { const dp = [cost[0], cost[1]]; for(let i = 2; i 계단의 시작은 0번 인덱스 혹은 1번 인덱스부터 시작할 수 있기 때문에, dp에서 해당 코스트를 미리 채워둔다.이후 특정 인덱스에 도달할 수 있는 방법은 직전 인덱스에서 오거나 2계단 전에서 올라오는 경우이다.최소 코스트를 구해야 하므로 두 경우 중 최소값을 취하고, 해당 계단의 코스트를 더해 도달할 수 있는 최소 비용을 쭉 구한다.마찬가지로 정상에 도달할 수 있는 경우의 수는 바로 직전 ..

1. 문제위와 같은 점화식을 만족하는 n의 값을 구하라.2. 해결function tribonacci(n: number): number { const dp = [0,1,1]; if(n === 0) return dp[0]; if(n === 1) return dp[1]; if(n === 2) return dp[2]; for(let i = 3; i DP Memorize를 이용해 점화식을 사용하여 해결.

1. 문제정수 k와 n이 주어질 때, 1~9 숫자 중 k개의 수를 사용해서 n을 만들 수 있는 모든 경우의 수를 반환하라.2. 해결function combinationSum3(k: number, n: number): number[][] { const ans = []; function backtrack(number:number, current: number[], sum: number) { if(current.length > k) return; if(current.length === k && sum === n) { ans.push([...current]); return; } for(let i =..

1. 문제문자열 digits이 2-9로 이루어져 있고, 그림처럼 구성된 번호가 있을 때, 조합할 수 있는 모든 문자 조합을 반환하라.2. 해결function letterCombinations(digits: string): string[] { if(digits.length === 0) return [] const map = new Map(); map.set('2', ['a', 'b','c']) map.set('3', ['d', 'e','f']) map.set('4', ['g', 'h','i']) map.set('5', ['j', 'k','l']) map.set('6', ['m', 'n','o']) map.set('7', ['p', 'q','r','s']) m..