hyunkookim 님의 블로그

Easy:Two Sum (LeetCode 1)설명: 주어진 배열에서 두 수의 합이 특정 값이 되는 인덱스를 찾습니다.핵심 개념: 해시 맵을 이용한 효율적인 탐색.Contains Duplicate (LeetCode 217)설명: 배열에 중복된 요소가 있는지 확인합니다.핵심 개념: 집합(Set)을 활용한 중복 검사.Intersection of Two Arrays (LeetCode 349)설명: 두 배열의 교집합을 구합니다.핵심 개념: 해시 맵과 집합을 이용한 교집합 연산.First Unique Character in a String (LeetCode 387)설명: 문자열에서 처음으로 반복되지 않는 문자의 인덱스를 찾습니다.핵심 개념: 해시 맵을 통한 문자 빈도 계산.Majority Element (LeetC..

518. Coin Change II https://hyunkookim.tistory.com/279 Knapsack 문제(배낭 문제) : DP 최적화**Knapsack 문제(배낭 문제)**는 조합 최적화 문제로, 주어진 조건 하에서 최대 또는 최적의 결과를 찾는 문제입니다. 이 문제는 동적 계획법(Dynamic Programming)이나 탐욕법(Greedy Algorithm)을 활용하여 풀hyunkookim.tistory.com Knapsack 문제와 동전 문제의 유사점Knapsack 문제와 동전 문제는 모두 조합 최적화 문제이며, 동적 계획법(DP)을 사용해 해결합니다.Knapsack 문제:최적의 가치를 찾는 것이 목표.각 물건의 가치와 무게가 있음.동전 문제:주어진 금액을 구성하는 조합의 수를 찾는 것..

**Knapsack 문제(배낭 문제)**는 조합 최적화 문제로, 주어진 조건 하에서 최대 또는 최적의 결과를 찾는 문제입니다. 이 문제는 동적 계획법(Dynamic Programming)이나 탐욕법(Greedy Algorithm)을 활용하여 풀 수 있습니다. 배낭 문제는 크게 두 가지로 나눌 수 있습니다. 1. 0-1 Knapsack 문제def knapsack(weights, values, W): n = len(weights) dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(W + 1): if weights[i-1]  2. Unbounded Knapsack..

279. Perfect Squares # 완전 제곱수의 합이 n 이 되는 요소 개수 찾기 # 그런데 그 요소 개수가 최대한 적어야 해서. # 제곱수는 큰수로 이뤄저 있어야 하므로, 큰수부터 검색하는것이..# DP 또는 BFS 로 풀수 있음  1. Dynamic Programming (DP) 풀이  예제)class Solution: def numSquares(self, n: int) -> int: """ 문제 설명: 정수 n을 완전 제곱수들의 합으로 표현할 때, 필요한 최소 항의 개수를 구하는 문제. 완전 제곱수는 1, 4, 9, 16과 같은 수를 의미합니다. """ # DP 배열 초기화 # dp[i]는 숫자 i를..

337. House Robber III 노드 2개가 연결된것을 선택하면 안된다는 거니,=> 부모, 자식은 선택 못함,즉,1) 같은 레벨 끼리, 아니면,2) 나를 기준으로, 내 부모->내 자식 요렇게 문제에서 요구하는 내용은 다음과 같습니다:"부모-자식 관계에 있는 노드가 같은 날 털리지 않도록 해야 함":즉, 부모 노드와 직접 연결된 자식 노드 중 하나만 선택 가능.예를 들어, 한 노드를 선택하면 그 노드의 부모나 자식 노드는 선택할 수 없음."최대 금액을 구해야 함":각 노드의 값을 합산할 때 가능한 최대 금액을 계산.해결 방법 (Dynamic Programming + Tree Traversal)이 문제를 해결하기 위해 재귀적 접근법과 **DP (Dynamic Programming)**를 사용합니다.아..

95. Unique Binary Search Trees II https://youtu.be/m907FlQa2Yc?si=0uoBNIz-4bKCMaD8 # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def generateTrees(self, n: int) -> List[Optional[TreeNode]]: # n개의 노드로 생성 가능한 모든 고유한 BST를 반환하는 함수 ..

슬라이딩 윈도우 문제EasyMaximum Average Subarray I (LeetCode 643)설명: 고정 크기 윈도우의 평균 값 중 최대값을 찾습니다.핵심 개념: 슬라이딩 윈도우.Find All Anagrams in a String (LeetCode 438)설명: 문자열에서 모든 애너그램의 시작 인덱스를 찾습니다.핵심 개념: 슬라이딩 윈도우, 해시맵.Contains Duplicate II (LeetCode 219)설명: 배열에서 특정 거리 내에서 중복값이 존재하는지 확인합니다.핵심 개념: 슬라이딩 윈도우, 해시맵.Longest Substring Without Repeating Characters (LeetCode 3)설명: 중복 없는 가장 긴 부분 문자열을 찾습니다.핵심 개념: 슬라이딩 윈도우, ..

96. Unique Binary Search Trees class Solution: def numTrees(self, n: int) -> int: # DP 배열 초기화 (Initialize the DP array) # dp[i]: i개의 노드를 사용하여 만들 수 있는 고유한 BST의 개수 # dp[i]: Number of unique BSTs that can be formed using i nodes dp = [0] * (n + 1) dp[0] = 1 # 빈 트리의 경우, 가능한 BST는 1개 (Empty tree has one valid BST) dp[1] = 1 # 노드가 1개인 경우, 가능한 BST는 1개 (One ..

from typing import Listclass Solution: def maxProfit(self, prices: List[int]) -> int: # 최대 이익을 계산해서, return # 언제든지 사고팔수 있지만, # 살려면. 기존 주식을 팔아야 하고 # 팔면 그다음날 cooldown 후, 그 다음날 살수 있음 """ root -> buy -> sell -> cooldown -> buy -> sell -> cooldown | -> cooldown -> cooldown -> buy -> cooldown ..

Naive String Matching 관련 문제28. Find the Index of the First Occurrence in a String (strStr) (Easy)설명: 주어진 두 문자열에서 특정 패턴 문자열의 시작 인덱스를 반환합니다.핵심 개념: 문자열 비교, Naive String Matching.796. Rotate String (Easy)설명: 두 문자열이 주어졌을 때, 하나를 회전하여 다른 문자열을 만들 수 있는지 확인합니다.핵심 개념: Naive 문자열 비교.415. Add Strings (Easy)설명: 두 문자열로 표현된 숫자를 더한 결과를 반환합니다.핵심 개념: Naive 문자열 처리, 수학.242. Valid Anagram (Easy)설명: 두 문자열이 애너그램인지 확인합니다..