본문 바로가기

가젤의 컴퓨터과학

 (96)
도박꾼의 파산 (Gambler's Ruin) 일확천금을 노리는 한 도박꾼이 있다고 하죠. 이 도박꾼이 참여한 게임은 아주 간단합니다. 매 판마다 이기면 십만 원을 얻고 지면 십만 원을 잃습니다. 이 도박꾼이 오백만 원의 자본금으로 시작해서 천만 원을 더 벌고 싶다고 합시다. 과연 이 도박꾼이 목표를 이룰 확률은 어떻게 될까요? 반대로 이 도박꾼이 파산하게 될 확률은 또 어떻게 될까요? 이는 도박꾼의 파산(gambler's ruin)이라는 이름으로 많이 연구된 문제입니다. 위 상황을 좀더 일반화하면 다음과 같습니다. 도박꾼이 참여하는 게임에서 매 판마다 도박꾼은 \(p\)의 확률로 이기며, \(1 - p\)의 확률로 집니다. 단위를 간소화하기 위해 도박꾼이 이기면 1원을 얻고, 지면 1원을 잃는다고 합시다. 도박꾼은 처음에 \(L\)원의 자본금을 갖..
세제곱 시간 헝가리안 알고리즘 (Hungarian Algorithm in Cubic Time) 할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업이 주어지고, 각 노동자-작업 쌍마다 노동자를 작업에 할당할 때의 비용이 주어질 때, 최소의 비용으로 각 노동자를 작업에 하나씩 할당하는 방법을 찾는 문제입니다. 제 블로그에는 할당 문제와 이를 해결하는 알고리즘인 헝가리안 알고리즘(Hungarian algorithm)에 대해 정리한 글이 있습니다. 제 블로그에서 가장 인기가 있는 글이죠. 2019.08.07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm..
다익스트라의 알고리즘 (Dijkstra's Algorithm) 최단 경로 문제(shortest path problem)는 가장 유명한 조합론적 최적화 문제 중 하나로, 이름에서 유추할 수 있듯이 다양한 분야에서 널리 활용되는 문제입니다. 지난 포스트에서는 이 문제를 정확히 정의하고 최단 경로가 갖는 구조적인 특징을 이해하였으며, 마지막으로 \( O(|V||E|) \) 시간에 이를 해결하는 벨만-포드 알고리즘(Bellman-Ford algorithm)에 대해서도 공부했습니다. 2021.08.22 - [조합론적 최적화/Shortest path] - 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman-Ford Algorithm) 최단 경로 문제 & 벨만-포드 알고리즘 (Shortest Path Problem & Bellman..
알고리즘 덕후의 「투 더 문」 퍼즐 푸는 방법 저는 게임을 좋아합니다. 특히 좋아하는 장르는 롤플레잉 게임이나 퍼즐 게임인데요. 롤플레잉 게임을 할 때는 주로 그 속에 담긴 이야기를 따라가는 것을 즐기고 퍼즐 게임을 할 때는 복잡한 문제를 시간을 들여 해결할 때 큰 희열을 느낍니다. 만약 롤플레잉 게임에 흥미로운 퍼즐 요소가 섞여 있거나 퍼즐 게임에 감동적인 이야기가 더해져 있다면 말하지 않아도 제 취향일 것입니다. 글을 쓰는 현재로부터 약 두세 달 전 제 취향의 게임을 하나 플레이했습니다. 바로 「투 더 문(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)가 무엇인지에 대해서 살펴보았으며, 최종적으로는 매번 현재 흐름으로 정의되는 잔여 네트워크 위에서 시점에서 종점으로 향하는 임의의 증가 경로를 찾아 현재 흐름을 증가시켜 주면 (모든 간선의 용량이 유리수일 때) 언젠간 최대 흐름을 찾..

티스토리툴바