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. 문제정수 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..

1. 문제정수 배열 piles가 주어질 때, 1시간에 임의의 값 k만큼 각 요소를 삭제할 수 있다고 하자.정수 h시간 전에 모든 요소를 삭제할 수 있는 최소 k를 구하라.2. 해결function getTotalHours(piles: number[], k: number) : number { let total = 0; for(let pile of piles) { total += Math.ceil(pile / k); } return total;}function minEatingSpeed(piles: number[], h: number): number { let left = 1, right = Math.max(...piles); while(left 이진 탐색 문제에서..

1. 문제정수 배열 nums가 주어질 때 자신의 왼쪽, 오른쪽 요소보다 큰 요소를 peak라 한다.이 peak는 여러 개 있을 수 있고, 그 중 아무 요소의 인덱스를 반환하라.2. 해결function findPeakElement(nums: number[]): number { let left = 0, right = nums.length - 1; while (left 0 ? nums[mid - 1] : -Infinity; const rightVal = mid leftVal && nums[mid] > rightVal) { return mid; } else if (nums[mid] 애초에 O(log n) 시간 복잡도로 탐색하라고 했으므로 이진 탐색을 사..