알고리즘 & 확률 (14) 썸네일형 리스트형 상자에 공 넣기, 상자를 두 개씩 고르면? (Power of Two Choices) 지난 포스트에서는 상자에 공 넣기 문제(balls into bins problem)를 공부했습니다. 2020/03/21 - [수학적 도구/Randomness] - 상자에 공 넣기 (Balls into Bins Problem) 상자에 공 넣기 (Balls into Bins Problem) 다음과 같은 상황을 생각해 보죠. 여러분의 눈 앞에는 \(n\) 개의 상자가 있고 옆에는 \(n\) 개의 공이 있습니다. 여러분은 공을 상자에 넣어야 합니다. 항상 특별한 일상을 원하는 여러분은 좀 독특한 방식으로.. gazelle-and-cs.tistory.com 문제는 다음과 같았습니다. 우리에게 \(n\) 개의 공이 주어지고 우리는 이를 \(n\) 개의 상자에 담으려고 합니다. 만약 우리가 공을 하나씩 넣을 때마다 .. 상자에 공 넣기 (Balls into Bins Problem) 다음과 같은 상황을 생각해 보죠. 여러분의 눈 앞에는 \(n\) 개의 상자가 있고 옆에는 \(n\) 개의 공이 있습니다. 여러분은 공을 상자에 넣어야 합니다. 항상 특별한 일상을 원하는 여러분은 좀 독특한 방식으로 공을 상자에 담아 보고자 합니다. 바로 공 하나를 넣을 때 상자를 균등한 확률(uniformly at random)로 선정하여 거기에 담는 것이죠. 과연 이런 방식으로 넣었을 때 상자에 담긴 공의 개수 중 가장 큰 값은 무엇일까요? 최악의 경우에는 당연히 \(n\)이 됩니다. 상자 하나에 모두 담기는 것이죠. 하지만 이런 경우가 많이 일어날까요? 각각의 공이 각 상자에 담길 확률이 \( \frac{1}{n} \)이고 이전에 공을 어떻게 넣었느냐가 이번에 넣을 공을 어떻게 넣을지 영향을 주지 않.. 야오의 법칙 (Yao's Principle) 이번에는 Yao's principle에 대해서 알아보도록 하겠습니다. 이 글은 이전 포스트에서 이어지는 내용이 많으므로 이를 먼저 읽어 보시는 것을 추천드립니다. 또한 확률에 대한 기본적인 내용을 숙지하셨다는 가정 아래 글이 작성되었다는 점도 밝힙니다. 2019/08/11 - [수학적 도구/Randomness] - Arbitrary & Random Arbitrary & Random 이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데.. gazelle-and-cs.tistory.com 지난 시간 'random'을 설명하기 위해서 같이 고민했던.. Arbitrary & Random 이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데 어쩔 수 없었습니다. 컴퓨터과학을 전공하신다면 아마 두 단어를 많이 접하셨으리라고 생각합니다. 그만큼 많이 사용되는 단어인데 제대로 아시는 분은 그리 많지 않을 겁니다. 당장에 저만 하더라도 대학교 졸업할 때까지 둘의 차이를 명확하게 알지 못하였습니다. 대학원에 들어오고 나서야 둘의 차이를 구분할 수 있게 되었죠. 이렇게 헷갈리는데 우리말로 이를 제대로 설명한 글은 찾기가 힘들더군요. 우리말로 'arbitrary'는 '임의의'로, 'random'은 '무작위의' 정도로 번역이 되겠습니다. (.. 이전 1 2 다음
