본문 바로가기

가젤의 컴퓨터과학

 (93)
「상자에 공 넣기, 상자를 두 개씩 고르면?」 증명 보충 예전에 상자에 공 넣기 문제(balls-into-bins problem)에서 매번 상자 두 개를 균일한 확률로 골라 공의 개수가 적은 쪽에 넣으면 어떻게 되는지 소개해 드린 적이 있습니다. 2020.03.22 - [알고리즘 & 확률/Balls into bins] - 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) 지난 포스트에서는 상자에 공 넣기 문제(balls into bins problem)를 공부했습니다. 2020/03/21 - [수학적 도구/Randomness] - 상자에 공 넣기 (Balls into Bins Problem) 상자에 공 넣기 (Balls into Bins Pro..
거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로 포스팅을 할 생각도 있었는지라 블로그에 글을 쓰는 것이 늦어졌습니다. 색다른 주제는 바로 양자 컴퓨팅(quantum computing)입니다. 하도 화제인지라 개인적으로도 공부해 보고 싶었습니다. 처음에는 전혀 이해가 되지 않았는데 이 책 저 책 찾아보면서 공부하다 보니 이제는 좀 이해가 되는군요. 언젠가 해당 주제로 포스팅을 해 보도록 하겠습니다. 각설하고, 이번 글의 주제를 고민하게된 배경에 대해서 간략히 설명을 드리겠습니다. 요새 온라인 메트릭 매칭 문제(online metric matching problem)를 (제가 찾아본 바로는) 기존에는 없던 새로운 모델에서 해결해 보는 연구를 진행하고 있습니다. 그런데 일반적인 메..
온라인 메트릭 이분 매칭 (Online Metric Bipartite Matching) 지난 포스트에서는 온라인 가중치 이분 매칭(online weighted bipartite matching)에 대해서 알아 보았습니다. 이 문제에서는 택시에 대한 정보는 미리 알고 있으며, 승객의 정보는 시간이 흐르면서 한 명씩 들어옵니다. 매 순간 어떤 승객의 정보가 알려질 때마다 우리는 이 승객을 택시에 할당할지 말지를 결정해야 하며, 만약 할당한다면 어느 택시에 태울지도 결정해야 합니다. 지난 포스트에서는 언젠가 승객을 어떤 택시에 할당했을 때 이를 더이상 번복할 수 없다면 좋은 경쟁비(competitive ratio)를 얻을 수 없다는 것을 확인하였습니다. 자세한 사항은 이전 포스트를 참고하시기 바랍니다. 2021.02.14 - [온라인 알고리즘/Online matching] - 온라인 가중치 이분..
비크리-클라크-그로브스 메커니즘 (Vickrey-Clarke-Groves Mechanism) 여러분이 한 사회의 정책 결정권자라고 해 봅시다. 여러분이 정책 후보들을 사회 구성원들에게 소개하면, 각 구성원은 이를 듣고 어느 후보를 선호할지 마음 속으로 결정합니다. 그러고는 여러분에게 알려 주죠. 여러분은 구성원들에게서 전달 받은 선호표를 통해 가장 '합리적'인 정책을 결정해야 합니다. 문제는 구성원들은 너무도 '이기적'이어서 여러분에게 거짓말을 할 수도 있다는 것입니다. 예컨대 이런 상황을 가정해 봅시다. 어떤 구성원이 정책 A는 무지막지하게 싫어하고 반대로 정책 B는 엄청 좋아합니다. 그런데 아무리 생각해도 정직하게 알려 줘서는 정책 A가 선택될 것 같다고 느낍니다. 따라서 차라리 차선으로 좋아하는 정책 C를 제일 좋아한다고 거짓으로 알려 줍니다. 만일 구성원 몇몇이 위와 같이 느끼고 행동했다..
애로우의 불가능성 정리 (Arrow's Impossibility Theorem) 우리는 거대한 사회를 이루며 살아 갑니다. 그 속에는 다양한 군상들이 존재하죠. 모든 사회 구성원들의 성격이나 가치관이 같을리 만무하므로 사회는 여러 요인에 의해 갈등이 발생할 수밖에 없습니다. 왕정이나 독재 하에서는 결국 절대 권력을 가진 사람이나 집단이 모든 의사 결정을 담당할 것이므로 (바람직하지는 않지만) 갈등을 효율적으로 해소할 수 있습니다. 하지만 우리나라를 포함한 많은 국가들이 채택하고 있는 민주주의 체제에서는 갈등을 합리적으로 해소하여 사회적 합일을 이루는 방안을 마련해야 합니다. 과연 어떻게 하면 될까요? 안타깝게도 합리적인 조건을 모두 만족하면서 사회적인 합치를 이루는 방법은 존재하지 않습니다. 이는 저명한 경제학자인 케네스 애로우(Kenneth Arrow)에 의해 증명이 되었는데요. ..
경제학으로 해석한 헝가리안 알고리즘 할당 문제(assignment problem)는 \(n\) 명의 노동자와 \(n\) 개의 작업 그리고 각 노동자를 각 작업에 할당했을 때 발생하는 비용이 모두 주어졌을 때, 각 노동자를 하나의 작업에 중복 없이 모두 최소의 비용으로 할당하는 방법을 찾는 문제이며, 헝가리안 알고리즘(Hungairan algorithm)은 이 문제를 해결하는 가장 유명한 방법입니다. 할당 문제와 헝가리안 알고리즘은 조합론적 최적화(combinatorial optimization) 분야의 근간을 이루는 개념 중 하나일 뿐 아니라 산업 공학(industrial engineering), 운용 과학(operations research) 등 여러 실용적인 분야에서도 널리 활용됩니다. 이렇게 다양한 분야에서 활약하는 할당 문제와 헝가..
비크리 경매 (Vickrey Auction) 희대의 역작이 경매로 올라왔고, 여러 입찰자들이 이 작품을 구매하기 위해 모여들었습니다. 작가는 자신의 가치를 실제로 가장 높게 쳐주는 사람에게 자신의 작품을 넘기기를 바라고 있습니다. 우리는 경매사로서 작가의 바람에 부응해야 합니다. 이를 위해서 우리는 모든 입찰자로부터 각자가 생각하는 작품의 가치를 종이에 적어서 제출해 달라고 부탁하였습니다. 가치가 기록된 종이는 입찰자들에게 공유되지 않고 오로지 신뢰 받는 경매사인 우리만 알게 됩니다. 하지만 입찰자들은 너무도 "이기적"이어서 만약 가치를 속여서 적는게 자신에게 이득이 된다면 기꺼이 그럴 것입니다. 이러한 무한 경쟁의 상황에서 과연 어느 입찰자에게 얼마의 금액으로 작품을 판매해야 실제로 가장 높은 가치를 쳐주는 입찰자에게 작품이 돌아가게 할 수 있을..
도박꾼의 파산 (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..

티스토리툴바