본문 바로가기

분류 전체보기465

이분 매칭 (Bipartite Matching) Contents 이분 매칭 (Bipartite Matching) 백준 2188 : 축사 배정 선형 계획법과 치환 (2) - Network Flow, Bipartite Matching 위 포스팅에서 네트워크 유량과 이분 매칭에 대해서 알아봤었는데, 이번 포스팅에서는 이분 매칭을 어떻게 구현하느냐에 초첨을 맞추어 보려고 합니다. 지난 포스팅에서 이분 매칭은 최대 유량(maximum flow) 문제로 치환되어 선형 계획법을 사용할 수 있다고 했었는데, 즉, 최대 유량 문제를 풀듯이 풀 수 있다는 것 입니다. 위에서 소년들과 소녀들을 매칭하는 문제에서, 위의 그래프처럼 모든 소년들을 향해 나가는 간선들을 갖는 새로운 source 노드와 모든 소녀들로부터 들어가는 간선들을 갖는 새로운 sink 노드 t를 만들고,.. 2022. 4. 21.
포드 풀커슨 / 에드몬드 카프 알고리즘 Contents 포드 풀커슨(Ford-Fulkerson) 알고리즘 에드몬드 카프(Edmonds-Karp) 알고리즘 선형 계획법과 치환 (2) - Network Flow, Bipartite Matching 위의 포스팅에서 네트워크 유량(network flow)에 관련한 내용들에 대해 다루었습니다. 여기서는 선형계획법과 심플렉스 방법에 대해 초점을 맞추어서 이야기를 했었는데, 이번 포스팅에서는 네트워크 유량 문제를 해결하는 알고리즘들에 대해 초점을 맞추어서 이야기해보고자 합니다. 알아볼 알고리즘은 포드 풀커슨 알고리즘과 애드몬드 카프 알고리즘입니다. 우선 위의 포스팅에서 사용했던 네트워크 유량을 나타내는 그래프를 가져오겠습니다. 그래프 (a)가 바로 네트워크를 나타내는 그래프입니다. 이 그래프의 간선에는 길.. 2022. 4. 20.
선형 계획법과 치환 (3) - 쌍대성, 심플렉스법 References Algorithm (Sanjoy Dasgupta) Contents Duality Zero-sum game Simplex Algorithm 선형 계획법과 치환 (1) - Examples of LP 선형 계획법과 치환 (2) - Network Flow, Bipartite Matching 지난 포스팅들에 이어서 계속해서 진행해보도록 하겠습니다. Duality 네트워크에서 flows는 cuts보다 작습니다. 그러나 maximum flow와 minimum cut이 정확히 일치하는 것을 지난 포스팅에서 살펴봤습니다. 따라서 각각은 서로의 최적성의 검증이 됩니다. maximum flow을 선형계획법에 의해 해결될 수 있는 어떤 문제로 일반화하는 현상을 주목할 만합니다. 모든 linear maxim.. 2022. 4. 19.
선형 계획법과 치환 (2) - Network Flow, Bipartite Matching References Algorithm (Sanjoy Dasgupta) Contents Flows in networks Max-flow Min-cut Theorem Bipartite Matching (이분 매칭) 선형 계획법과 치환 (1) - Examples of LP 선형 계획법과 치환 (1) - Examples of LP References Algorithms (Sanjoy Dasgupta) Contents Introduction to Linear Programming Reduction (치환) Simplex Method 최단 경로나 최소 비용 신장 트리(cheapest spanning tree), 최장 증가 부분 수열(longe.. junstar92.tistory.com 지난 포스팅에 이어서 선형 계.. 2022. 4. 17.
선형 계획법과 치환 (1) - Examples of LP References Algorithms (Sanjoy Dasgupta) Contents Introduction to Linear Programming Reduction (치환) Simplex Method 최단 경로나 최소 비용 신장 트리(cheapest spanning tree), 최장 증가 부분 수열(longest increasing subsequence)와 같은 알고리즘들에 대한 많은 문제들은 최적화(optimization) 작업들입니다. 이와 같은 경우, (1) 특정 제약(예를 들어, 경로는 반드시 그래프의 간선을 사용해야 하고, s에서부터 t로 이동해야 하며 트리의 모든 노드를 지나야 한다)을 만족하고, (2) 잘 정의된 기준에 부합하면서 이들 제약들을 만족하는 모든 솔루션 가운데 가장 최적의 솔.. 2022. 4. 16.
[DP] 외판원 문제 (Traverling Salseman Problem) References Algorithms (Sanjoy Dasgupta) Contents TSP (Traverling Salseman Problem) The Traverling Salseman Problem 이번 포스팅에서 다루어 볼 내용은 컴퓨터 공학 분야에서 유명한 외판원 순회 문제(TSP)입니다. 많은 변종 문제들이 존재하지만, 가장 기본적인 문제를 살펴보도록 하겠습니다. 문제는 다음과 같습니다. 외판원은 대규포 판매 투어를 준비하고 있습니다. 가방을 들고 외판원의 고향부터 시작하여 다시 고향으로 돌아오기 전에 그가 목표로 하는 도시를 정확히 한 번만 방문하도록 여행합니다. 각 도시 간의 거리가 주어졌을 때, 전체 이동 거리를 최소화하기 위한 여행 계획을 세워야 합니다. 여기서 이동 거리는 비용이 되.. 2022. 4. 15.
[DP] Knapsack Problem (0-1 Knapsack) References Algorithms (Sanjoy Dasgupta) Contents Knapsack Problem (배낭 문제) with repetition without repetition Knapsack Problem 배낭 문제(knapsack problem)는 간단하게 다음과 같습니다. 한 여행가의 배낭에 담을 수 있는 무게의 최댓값(W)이 정해져 있습니다. 담을 수 있는 항목은 총 n개가 있는데, 이들의 무게는 \(w_1, \cdots, w_n\)이고, 그 항목의 가치는 \(v_1, \cdots, v_n\) 일 때, 가치의 합이 최대가 되도록 배낭에 담을 항목을 고르는 방법은 무엇일까요? 예를 들어, W = 10일 때를 생각해보도록 하겠습니다. 이 문제는 두 종류의 버전이 존재합니다. 만약 각.. 2022. 4. 14.
동적 프로그래밍 (Dynamic Programming) References Algorithms (Sanjoy Dasgupta) Contents DAG에서의 최단 경로 Longest Increasing Subsequence (LIS; 최장 증가 부분 수열) Edit Distance (편집 거리) DAG에서의 최단 경로 DAG(Directed Acyclic Graph), 즉, 유향 비순환 그래프에서의 최단 경로 알고리즘에는 다익스트라(Dijkstra) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘 등이 있습니다. 이 알고리즘을 통해서 최단 경로 문제는 쉽게 해결될 수 있다는 것을 알 수 있습니다. 이는 동적 프로그래밍의 핵심적인 부분이기 때문에, 동적 프로그래밍에 대해 시작하기 전에 한 번 요약해보도록 하겠습니다. 각 최단 경로 알고리즘에 대해서는 다른.. 2022. 4. 13.
집합 커버(Set Cover) 문제 References Algorithms (Sanjoy Dasgupta) Contents Set Cover (집합 커버) 문제 Approximation Factor 위 이미지에서 점들은 마을을 표현합니다. 여기서 학교를 어디에 배치할 것인가 결정하는데, 두 가지 제한 사항이 있습니다. 각 학교는 마을 내에 위치해야 하고, 학교는 어떤 마을에서도 30마일보다 가까운 곳에 위치해야 합니다. 이 경우 필요한 학교의 최소 갯수는 몇 개 일까요? 이 문제는 전형적인 집합 커버(set cover) 문제입니다. 각 마을 x에 대해, \(S_x\)는 30마일 이내에 있는 마을들의 집합이라고 합시다. x에 있는 학교는 기본적으로 이 집합의 다른 마을들을 커버(cover)합니다. 이때 문제는 '얼마나 많은 집합 \(S_x\.. 2022. 4. 12.
최소 신장 트리 (Minimum Spanning Tree) References Algorithms (Sanjoy Dasgupta) Contents Minimum Spanning Tree 크루스칼 알고리즘 (Kruskal's algorithm) Union-Find 자료구조 C++ 구현 그리디(Greedy) 알고리즘들은 가장 명백하게 당장의 이득을 제공하는 다음 조각을 항상 선택하면서 한 조각씩 해결책을 만들어 나갑니다. 이와 같은 접근 방법이 계산을 요구하는 작업에 많은 피해를 줄 수 있을지라도, 최적이 되는 해결책을 얻을 수도 있습니다. 그리디 알고리즘의 예로 이번 포스팅에서는 최소 신장 트리(Minimum Spanning Tree; MST)에 대해 알아보고자 합니다. 최소 신장 트리 컴퓨터들을 쌍으로 연결함(linking)으로써 네트워크를 구성한다고 가정해봅시.. 2022. 4. 11.
​

티스토리툴바