목록dp (60)
N
https://leetcode.com/problems/decode-ways/ Decode Ways - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com const numDecodings = (s) => { const length = s.length; const dp = Array(length + 1).fill(0); if(s[0] === "0"){ return 0; } dp[length] = 1; dp[length - 1] = parseInt(s[length - 1..
https://leetcode.com/problems/unique-paths-ii/ Unique Paths II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP 알고리즘. Unique Path 문제에서 장애물이 추가된 문제다. m x n 크기로 DP 배열을 선언하여 0으로 초기화한다. 만약 obstacleGrid[0][0]이 1이라면 출발점이 장애물로 막혀있고, 더 이상 진행할 수 없다는 뜻이된다. 그렇다면 0을 바로 리턴하여 종료한다. 그렇지 않다면 이..
https://leetcode.com/problems/unique-paths/ Unique Paths - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP 알고리즘. m x n 크기의 배열을 선언하고 0으로 초기화한다. [0, 0] 좌표에서 [m - 1, n - 1] 좌표까지 갈 수 있는 방법을 모두 구하는데, [0, 0]은 1로 시작하고 이중 for문으로 DP를 적용한다. 로봇은 오른쪽 또는 아래로 가기 때문에 순회를 하면서 점화식을 적용한 값을 배열에 저장..
https://leetcode.com/problems/jump-game-ii/ Jump Game II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP 알고리즘 사용. dp 배열을 nums의 length 만큼 선언하고, Infinity로 초기화 한다. 시작은 0번째 인덱스부터 시작하기 때문에 dp[0] = 0으로 저장하고 for문을 시작한다. nums 배열을 순회. nums[i]는 점프할 수 있는 최대 거리를 나타내기 때문에 이중 for문으로 끝까지 갈 수..
https://leetcode.com/problems/min-cost-climbing-stairs/ Min Cost Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com dp 알고리즘 사용. cost의 길이를 나타내는 length. dp를 length의 길이만큼 할당하고 0으로 초기화. 계단은 1칸 또는 2칸 오를 수 있다. 그렇기 때문에 dp[0] = cost[0], dp[1] = cost[0] + cost[1] 과 cost[1] 중 ..
https://leetcode.com/problems/minimum-path-sum/ Minimum Path Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP 알고리즘 이용. 주어진 grid의 크기는 m x n 이므로 각 변수에 length를 저장한다. dp 테이블은 grid와 마찬가지로 m x n의 크기로 선언하여 0으로 초기화한다. 시작점인 [0, 0]에서 끝점 [m - 1, n - 1]로 향하기 때문에 dp[0][0]은 grid[0][0]으로 ..
https://programmers.co.kr/learn/courses/30/lessons/12971?language=javascript 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr DP를 이용한 문제 풀이. 하나의 스티커를 땠을 때, 양 옆의 스티커를 사용하지 못하기 때문에 DP 테이블을 2개 사용해야 한다. 왜냐하면 아래처럼 두 가지 경우 중 합이 큰 값을 골라야 하기 때문이다. 1) 첫번째 스티커부터 땠을 때(가장 마지막에 있는 스티커를 사용하지 못함) 2) 두번째 스티커부터 땠을 때..
53. Maximum Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Example 2: Input: nums = [1] Output: 1 Example 3: Input: nums = [5,4,-1,7,8] Output: 23..