hyunkookim 님의 블로그

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

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

1203. Sort Items by Groups Respecting 🔸 문제 설명There are n items each belonging to zero or one of m groups→ n개의 아이템이 있으며, 각 아이템은 m개의 그룹 중 하나에 속하거나, 어떤 그룹에도 속하지 않을 수 있습니다.where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group.→ group[i]는 i번째 아이템이 속한 그룹 번호이며, 그룹이 없는 경우 -1입니다.The items and the groups are zero indexed.→ 아이템과 그룹 번호는 모두 0번부터 ..

1462. Course Schedule IV class Solution: def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: # numCourses: 전체 수업 개수 (0부터 numCourses-1까지 번호가 매겨짐) # prerequisites[i] = [a, b]: 수업 a를 먼저 들어야 b를 들을 수 있음 (a → b) # queries[j] = [u, v]: u가 v의 직접 또는 간접 선행 과목인지 확인해야 함 # 1. 인접 리스트 (adjacency list)와 reachable ..

1) DFS 기반 위상 정렬# 주어진 방향성 있는 비순환 그래프(DAG)에서# 올바른 위상 정렬 순서를 반환하는 함수def topologicalSort(edges, n): # 1. 인접 리스트(adj)를 만들어서 그래프 구성 adj = {} for i in range(1, n + 1): adj[i] = [] # 각 노드를 key로 하여 빈 리스트 초기화 # 주어진 간선을 이용해 방향 그래프 구성 (src → dst) for src, dst in edges: adj[src].append(dst) # 2. 위상 정렬 결과를 담을 리스트 topSort = [] # 방문한 노드를 기록할 집합 visit = set() # 3. 모든 ..

1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1,👉 가중치가 있는 무방향 연결 그래프가 주어지며, 이 그래프는 0부터 n - 1까지 번호가 매겨진 정점들을 포함합니다. and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi.👉 edges[i] = [ai, bi, weighti] 형식의 배열이 주어지고, 이는 정점..