동적계획법

문제 설명 Longest Increasing Path in a Matrix - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Trapping Rain Water - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Fibonacci Number - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Jump Game II - LeetCode 배열 nums가 주어질 때, 각 인덱스에서 점프할 수 있는 최대 거리가 배열 요소로 주어집니다. 첫 번째 인덱스(0)에서 마지막 인덱스(n-1)로 이동하는 최소 점프 횟수를 구하는 문제입니다. ✅ 제약 조건 항상 마지막 인덱스로 도달할 수 있음 (즉, 도달 불가능한 경우는 없음) 1 ≤ nums.length ≤ 10⁴ 0 ≤ nums[i] ≤ 1000 해설 1️⃣ DP (O(N²)) → 비효율적 각 인덱스에서 모든 가능한 점프를 고려하여 최적해를 찾음 시간 복잡도 O(N²) 으로 큰 입력에서 비효율적 2️⃣ 그리디 알고리즘 (O(N)) [추천] 각 단계에서 최적의 점프 선택 (가장 멀리 갈 수 있는 지점 탐색) 현재 범위 내에서 점프 가능한 최대 위치를 갱신 한 번의 순회(O(N))로 해결 가능 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def jump(nums): n = len(nums) jumps = 0 # 점프 횟수 farthest = 0 # 현재까지 도달할 수 있는 가장 먼 위치 end = 0 # 현재 점프에서 도달할 수 있는 최대 범위 for i in range(n - 1): farthest = max(farthest, i + nums[i]) # 최대 도달 범위 갱신 if i == end: # 현재 범위를 벗어나기 직전이면 점프 jumps += 1 end = farthest # 새로운 점프 범위 설정 return jumps Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 var jump = function(nums) { let jumps = 0; let farthest = 0; let end = 0; for (let i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i === end) { jumps++; end = farthest; } } return jumps; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Palindrome Partitioning II - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Longest Palindromic Subsequence - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 Jump Game - LeetCode 주어진 정수 배열 nums에서 각 인덱스에서 점프할 수 있는 최대 거리가 nums[i]로 주어질 때, 배열의 첫 번째 인덱스에서 마지막 인덱스로 도달할 수 있는지 여부를 판단하는 문제입니다. ✅ 제약 조건 1 ≤ nums.length ≤ 10⁴ 0 ≤ nums[i] ≤ 10⁵ O(N) 이하의 시간 복잡도로 해결하는 것이 바람직 ✅ 출력 값 마지막 인덱스에 도달할 수 있으면 True, 도달할 수 없으면 False 해설 1️⃣ 동적 계획법 (DP, O(N²)) → 비효율적 dp[i] = True이면 해당 위치에서 도달 가능하다는 의미 각 인덱스에서 가능한 점프를 모두 확인하여 dp 배열 업데이트 시간 복잡도 O(N²) → 입력 크기가 크면 비효율적 2️⃣ 그리디 알고리즘 (O(N)) [추천] 현재까지 도달할 수 있는 최대 거리(maxReach)를 갱신 현재 인덱스(i)가 maxReach보다 크면 도달 불가 → False 반환 도달 가능하면 True 반환 시간 복잡도 O(N) (배열을 한 번만 순회) 공간 복잡도 O(1) (추가 배열 사용 X) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 def canJump(nums): maxReach = 0 # 현재 도달할 수 있는 최대 거리 for i in range(len(nums)): if i > maxReach: # 현재 인덱스에 도달할 수 없으면 False return False maxReach = max(maxReach, i + nums[i]) # 최대 도달 거리 갱신 if maxReach >= len(nums) - 1: # 마지막 인덱스에 도달 가능하면 True return True return True Javascript 1 2 3 4 5 6 7 8 9 10 11 var canJump = function(nums) { let maxReach = 0; for (let i = 0; i < nums.length; i++) { if (i > maxReach) return false; maxReach = Math.max(maxReach, i + nums[i]); if (maxReach >= nums.length - 1) return true; } return true; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Best Time to Buy and Sell Stock III - LeetCode 해설 코드 풀이 Python Javascript 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform

문제 설명 3Sum - LeetCode 해설 📌 문제 설명 주어진 배열 nums에서 합이 0이 되는 세 개의 숫자 조합(삼중합, triplets) 을 모두 찾는 문제입니다. ✅ 조건: 각 조합은 중복 없이 한 번만 포함되어야 합니다. 시간 복잡도 O(n²) 이하로 최적화 해야 합니다. 입력 배열의 원소는 중복될 수 있음 ✅ 예제 1 1 nums = [-1, 0, 1, 2, -1, -4] 🔹 출력: 1 [[-1, -1, 2], [-1, 0, 1]] ✔ (-1, -1, 2) ✔ (-1, 0, 1) 📌 중복된 (-1, -1, 2)는 한 번만 포함! ...

문제 설명 Maximum Subarray - LeetCode 주어진 정수 배열 nums에서 연속된 서브어레이(subarray) 중 합이 가장 큰 값을 찾는 문제입니다. ✅ 제약 조건 1 ≤ nums.length ≤ 10⁵ -10⁴ ≤ nums[i] ≤ 10⁴ O(N) 이하의 시간 복잡도로 해결하는 것이 바람직 해설 1️⃣ 브루트포스 (O(N²)) → 비효율적 모든 가능한 부분 배열을 확인하며 최대 합을 찾음 시간 복잡도 O(N²) → 입력 크기가 크면 비효율적 2️⃣ 동적 계획법 (DP, O(N)) 점화식: dp[i] = max(dp[i-1] + nums[i], nums[i]) 즉, 현재 값을 새로운 서브어레이로 시작할지, 기존 서브어레이에 추가할지를 결정 시간 복잡도: O(N) 공간 복잡도: O(N) (배열 dp를 저장) 3️⃣ 카데인 알고리즘 (Kadane’s Algorithm, O(N)) [추천] DP에서 배열 저장 없이 최적화한 방법 현재 서브어레이 합이 음수라면 새로운 서브어레이 시작 시간 복잡도: O(N) 공간 복잡도: O(1) (배열 사용 없이 변수 2개만 사용) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 def maxSubArray(nums): max_sum = nums[0] # 최대 합 current_sum = nums[0] # 현재 부분 배열의 합 for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) # 현재 값 포함 여부 결정 max_sum = max(max_sum, current_sum) # 최댓값 갱신 return max_sum Javascript 1 2 3 4 5 6 7 8 9 10 11 var maxSubArray = function(nums) { let maxSum = nums[0]; let currentSum = nums[0]; for (let i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...