본문 바로가기

조합론적 최적화

 (22)
보루프카 알고리즘 (Borůvka's Algorithm) 최소 신장 트리(minimum spanning tree, MST)는 최소의 비용으로 주어진 그래프의 모든 정점을 연결하는 방법으로, 학부 자료구조 수업이나 알고리즘 수업에서 이를 찾는 문제를 분명 배우셨을 겁니다. 예전에 저도 자료구조 시간에 이 문제를 배웠던 기억이 있습니다. 당시 이 문제를 푸는 방법으로 크루스칼 알고리즘(Kruskal's algorithm)과 프림 알고리즘(Prim's algorithm)을 배웠습니다. 아마 이 두 알고리즘이 가장 유명한 방법이 아닐까 싶습니다. 그런데 최근 두 알고리즘과는 또 다른 알고리즘을 알게 되었습니다. 바로, 보루프카 알고리즘(Borůvka's algorithm)인데요. 사실은 이 알고리즘이 맨 처음으로 제시된 MST 알고리즘이라고 하더군요. 찾아보니 우리말..
텃의 정리 (Tutte's Theorem) 드넓은 황야에 위치한 초원 대학교의 컴퓨터과학과 소속 폰가젤 교수는 2인 조별 과제를 내는 것을 좋아합니다. 혼자서 해결하기에는 벅찬 문제를 두 명이서 협력하여 해결한다면 학생들에게 협동심은 물론 위기에 굴복하지 않는 능력을 기를 수 있다고 굳게 믿기 때문이죠. 물론 '조별과제 잔혹사'라는 말을 언젠간 들어 봤을 정도로 학생들의 원성이 자자하다는 사실도 잘 알고 있습니다. 그가 개설했던 알고리즘 수업의 강의 평가를 보면 쉽게 유추할 수 있었죠. 그동안은 학생들이 자율적으로 조를 편성하도록 놔두었는데, 이러니 어떤 학생들은 전혀 마음이 맞지 않는 사람과 조를 이루어야 하는 불상사가 발생했었죠. 이 부분이 바로 학생들이 가장 불편을 느낀 부분이었습니다. 이번 학기에 가젤 교수는 이러한 학생들의 원성을 잠재우..
포드-풀커슨 방법 (Ford-Fulkerson Method) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때, 시점에서 종점으로 흐르는 최대 흐름을 찾는 문제입니다. 지난 두 포스트를 통해 우리는 이 문제에서 최대 흐름이 다음과 같은 흥미로운 특징을 갖는다는 것을 알게 되었습니다. 정리 1. 최대 흐름의 잔여 네트워크의 특징 최대 흐름의 잔여 네트워크(residual network)에서는 시점에서 종점으로 도달할 수 없다. 정리 2. 잔여 네트워크의 종점 비도달성의 특징 어떤 흐름의 잔여 네트워크에서 종점이 시점으로부터 도달 불가능할 때, 그것의 흐름양과 동일한 값의 용량을 갖는 절단(cut)을 찾을 수 있다. 그러므로, 이 흐름은 최대 흐름이다. 정리 1의 증명이 궁금하면 아래 글을 참조하세요...
최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem) 저번 글에서는 최대 흐름 문제(maximum flow problem)가 무엇인지 알아 보고 최대 흐름이 만족하는 성질들도 함께 확인해 보았습니다. 최대 흐름 문제가 무엇인지 잘 모르신다면 이전 포스트를 참조하시기 바랍니다. 2020/08/29 - [기초 강좌/Algorithm analysis] - 최대 흐름 문제 이해하기 (Maximum Flow Problem) 최대 흐름 문제 이해하기 (Maximum Flow Problem) 여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결 gazelle-and-cs.tistory.com 결론부터 말씀드리면 최대 흐름의 잔여 네트워크(r..
최대 흐름 문제 이해하기 (Maximum Flow Problem) 여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결된 수도관을 따라 흘려주는 것입니다. 해당 지역에는 사람도 많고 공단도 있어서 최대한 많은 물을 공급받고 싶어합니다. 만약 두 지점 사이를 잇는 수도관이 딱 하나 있다면 쉽게 해결되겠지만, 문제는 이보다 더 복잡합니다. 바로 수도관이 여러 사정에 의해 매우 얼기설기 설치되어 있기 때문입니다. 게다가 수도관마다 연식이나 제원도 달라서 수도관마다 견딜 수 있는 수압이나 용량도 정해져 있습니다. 과연 물을 어떻게 흘려야 수도관에 무리를 주지 않고 해당 지역으로 최대한 많은 물을 보내줄 수 있을까요? 이 문제는 유명한 최적화 문제인..
최소 경로 덮개 (Minimum Path Cover) 얼마 전 친한 형님이 또 재미있는 문제를 하나 소개해주었습니다. 처음에 전 그 문제가 NP-난해일 것이라고 생각했지만, 토의를 거친 끝에 그 문제가 순환이 없는 방향 그래프(directed acyclic graph, DAG)에서 최소 경로 덮개(minimum path cover)를 찾는 문제로 환원될 수 있다는 것을 찾아냈습니다. 또한 놀랍게도, 일반적인 그래프에서 최소 경로 덮개를 찾는 문제는 NP-난해하지만, DAG에서는 다항 시간에 찾을 수 있다는 것도 알게 되었습니다. Bipartite matching을 활용하면 된다는데, 곰곰이 생각해 보니 쉽게 보일 수 있더군요. 이번 포스트에서는 이에 대해서 간단히 알아보도록 하겠습니다. 문제를 엄밀히 정의하도록 하겠습니다. 입력으로는 방향이 있는 그래프(d..
중국인 우체부 문제 (Chinese Postman Problem) 어느 작은 마을의 우체부의 고민을 한번 들어봅시다. 이 마을은 하도 작아서 마을의 우체부는 이 사람 혼자입니다. 이 우체부의 하루 일과는 아침에 모든 우체통에 들어있는 편지나 소포를 우체국으로 가지고 오는 것으로 시작합니다. 잘 아시다시피 우체통은 길가에 듬성듬성 설치되어 있죠. 다시 말해, 마을의 모든 길을 최소한 한 번은 지나간다면 모든 우체통을 방문할 수 있게 됩니다. 이 우체부는 아침 일과를 빨리 끝내고 돌아와 아침 햇살을 쬐며 한 잔의 커피를 즐기는 낭만(?)적인 사람입니다. 그래서 어떻게 하면 가장 짧은 경로로 마을의 모든 길목을 지나칠 수 있을지 고민하고 있습니다. 과연 모든 길목을 최소 한 번씩은 지나는 가장 짧은 경로는 어떻게 구할 수 있을까요? 이 우체부가 고민하는 문제가 바로 중국인 ..
헝가리안 알고리즘 시간 복잡도 분석 지난번에 할당 문제와 헝가리안 알고리즘을 주제로 글을 작성하였습니다. 아래 링크를 참조하세요. 2019/08/07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾아.. gazelle-and-cs.tistory.com 저기서는 할당 문제가 무엇인지 알아보고..
호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm) 엄청 오랜만에 포스팅을 합니다. 방학이 되면 시간이 나서 글을 좀 쓸 수 있을 줄 알았는데, 대학원생은 방학도 바쁘군요. 다행히 어느정도 일단락이 나서 이렇게 글을 쓸 수 있게 되었습니다. 개강 전에 한 두 개는 더 적을 수 있지 않을까 생각합니다. 반년에 글 하나씩 올리는 주제에 블로그를 운영한다고 말할 수 있으련지는 모르겠지만, 아무튼 블로그를 운영하면서 이제 슬슬 외부에도 노출이 되어가는 것을 보니 감회가 새롭습니다. 특히 제 블로그에서 가장 조회수가 높은 글은 헝가리안 알고리즘에 관한 글이었습니다. 2019/08/07 - [조합론적 최적화/Bipartite matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 ..
할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾아보니 Hungarian algorithm 자체가 어떻게 동작하는지에 대해서는 우리말로 된 포스팅이 많이 있는 반면에 이 알고리즘이 왜 정확히 돌아가는지에 대해서 분석한 글은 보지 못하였습니다. 제 블로그는 이 간격을 열심히 줄이는 데 초점이 맞추어져 있습니다. 그러니 이번에도 왜 이 알고리즘이 올바른 결과를 출력하는지 함께 알아보도록 하죠. 문제 정의 문제를 정의하기 전에 제 하소연부터 좀 하겠습니다. 이 글을 작성하는 현재 제 자취방 에어컨이 고장 난 상태입니다..

티스토리툴바