본문 바로가기

Data Structure & Algorithm36

2-SAT References Algorithms (Sanjoy Dasgupta) Contents Backtracking 2-SAT를 그래프 문제로 변환 백준 11277번, 11278번, 11280번, 11281번 이번 포스팅에서는 아래의 포스팅에서 언급했었던 2-SAT 문제에 대해서 살펴볼 예정입니다. NP-Complete Problems (1) NP-Complete Problems (2) 포스팅에서 2-SAT를 그래프로 변환한 다음 SCC를 찾음으로써 다항 시간에 해결할 수 있다고 했습니다. 하지만, 그 전에 먼저 백트래킹 기법을 이용하여 SAT 문제를 푸는 방법에 대해서 살펴보겠습니다. Backtracking 백트래킹은 해의 일부분만을 보고 이 해가 답이 될 수 없다는 것을 판단할 수 있는 경우가 많다는 관찰.. 2022. 4. 28.
NP-Complete Problems (2) Reference Algorithms (Sanjoy Dasgupta) Contents The reductions (치환) NP-Complete Problems (1) 이전 포스팅에 이어서 계속 진행해보도록 하겠습니다. 열심히 공부해봤으나... ㅠ 부족한 머리로 아직 완전히 이해를 하진 못해서 설명에 부족한 부분이 많습니다. 이점 유의하시고... 혹시 덧붙이고 싶은 내용이나 정정해야할 부분이 있다면 언제든지 댓글로 남겨주세요 ! The Reductions 이전 포스팅에서 다루었던 문제들이 위의 그림처럼 서로 치환될 수 있음을 살펴볼 예정입니다. 결과적으로 이들은 모두 NP-Complete 입니다. 위 그림에서의 치환들을 살펴보기 전에 먼저 두 가지 버전의 루드라타 문제들을 서로 연관지어 보도록 하겠습니다... 2022. 4. 25.
NP-Complete Problems (1) References Algorithms (Sanjoy Dasgupta) Contents Search Problems NP-Complete Problems Search Problems 현재 참고 중인 교재(Algorithms)에서 그래프에서의 최단 경로, 최소 신장 트리, 이분 매칭, 최장 증가 부분 수열, 네트워크 플로우 등의 알고리즘에 대해 살펴봤었습니다. 이러한 알고리즘들은 실행 시간이 입력 데이터 크기에 대한 다항식(ex, \(n, n^2, n^3\))이었으며, 따라서 효율적인 알고리즘이라 할 수 있습니다. 이와 같은 알고리즘을 좀 더 이해하기 위해 알고리즘이 해결하려는 문제를 다른 방법으로 접근해보겠습니다. 이 문제들에서 가능한 솔루션(path, tree, matching)의 수는 모두 지수승으로.. 2022. 4. 23.
강한 연결 요소 (Strongly Connected Component) References Algorithm (Sanjoy Dasgupta) Contents SCC (Strongly Connected Component) 백준 2150 : Strongly Connected Component 코사라주 알고리즘 (Kosaraju Algorithm) Connectivity for directed graphs 무향 그래프(undirected graph)에서 연결성(connectivity)는 꽤 명확합니다. 연결이 안된 그래프는 자연스럽게 여러 연결된 요소들로 분리될 수 있습니다. 무향 그래프는 만일 정점들의 임의의 쌍 사이에 경로가 있다면 연결되었다고 할 수 있습니다. 위 이미지에서 (a) 그래프는 전부 연결되지는 않았습니다. 따라서 아래의 세 집합에 대응되는 3가지의 다른 연결된 .. 2022. 4. 22.
이분 매칭 (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.
​

티스토리툴바