본문 바로가기

가젤의 컴퓨터과학

 (93)
알고리즘 덕후의 「투 더 문」 퍼즐 푸는 방법 저는 게임을 좋아합니다. 특히 좋아하는 장르는 롤플레잉 게임이나 퍼즐 게임인데요. 롤플레잉 게임을 할 때는 주로 그 속에 담긴 이야기를 따라가는 것을 즐기고 퍼즐 게임을 할 때는 복잡한 문제를 시간을 들여 해결할 때 큰 희열을 느낍니다. 만약 롤플레잉 게임에 흥미로운 퍼즐 요소가 섞여 있거나 퍼즐 게임에 감동적인 이야기가 더해져 있다면 말하지 않아도 제 취향일 것입니다. 글을 쓰는 현재로부터 약 두세 달 전 제 취향의 게임을 하나 플레이했습니다. 바로 「투 더 문(To the Moon)」입니다. 사실 이 게임을 처음 구매할 때는 이 게임에 퍼즐 요소가 들어있을 줄 몰랐습니다. 스팀에서 게임을 구매하는 분들이라면 많이 공감하실텐데, 저는 스팀에서 할인 행사를 진행할 때 게임을 좀 쟁여 놓는 편입니다. 이 ..
파이썬 PuLP 입문 제가 주로 하는 연구가 조합론적 최적화 쪽이다 보니 아무래도 선형 계획법(linear programming, LP)을 풀어야 할 때가 적잖이 있습니다. 그럴 때마다 예전에는 CPLEX나 Gurobi와 같은 프로그램을 C++로 불러서 해결을 했었습니다. 그렇지만 이를 사용하려면 여러 설정을 만져 줘야하는 번거로움이 있었습니다. 또, C++ 자체가 아무래도 오래된 언어다 보니 문자열 처리 등 개인적으로 불편한 부분도 많았죠.(이를 연구실 동료가 들으면 기겁하겠지만요. 하하.) 마지막으로 CPLEX나 Gurobi 모두, 비록 학술용 라이센스를 제공하기는 하지만, 상용 소프트웨어라는 점도 마음에 걸렸습니다. 그러던 와중에 파이썬에서 LP를 해결해 주는 오픈 소스 라이브러리가 있다는 것을 최근 알게 되었습니다. ..
최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm) 자동차를 타고 서울에서 부산까지 여행을 떠난다고 생각해 봅시다. 일분일초라도 여행을 더 즐기기 위해서는 빨리 목적지에 도달하는 것이 좋겠죠. 그러려면 어떤 경로를 따라 자동차를 운전해야 할까요? 한 가지 방법으로는 서울에서 부산까지 가는 모든 경로를 따져 본 다음, 가장 빨리 도달할 수 있는 경로를 선택하는 것입니다. 하지만 이 방법은 한눈에 봐도 멍청하다는 것을 알 수 있습니다. 서울에서 부산까지 가는 경로는 엄청나게 많기 때문입니다. 여기서 곰곰이 생각해 보면, 우리는 모든 경로를 다 탐색할 필요가 없어 보입니다. 예를 들어, 서울에서 부산까지 가는데 굳이 둘러 둘러 광주를 경유할 필요는 없겠죠. 반대로 서울과 부산의 가운데 정도에 위치한 대전은 지나는 것이 좋을 것입니다. 과연 어떻게 하면 효율적으..
분할 상환 분석 (Amortized Analysis) 이번 포스트에서는 분할 상환 분석(amortized analysis)에 대해서 알아보도록 하겠습니다. 자료 구조나 알고리즘 수업을 들으셨다면 분명 한 번쯤은 들어 보신 개념일 것입니다. 개인적으로는 자료 구조 수업 시간에 처음 분할 상환 분석에 대해서 배웠었는데요, 당시에는 잘 이해하지 못했던 기억이 있습니다. 아마도 많은 분들이 도대체 분할 상환 분석이 무엇이고, 이것이 어째서 중요한지에 대해 당시의 저처럼 이해하지 못하실 것으로 생각하는데요. 이 포스트를 통해서 그 이유를 알아 가셨으면 하는 바람입니다. 서론: 어느 회사의 커피 이 예제는 제가 대학생일 때 자료 구조 수업에서 교수님께서 분할 상환 분석을 설명하기 위하여 소개한 것입니다. 솔직히 처음 들을 당시에는 제대로 이해하지 못했습니다만, 지금 ..
비서 문제 (Secretary Problem) 여러분이 다음 뽑기 게임에 참가했다고 가정해 봅시다. 안을 볼 수 없는 상자가 여러분 앞에 놓여 있습니다. 여러분은 상자 안에 총 \(n\) 개의 공이 들어 있다는 것과, 공에는 서로 다른 숫자가 적혀 있다는 것을 알고 있습니다. 이제 여러분은 상자에서 공을 하나씩 무작위로 뽑고 공의 숫자를 확인할 것입니다. 만약 숫자가 마음에 든다면 여러분은 이 공을 선택할 수 있고, 만약 마음에 들지 않는다면 이를 버리고 새 공을 뽑을 수 있습니다. 다만 한 번 버린 공은 다시 주울 수 없죠. 가장 큰 숫자가 적힌 공을 선택해야 뽑기 게임에서 이긴다고 할 때, 과연 여러분은 어떤 전략을 취해야 할까요? 이 문제는 1950-60년대 여러 수학자들과 통계학자들 사이에서 매우 깊이 연구되었던 비서 문제(secretary ..
디니츠의 알고리즘 (Dinitz' Algorithm) 지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다. 가장 최근에는 최대 흐름 문제를 다항 시간에 해결하는 에드몬즈-카프 알고리즘(Edmonds-Karp algorithm)을 소개해 드렸죠. 이번에는 에드몬즈-카프 알고리즘보다 더 빠른 시간에 최대 흐름 문제를 해결하는 방법 중 하나를 소개하고자 합니다. 바로 우리에게는 디닉의 알고리즘(Dinic's algorithm)으로 더 잘 알려진, 디니츠의 알고리즘(Dinitz' algorithm)입니다. 포탈에 검색해 봤더니 디니츠의 알고리즘을 어떻게 구현하는지 우리말로 설명한 게시글은 적잖이 볼 수 있었습니다. 다만 어째서 디니츠의 알고리즘이 에드몬즈-카프 알고리즘보다 효율적으로 동작하는지..
에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때 시점(source)에서 종점(sink)까지 최대로 많은 양의 흐름을 찾는 문제입니다. 이때 흐름은 각 간선에서 용량(capacity)을 넘을 수 없고, 시점과 종점을 제외한 나머지 정점에서는 들어오는 양과 나가는 양이 동일해야 하죠. 지난 포스트에서는 이 문제를 풀기 위하여 잔여 네트워크(residual network)와 증가 경로(augmenting path)가 무엇인지에 대해서 살펴보았으며, 최종적으로는 매번 현재 흐름으로 정의되는 잔여 네트워크 위에서 시점에서 종점으로 향하는 임의의 증가 경로를 찾아 현재 흐름을 증가시켜 주면 (모든 간선의 용량이 유리수일 때) 언젠간 최대 흐름을 찾..
온라인 가중치 이분 매칭 (Online Weighted Bipartite Matching) 저번 글에서는 온라인 이분 매칭 문제(online bipartite matching problem)가 무엇인지 설명하고 이를 경쟁적으로 해결하는 알고리즘에 대해서 알아 보았습니다. 문제를 간략히 다시 소개하도록 하겠습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 태운 적이 없는 택시 가운데 하나를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 매번 바로 결정해야 한다. 이 결정은 차후에 번복될 수 없다. 이때, 최대한 많은 승객을 태우시오. 위 예시에서 한 가지 현실과는 약간 동떨어진 점이 있다면 바로 건당 정액을 받는 수익 ..
보루프카 알고리즘 (Borůvka's Algorithm) 최소 신장 트리(minimum spanning tree, MST)는 최소의 비용으로 주어진 그래프의 모든 정점을 연결하는 방법으로, 학부 자료구조 수업이나 알고리즘 수업에서 이를 찾는 문제를 분명 배우셨을 겁니다. 예전에 저도 자료구조 시간에 이 문제를 배웠던 기억이 있습니다. 당시 이 문제를 푸는 방법으로 크루스칼 알고리즘(Kruskal's algorithm)과 프림 알고리즘(Prim's algorithm)을 배웠습니다. 아마 이 두 알고리즘이 가장 유명한 방법이 아닐까 싶습니다. 그런데 최근 두 알고리즘과는 또 다른 알고리즘을 알게 되었습니다. 바로, 보루프카 알고리즘(Borůvka's algorithm)인데요. 사실은 이 알고리즘이 맨 처음으로 제시된 MST 알고리즘이라고 하더군요. 찾아보니 우리말..
동적, 스트리밍, 온라인 알고리즘 비교 (Dynamic, Streaming, and Online Algorithm) 최근, 저널에 제출했던 논문에 대한 심사 결과를 받았습니다. 논문의 주제는 온라인 알고리즘인데 스트리밍 알고리즘에 대한 문헌 검토가 부족하니 이를 보충하라는 평가를 받았습니다. 논문을 쓸 때 참조했던 다른 논문들에서는 스트리밍 알고리즘에 대한 내용을 발견하지 못했었는데 이런 평가를 받아서 처음에는 적잖이 당황했습니다. 그런데 이 내용들을 공부해 보니 서로 비슷하면서도 다른 특징들이 있더군요. 우리말로 적힌 자료는 찾기 어려웠어서, 제 공부를 겸해 이번에 알게 된 내용들을 여기에 정리하고자 합니다. 아래 내용을 미리 요약을 하자면 다음과 같습니다. 동적 알고리즘(dynamic algorithm)은 입력에 무언가 추가되거나 삭제되는 등의 수정(update)이 발생하며 그때마다 바뀐 입력에 맞는 올바른 답을 ..

티스토리툴바