동적계획법

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

문제 설명 Minimum Path Sum - LeetCode 2D 격자(grid)에서 좌측 상단(0,0) → 우측 하단(m-1, n-1)으로 이동하는 최소 비용 경로를 찾는 문제입니다. 오른쪽 또는 아래쪽으로만 이동 가능 각 칸의 값은 해당 칸을 방문할 때 드는 비용 최소 비용 경로의 합을 반환 ✅ 제약 조건 1 ≤ m, n ≤ 200 (격자 크기) 0 ≤ grid[i][j] ≤ 100 (비용 값) O(m × n) 이하의 시간 복잡도로 해결하는 것이 바람직 해설 1️⃣ DFS + 백트래킹 (O(2^(m+n))) → 비효율적 모든 가능한 경로 탐색 → 시간 초과 O(2^(m+n)) → 너무 비효율적이므로 사용 불가 2️⃣ 동적 계획법 (DP, O(m × n)) [추천] 최적 부분 구조를 가지므로 DP를 활용 가능 점화식: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 즉, 위쪽 또는 왼쪽에서 오는 최소 비용 + 현재 위치 비용 시간 복잡도: O(m × n) 공간 복잡도: O(1) (grid를 직접 수정하여 사용 가능) 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def minPathSum(grid): m, n = len(grid), len(grid[0]) # 첫 번째 행 초기화 (왼쪽에서 오는 값 누적) for j in range(1, n): grid[0][j] += grid[0][j - 1] # 첫 번째 열 초기화 (위쪽에서 오는 값 누적) for i in range(1, m): grid[i][0] += grid[i - 1][0] # DP 점화식 적용 for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]) return grid[m - 1][n - 1] # 우측 하단 값 반환 Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 var minPathSum = function(grid) { let m = grid.length, n = grid[0].length; // 첫 번째 행 초기화 for (let j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; } // 첫 번째 열 초기화 for (let i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; } // DP 점화식 적용 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; // 우측 하단 값 반환 }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Longest Palindromic Substring - LeetCode 주어진 문자열 s에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제입니다. ✅ 팰린드롬(Palindrome)이란? 앞에서 읽어도, 뒤에서 읽어도 동일한 문자열 예: "racecar", "madam", "a" ✅ 제약 조건 1 ≤ s.length ≤ 1000 반환값: 가장 긴 팰린드롬 부분 문자열 해설 1️⃣ 다이나믹 프로그래밍 (DP, O(N²)) DP 테이블을 사용하여 s[i:j+1]이 팰린드롬인지 저장 dp[i][j] = True → s[i:j+1]이 팰린드롬 점화식: s[i] == s[j]이고, j - i <= 2 (길이 2 이하) 또는 dp[i+1][j-1] == True 이면, dp[i][j] = True 시간 복잡도: O(N²) → 테이블 갱신이 O(N²) 2️⃣ 확장 중심 접근법 (Expand Around Center, O(N²)) 각 문자를 중심으로 팰린드롬 확장 (중심 확장) 홀수 길이 팰린드롬: "racecar" → 중심 e 짝수 길이 팰린드롬: "abba" → 중심 bb 시간 복잡도: O(N²) → 각 문자를 중심으로 O(N) 확장 코드 풀이 Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def longestPalindrome(s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start, max_length = 0, 1 # 가장 긴 팰린드롬의 시작 위치와 길이 # 길이 1짜리 문자열은 항상 팰린드롬 for i in range(n): dp[i][i] = True # 길이 2 이상 문자열 검사 for j in range(1, n): for i in range(j): if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]): dp[i][j] = True if j - i + 1 > max_length: # 더 긴 팰린드롬이면 갱신 start, max_length = i, j - i + 1 return s[start:start + max_length] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def longestPalindrome(s: str) -> str: if len(s) < 2: return s def expand_around_center(left: int, right: int) -> str: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right] # 범위를 넘어간 부분을 제외 longest = "" for i in range(len(s)): odd_palindrome = expand_around_center(i, i) # 홀수 길이 even_palindrome = expand_around_center(i, i + 1) # 짝수 길이 longest = max(longest, odd_palindrome, even_palindrome, key=len) return longest Javascript 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 var longestPalindrome = function(s) { if (s.length < 2) return s; const expandAroundCenter = (left, right) => { while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } return s.slice(left + 1, right); }; let longest = ""; for (let i = 0; i < s.length; i++) { let oddPalindrome = expandAroundCenter(i, i); // 홀수 길이 let evenPalindrome = expandAroundCenter(i, i+1); // 짝수 길이 longest = oddPalindrome.length > longest.length ? oddPalindrome : longest; longest = evenPalindrome.length > longest.length ? evenPalindrome : longest; } return longest; }; 참고 및 출처 programmers Coding Test LeetCode - The World’s Leading Online Programming Learning Platform ...

문제 설명 Edit Distance - LeetCode 두 개의 문자열 word1과 word2가 주어질 때, 첫 번째 문자열을 두 번째 문자열로 변환하기 위한 최소 편집 횟수를 구하는 문제입니다. ✅ 편집 연산 (Operations) 삽입 (Insert) → 문자를 추가 삭제 (Delete) → 문자를 제거 변경 (Replace) → 문자를 다른 문자로 변경 ✅ 제약 조건 0 ≤ word1.length, word2.length ≤ 500 최적화된 O(m × n) 알고리즘이 필요 해설 1️⃣ 재귀 (O(3^N)) → 비효율적 모든 가능한 연산을 수행하여 최소 값을 찾음 시간 복잡도 O(3^N) → 매우 비효율적 사용하지 않음 2️⃣ 동적 계획법 (DP, O(m × n)) [추천] ✔ DP 테이블을 사용하여 중복 연산을 제거 ✔ 점화식: ...