본문 바로가기

가젤의 컴퓨터과학

 (93)
안정 매칭 (Stable Matching) 오랜만에 글을 적습니다. 미국에서 인턴을 마치고 돌아온 후 그동안 좀 바빴습니다. 인턴을 하는 동안 연구한 결과를 잘 마무리하여 학회에 제출하기도 했고, 이론 컴퓨터 과학을 연구하거나 그것에 관심이 있는 학생들을 모아 교내 학생 모임을 발족하기도 하였습니다. 모쪼록 좋은 결과가 있기를 바라 봅니다. 그러는 와중에 최근 흥미로운 논문을 하나 읽었습니다. 지난 포스트에서 다루었던 다중 슬롯머신 문제(multi-armed bandits)에다가 안정 매칭(stable matching)을 결합한 문제였습니다. 다중 슬롯 머신이 무엇인지 궁금하시면 아래 포스트를 참고하시기 바랍니다. 다중 슬롯머신 문제 & 비적응 탐사 알고리즘 (Multi-Armed Bandits & Non-Adaptive Exploration A..
우월 전략 균형 & 내쉬 균형 (Dominant Strategy Equilibrium & Nash Equilibrium) 한 형사가 강도 사건을 조사하고 있습니다. 꼼꼼한 수사와 끈질긴 추적을 통해 그는 피의자를 두 명으로 좁히는데 성공하였습니다. 현재까지 얻은 증거로는 각각에게 일 년의 징역형을 줄 수 있는 수준입니다. 그렇지만 드러난 피해로 보건데 이는 두 피의자에게 각각 오 년의 징역형을 줄 수 있는 매우 중대한 범죄였습니다. 다만 아직 이 혐의를 완벽히 입증할 증거를 발견하지 못한 상태였습니다. 자백을 얻기 위해 형사는 피의자를 모두 불러 심문하였습니다. 때로는 무섭게 겁을 주기도 하고, 또 때로는 어르고 달래도 봤지만, 서로 말을 잘 맞추었는지 두 피의자 모두 모르쇠로 일관하였습니다. 이대로면 둘 다 일 년 형만 받고 끝날 것이었습니다. 별다른 진전 없이 시간만 흘러 형사의 속이 타들어 가던 중 그는 문득 묘안을 ..
다중 슬롯머신 문제 & 비적응 탐사 알고리즘 (Multi-Armed Bandits & Non-Adaptive Exploration Algorithms) 대단히 좋은 기회로 현재 미국에 연구 인턴을 오게 되었습니다. 이곳에서 여러 세미나를 듣고 다른 연구자들과 소통하면서 다양한 분야를 접하고 있는 중입니다. 그중에서도 특히 개인적으로 관심이 생긴 분야가 있는데, 바로 학습 이론(learning theory)입니다. 제가 들은 세미나 주제 중 상당수가 이 분야와 연관이 있었기 때문입니다. 원래도 잘 연구된 분야였겠지만, 최근 인공 지능과 기계 학습 분야의 괄목할 만한 성장이 큰 영향을 미치고 있다는 생각도 듭니다. 다중 슬롯머신 문제(multi-armed bandits problem)는 그중 가장 기본이 되는 문제입니다. 이 문제에 익숙하지 않으시면 영어 이름과 우리말 번역이 바로 대응되지 않아서 의아해하실 것 같습니다. 사실 제가 그랬습니다. 처음에 이 ..
설비 입지 선정 문제 (Facility Location Problem) 여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설해야 하겠죠. 여러 곳에서 자문을 얻어 물류 창고를 건설할 후보지를 받아 놓았다고 합시다. 이제 여러분은 큰 결단의 기로에 서게 됩니다. 바로 후보지 중 어느 곳에 물류 창고를 건설할지 결정해야 합니다. 고려해야 하는 요인은 크게 두 가지입니다. 하나는 각 후보지마다 물류 창고를 건설하게 될 때 발생할 비용일 것이고, 다른 하나는 물류 창고에서 각 고객에게 상품을 배송할 때 들어가는 비용입니다. 경영자의 입장에서 여러분은 당연히 총 비용이 최소가 되도록 하고 싶습니다. 과연 어느 후보지에 물류 창고를 건설하면 될까요? 실제 ..
예측이 있는 스키 대여 문제 (Ski Rental Problem with Predictions) 온라인 문제(online problem)의 대표격인 스키 대여 문제(ski rental problem)는 지난 수십 년간 깊이 그리고 널리 연구되어 온 매우 유서 깊은 문제입니다. 제 블로그에서도 비중 있게 다룬 적이 있는데요. 문제는 다음과 같이 정의됩니다. 우리는 스키장이 문을 닫을 때까지 스키를 타고 싶어 합니다. 스키를 타는 방법은 두 가지로, 하나는 1 원으로 스키를 하루 대여하는 것이고, 다른 하나는 \(B\) 원으로 스키를 구매하는 것입니다. 당연히 언젠가 스키를 대여하면 다음날에는 또 스키를 대여하든지 구매하든지 하여야 하며, 언젠가 스키를 구매하면 더 이상 그런 고민을 할 필요가 없어집니다. 이때 최소의 비용으로 스키장이 문을 닫을 때까지 스키를 타는 것이 문제의 목표입니다. 만약 스키장..
형독 카트라이더 디비디비딥 최적(?)의 위치 선정 넥슨이 서비스하는 「크레이지레이싱 카트라이더」는 제가 초등학생일 때부터 있었던 유구한 전통(?)의 온라인 게임입니다. 초등학생 때 부족한 실력이나마 이 게임을 열심히 즐긴 기억이 있습니다. 대학생 때 친구들과 술 한 잔 하고 PC방에서 함께 아이템전을 돌리던 추억도 새록새록 떠오릅니다. 요즘은 직접 플레이하지는 않지만, 유튜브에서 카트라이더 영상이 종종 추천되면 즐겨 시청하는 편입니다. 그 중에서도 형독방송 채널의 영상을 많이 시청하는데요. 저번 주에는 '디비디비딥'이라는 이름의 게임을 빠른 시간에 끝내는 미션을 수행하는 영상이 올라왔습니다. 형독방송 「🔥머리만 서로 다르게 돌리면 된다는 고액 미션🔥 와 진짜 레전드 영상 나왔습니다ㅋㅋㅋㅋㅋㅋㅋㅋ」 2022. 영상에서 형독이 즐긴 '디비디비딥'은 다음과 ..
이분 매칭에 관한 몇 가지 반례들 매칭(matching), 특히 이분 매칭(bipartite matching)은 제 주된 연구 분야 중 하나입니다. 제 블로그에 매칭 관련된 포스트가 가장 많은 것을 보면 쉽게 유추할 수 있으시리라 생각합니다. 최근 개인적으로 이분 매칭과 관련하여 몇 가지 명제를 세워 증명해 보려고 했습니다. 만약 참으로 밝혀진다면 제가 요즘 하는 연구에 도움이 될 명제들이었습니다. 하지만 안타깝게도 모두 반례가 존재하였습니다. 어디 가서 써 먹을 곳도 없다 보니 약간은 울적한 마음에 블로그에라도 적어 보려고 합니다. 혹여 비슷한 주제를 고민하시는 분들이 계시다면 이 글이 약간의 도움이 되었으면 합니다. 차수와 간선 서로소인 최대 매칭의 개수 첫 번째 명제는 다음과 같았습니다. 어떤 이분 그래프의 최소 차수(degree)..
절단 성질을 이용한 MST 알고리즘 증명 (Proving MST Algorithms by Cut Property) 이 포스트에서 다룰 최소 신장 트리(minimum spanning tree, MST) 문제는 매우 유명한 조합론적 최적화 문제입니다. 아마 이 글을 읽으러 들어오셨다면 아무래도 학부 자료 구조나 알고리즘 수업 시간에 이 문제가 어떤 문제인지에 대해서 들어 보셨을 것입니다. 굳이 다시 정의를 해 보자면, 이 문제는 간선마다 비용이 정의된 그래프 위에서 최소의 비용으로 모든 정점을 연결하는 트리를 찾는 문제입니다. 수업 시간에 이 문제를 다루면서 분명 이 문제를 해결하는 알고리즘에 대해서도 함께 배우셨을 것입니다. 적어도 다음 두 알고리즘은 배웠을 텐데, 바로 크루스칼의 알고리즘(Kruskal's algorithm)과 프림의 알고리즘(Prim's algorithm)입니다. 두 알고리즘 모두 한두 문장으로 설..
하벨-하키미 알고리즘 (Havel-Hakimi Algorithm) 티스토리 블로그 관리 페이지에는 유입 키워드를 확인할 수 있는 기능이 있습니다. 저는 하루에 몇 번씩 유입 키워드를 살펴보면서 어떤 검색어로 제 블로그에 유입되는지를 확인하고는 합니다. 그러다 최근 'hakimi 방식', 'hakimi의 방법' 등의 키워드로 제 블로그에 방문한 사람이 있다는 사실을 알게 되었습니다. 최근에 제가 작성한 거리의 그래프 실현 가능성에 대한 포스트로 유입된 것이었습니다. 2022.05.15 - [수학적 도구/Graph theory] - 거리의 트리 실현 가능성 (Tree Realizability of Distance) 거리의 트리 실현 가능성 (Tree Realizability of Distance) 오랜만에 포스팅을 합니다. 그동안 연구에 집중하기도 했고, 좀 색다른 주제로..
피셔-예이츠 셔플 (Fisher-Yates Shuffle) 우리는 종종 무언가를 잘 뒤섞을 필요가 있습니다. 예를 들어, 친구들과 여행을 가서 저녁을 맛있게 먹은 다음 설거지 당번을 뽑는 경우를 생각해 봅시다. 다양한 방법이 있겠지만, 가장 고전적인 방법 중 하나는 종이 조각을 사람 수만큼 준비하고 한 곳에 '꽝'을 적은 후 이를 잘 뒤섞고 한 명씩 종이 조각을 뽑는 것입니다. 이때 우리는 이 조각들이 잘 뒤섞여 있기를 바랍니다. 다른 예시로는 포커 게임을 들 수 있겠습니다. 딜러는 게임을 시작하기 전에 카드를 뒤섞습니다. 이때 게임 참가자들은 카드가 잘 뒤섞여 있기를 희망할 터입니다. 그렇다면, 과연 어떻게 하면 잘 뒤섞을 수 있을까요? 사실 이 주제는 처음부터 제가 정리하겠다고 염두에 둔 주제는 아니었습니다. 처음에는 쿠폰 수집가 문제(coupon colle..

티스토리툴바