🎲확률 및 통계 썸네일형 리스트형 그래프 색칠 (Graph Coloring) 알고리즘 - 램지 수 문제 예제 이런! 학회 뱅큇에서 일행을 놓쳐 버렸다! 사람이 너무 많아 찾기를 포기하고 그냥 아무 테이블에 앉아 버리는데.... 이때 테이블에 여섯 명이 앉는 경우 서로 아는 관계인 세 명의 그룹이나 서로 모르는 관계인 세 명의 그룹이 반드시 존재함을 보이시오. (!!) 아니, 이게 웬 유학 준비하다 잘 안 풀려서 급하게 준비했던 기업 인적성에서나 보던 문제입니까. 문제집에서 이런 문제를 보면 왜 풀어야 하나 하는 의문을 한 번쯤 가져보신 적이 있을 겁니다. 이런 문제를 수학적으로 모델링할 때는 여러 행위자 (위 예시에서는 사람)가 있고 그것들 간의 관계를 표현할 수 있는 그래프가 사용됩니다. 제가 수학을 전공하지는 않아서 그래프 이론 전반에 대해서는 잘 모르지만, 통신 분야에서는 그래프 안에서 발생하는 연결에 초.. 더보기 Reservoir Sampling Algorithm - 순차적으로 한 번에 하나의 샘플만 볼 수 있고 전체 샘플 개수를 모르는 상황에서 무작위 추출을 하는 방법 왜 이런 설정에서 무작위 추출을 할 수 있는 것이 중요할까? 오늘은 확률 기법 수업의 숙제로 받은 연습문제를 풀다가 재미있는 알고리즘을 알게 되어 글을 쓰게 되었습니다. 보통 random sampling(무작위 추출)과 관련된 문제를 풀 때면 우리는 주머니에 들은 여러 개의 공 중에 하나의 공을 뽑는 것처럼 모든 샘플을 모아 두고 거기서 하나를 공평하게 뽑는 상상을 합니다. 하지만 항상 모든 샘플에 대한 접근이 가능한 것도 아니고 샘플의 개수가 총 몇 개인지도 모르는 경우도 있습니다. 예를 들어, 메모리가 제한적인 기기를 생각해보지요. 모든 샘플을 다 저장해둔 후 총샘플의 개수를 알고 각각의 샘플을 1/(샘플의 총 개수)의 확률로 무작위 추출을 하려면 샘플의 개수만큼 많은 메모리가 필요합니다. 하지만 메.. 더보기 이전 1 다음
