hyunkookim 님의 블로그

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