본문 바로가기

DP

[Leetcode/파이썬] 63. Unique Paths II Unique Paths IIYou are given an m x n integer array grid. There is a robot 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.An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any squar.. 더보기
[Leetcode/파이썬] 97. Interleaving String Interleaving StringGiven strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...Note: a + b is th.. 더보기
[Leetcode/파이썬] 198.House Robber House RobberYou 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 the amou.. 더보기
[Leetcode/파이썬] 221. Maximal Square Maximal SquareGiven an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example 1:Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]Output: 4Example 2:Input: matrix = [["0","1"],["1","0"]]Output: 1Example 3:Input: matrix = [["0"]]Output: 0 Constraints:m == matrix.lengthn == matrix[.. 더보기
[Leetcode/파이썬] 72. Edit Distance Edit DistanceGiven two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.You have the following three operations permitted on a word:Insert a characterDelete a characterReplace a character Example 1:Input: word1 = "horse", word2 = "ros"Output: 3Explanation: horse -> rorse (replace 'h' with 'r')rorse -> rose (remove 'r')rose -> ros (remove 'e')Exa.. 더보기
[Leetcode/파이썬]123. Best Time to Buy and Sell Stock III Best Time to Buy and Sell Stock IIIYou are given an array prices where prices[i] is the price of a given stock on the ith day.Find the maximum profit you can achieve. You may complete at most two transactions.Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Example 1:Input: prices = [3,3,5,0,0,3,1,4]Output: 6Explanation: Buy o.. 더보기
[백준/파이썬][Gold III] 행렬 곱셈 순서 - 11049 [Gold III] 행렬 곱셈 순서 - 11049문제 링크성능 요약메모리: 112952 KB, 시간: 540 ms분류다이나믹 프로그래밍제출 일자2025년 2월 10일 17:42:53문제 설명크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는.. 더보기
[백준/파이썬][Gold V] 개업 - 13910 [Gold V] 개업 - 13910문제 링크성능 요약메모리: 110908 KB, 시간: 256 ms분류다이나믹 프로그래밍제출 일자2025년 2월 8일 03:04:36문제 설명해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.예를 들어 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.해빈이가 5그릇을 주문 받았고, 해빈이가 가지고 있는 웍의 종류가 1, 3.. 더보기

티스토리툴바