hyunkookim 님의 블로그

21. Merge Two Sorted Lists# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy # for l1, l2 in range(min(len(list1), len(list2))): ❌ ..

20. Valid Parenthesesclass Solution: def isValid(self, s: str) -> bool: charDict = {')':'(', '}':'{', ']':'['} stack = [] for w in s: if w in charDict and stack: if stack[-1] != charDict[w]: return False else: stack.pop() else: stack.append(w) # ..

1. Two Sum class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: pair = {} # value: idx for i, num in enumerate(nums): diff = target-num if diff in pair: # i != pair[diff] 이 조건은 항상 참임 return [pair[diff], i] # 작은 index 가 앞으로. pair[num] = i

567. Permutation in Stringfrom collections import defaultdictclass Solution: def checkInclusion(self, s1: str, s2: str) -> bool: def getCountDictString(strs): cm = defaultdict(int) for s in strs: cm[s] += 1 cm = dict(sorted(cm.items())) res = "" for k, v in cm.items(): res += f"{k}_{v}," ret..

1092. Shortest Common Supersequence  이 문제 **1092. Shortest Common Supersequence (SCS)**는 **LCS(최장 공통 부분 수열)**를 기반으로 푸는 고전적인 문제입니다.아래에 개념 정리부터 상세한 접근 방식, 그리고 주석이 풍부한 코드까지 정리해드릴게요.✅ 문제 요약두 문자열 str1, str2가 주어질 때,두 문자열 모두의 subsequence가 되는 가장 짧은 문자열을 만들어 반환하세요.✔ 단순히 길이만 구하는 게 아니라, 문자열 자체를 반환해야 합니다.🧠 핵심 아이디어: "LCS 기반으로 SCS 만들기"✔ 두 문자열의 **LCS(최장 공통 부분 수열)**를 구하면,✔ 그걸 중심 축으로 하여 나머지 문자를 적절히 붙이면 SCS를 만들 ..

322. Coin Changeclass Solution: def coinChange(self, coins: List[int], amount: int) -> int: # 메모이제이션을 위한 딕셔너리 # dp[amount] = 해당 금액을 만드는 최소 동전 수 dp = {} # dfs(amount): 해당 금액을 만들기 위한 최소 동전 개수를 반환 def dfs(amount): # 금액이 0이면 동전이 필요 없음 → 종료 조건 if amount == 0: return 0 # 이미 계산한 금액이면 캐시에서 바로 반환 if a..

1049. Last Stone Weight II 📌 문제 요약stones[i]: 각 돌의 무게두 개를 선택해 부딪히면,같으면 둘 다 없어짐다르면 무게가 |x - y|인 돌이 하나 남음이 과정을 반복 → 마지막에 남는 돌의 최소 무게를 반환하라는 문제 ✅ 잘못된 풀이실제 문제에서 설명된 smash 동작을 직접 시뮬레이션하려고 한 코드야.그런데 이 방식이 **틀린 이유는 "최적의 순서를 보장할 수 없기 때문"**이야.class Solution: def lastStoneWeightII(self, stones: List[int]) -> int: # 2개 골라서 두개가 같으면, 배열에서 제거 # 2개 골라서, 두개가 다르면, 두개 제거하고, 그 차이(큰거-작은거) 를 추가 ..

474. Ones and Zeroes https://youtu.be/miZ3qV04b1g strs 셋들 중에.. 0이 m 개수, 1이 n 개 가지는 substr 셋의 최대 개수를 return하라는 거 같은데 맞아? 응, 정확히 이해했어! 문제 요약해 줄게:🔍 문제 요약:strs는 0과 1로 구성된 문자열 리스트야.각 문자열을 하나의 "아이템"처럼 생각하고, 이들 중에서 몇 개를 선택할지 결정해야 해.단, 선택된 문자열들 속에 포함된 0의 총 합(개수)이 m 이하여야 하고, 1의 총 합(개수)이 n 이하여야 해.그런 조건을 만족하는 부분집합의 최대 크기(문자열 개수)를 구하는 문제야.예시로 다시 보면:python복사편집strs = ["10", "0001", "111001", "1", "0"], m = 5..

416. Partition Equal Subset Sum 잘못된 풀이!!class Solution: def canPartition(self, nums: List[int]) -> bool: # subset 들의 합이 같은게 있으면 return True, 아니면 False subsets = [] def dfsBacktrack(path, start): if start == len(path): subsets.append(path.copy()) for i in range(start, len(nums)): path.append(nums[i]) # nums[i] 추가 ..

269. Alien Dictionary 🔍 문제 설명 (한 줄씩 해석)There is a new alien language that uses the English alphabet.→ 새로운 외계 언어가 있는데, 영어 알파벳을 사용합니다.However, the order of the letters is unknown to you.→ 하지만, 그 알파벳의 순서는 당신에게 알려지지 않았습니다.You are given a list of strings words from the alien language's dictionary.→ 외계 언어 사전에 등장하는 단어들이 정렬된 리스트 words로 주어집니다.Now it is claimed that the strings in words are sorted lexico..