hyunkookim 님의 블로그

해밀턴 순회 문제(모든 정점을 한 번씩 방문하고 다시 시작 정점으로 돌아올 수 있는지를 판단, 가중치 고려하지 않음) 해밀턴 경로 문제(해밀턴 순회와 비슷하지만 시작정점으로 돌아올 필요는 없는 경로) 알고리즘 팁DFS + 백트래킹: 해밀턴 순회와 경로 문제의 기본. 재귀적으로 경로를 탐색하며 경로가 유효한지 확인.DP + 비트마스크: 모든 정점을 방문하는 경로 문제를 효율적으로 해결하는 방법. 특히 가중치가 있는 그래프에서 유용.위상 정렬: DAG에서 해밀턴 경로를 찾는 데 강력한 도구. 해밀턴 순회 문제 (Hamiltonian Cycle)목표: 그래프에서 모든 정점을 한 번씩 방문하고 시작 정점으로 돌아올 수 있는지를 판단합니다.Find Hamiltonian Cycle (Custom Problem - ..

모든 정점을 방문하고 시작점으로 다시 돌아오는 모든 경로를 찾는 문제All Paths From Source to Target (LeetCode 797)설명: 방향 그래프에서 시작점부터 끝점까지 모든 가능한 경로를 찾습니다.핵심 개념: DFS, 백트래킹.Find All Possible Paths (Custom Problem - 구현 필요)설명: 모든 정점을 방문하는 모든 경로를 출력합니다.핵심 개념: DFS, 백트래킹.Word Search (LeetCode 79)설명: 2D 그리드에서 주어진 단어를 찾는 경로를 출력합니다.핵심 개념: DFS, 백트래킹. 모든 정점을 방문하고 시작점으로 다시 돌아오는 모든 경로를 찾아서 모든 경로의 가중치 합을 구하는 문제Cheapest Flights Within K Sto..

타잔 알고리즘 (Tarjan's Algorithm)개념타잔 알고리즘은 그래프에서 **강하게 연결된 컴포넌트(SCC, Strongly Connected Components)**를 찾는 알고리즘입니다.DFS 기반으로 동작하며, 각 노드의 발견 순서(low-link value)를 이용합니다.방향 그래프에서 SCC를 탐색하는 데 유용합니다.문제Critical Connections in a Network (LeetCode 1192)설명: 네트워크에서 단일 연결을 끊으면 그래프가 분리되는 간선을 찾습니다.핵심 개념: Tarjan's Algorithm, DFS.Strongly Connected Components (Custom Problem - 구현 필요)설명: 방향 그래프에서 모든 SCC를 탐지합니다.핵심 개념: ..

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

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

Problem 1: Minimum Spanning Tree설명: 주어진 그래프에서 최소 신장 트리를 찾습니다.핵심 개념: 그래프, 최소 신장 트리, 크루스칼 알고리즘, 유니온 파인드.링크: LeetCode 1000Problem 2: Minimum Cost to Hire K Workers설명: K명의 노동자를 고용하는 최소 비용을 계산합니다.핵심 개념: 그리디 알고리즘, 우선순위 큐.링크: LeetCode 857Problem 3: Minimum Cost to Merge Stones설명: 주어진 돌들을 하나로 합치는 최소 비용을 계산합니다.핵심 개념: 동적 계획법, 누적 합.링크: LeetCode 1000Problem 4: Minimum Cost to Make at Least One Valid Path in..

Problem 1: Minimum Cost to Connect Sticks설명: 주어진 막대들을 모두 연결하는 데 필요한 최소 비용을 계산합니다.핵심 개념: 그리디 알고리즘, 우선순위 큐.링크: LeetCode 1167Problem 2: Path With Minimum Effort설명: 2D 그리드에서 시작점부터 도착점까지 이동할 때, 경로의 최대 고도 차이가 최소가 되는 경로를 찾습니다.핵심 개념: 그래프, 최소 신장 트리, 다익스트라 알고리즘.링크: LeetCode 1631Problem 3: Connecting Cities With Minimum Cost설명: 도시들을 연결하는 도로의 비용이 주어질 때, 모든 도시를 연결하는 최소 비용을 계산합니다.핵심 개념: 최소 신장 트리, 크루스칼 알고리즘, 유..