hyunkookim 님의 블로그

Stable Matching Problem설명: 두 집단 간에 안정적인 매칭을 찾는 문제입니다.핵심 개념: 게일-섀플리 알고리즘, 그래프 이론.Gale-Shapley Algorithm설명: 모든 참여자가 만족하는 안정적인 결혼 매칭을 계산합니다.핵심 개념: 매칭 알고리즘. LeetCode EasyTwo Sum (LeetCode 1)설명: 주어진 배열에서 두 수의 합이 목표값이 되는 인덱스를 찾습니다.핵심 개념: 해시맵, 완전 탐색.Valid Parentheses (LeetCode 20)설명: 괄호가 유효한 조합인지 확인합니다.핵심 개념: 스택.Merge Two Sorted Lists (LeetCode 21)설명: 두 개의 정렬된 연결 리스트를 병합합니다.핵심 개념: 연결 리스트, 재귀.Best Time ..

1027. Longest Arithmetic Subsequence class Solution: def longestArithSeqLength(self, nums: List[int]) -> int: # longestArithSeq 는 같은 간격을 같는 LIS 를 찾는 거라서. # 즉, "등차수열을 이루는 가장 긴 부분 수열의 길이" # 해쉬맵에 lenLIS 와 간격 difference 를 저장해야 할듯 dp = {} # 키: (index, difference) -> 값: 등차수열의 길이 max_len = 1 # 최소 길이는 1 for i in range(len(nums)): # 정방향 순회 for j in..

1218. Longest Arithmetic Subsequence of Given Difference class Solution: def longestSubsequence(self, arr: List[int], difference: int) -> int: # 주어진 배열 arr에서 # 차이가 difference인 '부분 수열(subsequence)'의 # 최대 길이를 찾는 것 dp = [1] * len(arr) res = -float("inf") for i in range(len(arr)-1, -1, -1): for j in range(i+1, len(arr)): if arr..

646. Maximum Length of Pair Chain class Solution: def findLongestChain(self, pairs: List[List[int]]) -> int: # right 기준으로 오름차순 정렬 pairs = sorted(pairs, key=lambda x: x[1]) print(pairs) # 이전꺼의 r 보다 다음거의 l 가 작거나 같으면 추가 안함 right = pairs[0][1] res = [pairs[0]] for i in range(1, len(pairs)): if right

673. Number of Longest Increasing Subsequence https://youtu.be/Tuc-rjJbsXU?si=n0lvzu2hxl6XtygW class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: # DP를 사용하는데, # lenLIS: LIS 길이도 저장해야되고, # Count: LIS 개수도 저장해야 함 """ i | 0 | 1 | 2 | 3 | 4 | nums | 1 | 3 | 5 | 4 | 7 | lenLIS ..

Easy 난이도 (Bipartite Graph 문제)Problem 1: Is Graph Bipartite? (LeetCode 785)설명: 주어진 그래프가 이분 그래프인지 확인합니다.핵심 개념: BFS, DFS, 그래프 탐색.Problem 2: Find if Path Exists in Graph (LeetCode 1971)설명: 주어진 두 노드 사이에 경로가 존재하는지 확인합니다.핵심 개념: DFS, BFS.Problem 3: Number of Connected Components in an Undirected Graph (LeetCode 323)설명: 무방향 그래프의 연결 요소 개수를 계산합니다.핵심 개념: DFS, BFS.Problem 4: Maximal Network Rank (LeetCode 16..

Easy 난이도 (짝짓기 문제)Problem 1: Is Graph Bipartite? (LeetCode 785)설명: 주어진 그래프가 이분 그래프인지 확인합니다.핵심 개념: BFS, DFS, 이분 그래프.Problem 2: Maximum Bipartite Matching (GeeksForGeeks)설명: 이분 그래프에서 최대 매칭을 찾습니다.핵심 개념: 플로우 네트워크, 이분 그래프 매칭.Problem 3: Assign Cookies (LeetCode 455)설명: 아이들에게 쿠키를 배정해 최대 만족도를 계산합니다.핵심 개념: 매칭 문제, 그리디 알고리즘.Problem 4: Two Sum (LeetCode 1)설명: 두 숫자를 짝지어 목표 합을 찾습니다.핵심 개념: 매칭 문제, 해시맵.Problem 5:..

최대 유량 관련 문제 (Maximum Flow) Problem 1: Dinic's Algorithm Implementation설명: 주어진 플로우 네트워크에서 최대 유량을 찾는 문제입니다.핵심 개념: Ford-Fulkerson, BFS, DFS, Dinic's Algorithm.Problem 2: Bipartite Graph Maximum Matching (GeeksForGeeks)설명: 이분 그래프에서 최대 매칭을 찾는 문제입니다.핵심 개념: 최대 유량, 이분 그래프 매칭.Problem 3: Max Flow in Network (SPOJ - FASTFLOW)설명: 네트워크에서 최대 유량을 찾는 문제입니다.핵심 개념: Ford-Fulkerson, Push-Relabel Algorithm.Problem 4..

Easy 난이도Problem 1: Find if Path Exists in Graph (LeetCode 1971)설명: 주어진 두 노드 사이에 경로가 존재하는지 확인합니다.핵심 개념: DFS, BFS.Problem 2: Maximal Network Rank (LeetCode 1615)설명: 주어진 네트워크의 최대 연결성을 찾습니다.핵심 개념: 그래프 탐색.Problem 3: Clone Graph (LeetCode 133)설명: 그래프를 깊은 복사합니다.핵심 개념: BFS, DFS.Problem 4: Flood Fill (LeetCode 733)설명: 이미지를 채우는 문제로 그래프 탐색 기법을 연습할 수 있습니다.핵심 개념: BFS, DFS.Problem 5: Island Perimeter (LeetCod..

115. Distinct Subsequences 이 문제는 문자열 s에서 문자열 t를 **부분 수열(subsequence)**로 만들 수 있는 서로 다른 방법의 수를 구하는 문제입니다.S의 부분 수열 = 문자열 T를 만드는 수 찾는 것이를 해결하기 위해 **동적 계획법(DP)**을 사용합니다.문제 이해부분 수열 (Subsequence):문자열의 일부 문자들을 선택해 순서를 유지하면서 생성된 새로운 문자열.예: s="rabbbit", t="rabbit"부분 수열로 t를 생성하는 방법:첫 번째 r, 첫 번째 a, 첫 번째 b, 두 번째 b, 첫 번째 i, 첫 번째 t....총 3가지 방법.목표:s에서 t를 생성하는 모든 부분 수열의 개수를 반환.시간 및 공간 복잡도시간 복잡도:O(m×n): DP 테이블 크기..