hyunkookim 님의 블로그

72. Edit Distance https://youtu.be/XYi2-LPrwm4?si=8R5kcaUc9tWO8sSQ 초기값 세팅 설명초기 설정의 의미첫 번째 행과 열은 문자열이 비어 있을 때 작업의 기준점을 제공합니다.이후, 이 값을 기반으로 나머지 테이블 값을 채우며 두 문자열의 변환 비용을 계산합니다.이후 과정결론DP 테이블의 최종 값은 문자열을 변환하는 모든 가능한 경로를 고려해 최적의 변환 비용을 계산한 결과입니다. 이를 통해 삽입, 삭제, 교체 작업을 효율적으로 비교할 수 있습니다. Codeclass Solution: def minDistance(self, word1: str, word2: str) -> int: # DP 테이블 생성 # cache[i][..

714. Best Time to Buy and Sell Stock with Transaction Fee https://youtu.be/cUsPoH5DG1Q?si=vWqiiqYgUO8o6U1N Code class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: n = len(prices) # buy[i]: i번째 날에 주식을 구매한 상태에서의 최대 이익 # sell[i]: i번째 날에 주식을 판매한 상태에서의 최대 이익 buy = [0] * n sell = [0] * n # 초기값: # 첫 번째 날에 주식을 구매한 경우: -prices[0] ..

문제 링크 : 1143. Longest Common Subsequence https://youtu.be/Ua0GhsJSlWM?si=-h73SwkVPoCVziy6  코드  class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: dp = [[0 for j in range(len(text2)+1)] for i in range(len(text1)+1)] for i in range(len(text1)-1, -1, -1): for j in range(len(text2)-1, -1, -1): if text1[i] == text2[j]: ..

62. Unique Paths 문제62. Unique PathsThere is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.Given the two integers m and n, return the number of possible unique paths that the robot can take to reach t..

문제790. Domino and Tromino Tiling You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent ce..

문제198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.Given an integer array nums representing ..