hyunkookim 님의 블로그

136. Single Number class Solution: def singleNumber(self, nums: List[int]) -> int: # 2번 나온거는 무시하고, 1번 나온것만 찾음 # You must implement a solution with a linear runtime complexity and use only constant extra space. # 시간: O(n), 공간: O(1) 으로 풀어야 함 # for 루프 여러개? 단일 변수 여러개? # xor 하면(^) 2번 계산한건 0으로 사라짐 res = nums[0] for i in range(1, len(nums)): ..

338. Counting Bits Given an integer n, return an array ans of length n + 1 such that for each i (0  ans[i] is the number of 1's in the binary representation of i. Example 1:Input: n = 2Output: [0,1,1]Explanation:0 --> 01 --> 12 --> 10Example 2:Input: n = 5Output: [0,1,1,2,1,2]Explanation:0 --> 01 --> 12 --> 103 --> 114 --> 1005 --> 101 Constraints:0  Follow up:It is very easy to come up with a s..

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]: ..

문제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 ..