xMO 카페에 올라온 조합 문제들

오랜만에 xMO 카페에 들렀는데 조합 문제들 몇 가지가 소개된 글을 보게 되어 여기에서 그 문제들을 살펴보고자 한다. 1번은 Coupon collector’s problem으로도 알려져있는 문제이다. 처음으로 종류의 과자를 얻었을 때의 과자 수를 나타내는 random variable을 , 로 두면 () 구하고자 하는 것은 가 된다. 편의상 라 하면 이므로 답은 이 된다. Probabilistic method에서 자주 쓰이는 linearity of […]

Read More xMO 카페에 올라온 조합 문제들

19-5: 29년만에 클리어된 테트리스

NES 테트리스에는 두 가지 모드가 있다. A 타입 모드는 플레이하다보면 속도가 올라 게임오버되기 전까지 스코어링을 겨루는 모드로 클래식 테트리스 월드 챔피언십에도 쓰이고 있다. B 타입 모드는 레벨과 높이를 지정하면 필드 위에 특정 높이까지 랜덤한 블록들이 일부 주어져있는 채로 25줄을 깨면 클리어하는 일종의 퍼즐 모드이다. 고를 수 있는 레벨은 0에서 19까지인데, 레벨 13-15는 내려오는 속도가 1줄/4프레임, […]

Read More 19-5: 29년만에 클리어된 테트리스

잊혀진 심 게임, SimRefinery

레딧으로 보게 된 Ars Technica의 한 기사(2020/6/5). 심시티를 위시한 심 시리즈로 유명한 맥시스의 잊혀진 게임 SimRefinery에 대한 이야기이다. 심시티의 성공 이후 맥시스는 다른 분야의 시뮬레이션 제작으로도 눈을 돌리고 있었는데, 석유업체 셰브론(Chevron)이 자신들의 정유 회사에 있는 직원들을 가르치기 위한 비슷한 게임이 만들어지길 원했다고 한다. 물론 이 게임을 통해 실제 운영법이나 ChemE 교육을 대체하려는 것은 매우 위험한 […]

Read More 잊혀진 심 게임, SimRefinery

빈 그래프는 수형도인가

트위터에서 empty graph가 tree가 아닌 forest로 분류되어야하는지에 대한 이야기가 있었는데 (원본 트윗은 쓰신 분이 플텍 걸어놔서 보이지 않는다) 여러모로 봤을 때 forest로 보는 것이 타당하다. 이게 문제가 된 이유는 tree의 정의들을 생각해보면 ‘임의의 두 점이 정확히 한 개의 경로로 연결되는 그래프’, ‘연결되고 cycle이 없는 그래프’ 등이 있는데 전자 같은 경우 뽑을 두 점이 애초에 없으니 […]

Read More 빈 그래프는 수형도인가

사상 최악의 일본 입시 수학 문제

구독중인 ‘타마키의 수학’ 유튜브 채널에 올라온 한 영상. 1998년 도쿄대 후기 이과 입시 문제로 나왔던 한 수학문제를 다루고 있는데, 그 악명높은 난이도로 인해 전설이 된 문제라고. 문제는 다음과 같다. 먼저 흰 점 한 개만 있는 그래프가 주어져있다. 여기서 말하는 그래프는 각각의 점에 흑과 백 두 색 중 하나를 칠한 단순그래프를 뜻한다. 이 때, 다음과 같은 […]

Read More 사상 최악의 일본 입시 수학 문제

시컨트 함수의 적분이 발견되기까지

미적분을 공부하는 대학생이라면 한 번은 마주쳤을 적분식 . 이 식이 실은 메르카토르 도법이 디벨롭되는 과정에서 나온 부산물이었다는 내용이다. 이하 시컨트함수의 적분의 역사에 대한 원문[1]의 요약. 항해의 범위가 넓어짐에 따라, 지도를 위도와 경도가 동일한 간격을 갖도록 평면에 그리는 것에 어려움이 따르기 시작했다. 13세기 이후 항해에 나침반을 활용하기 시작했고, 나침반이 가리키는 특정한 방향을 따라 쭉 나아가는 진로를 […]

Read More 시컨트 함수의 적분이 발견되기까지

팩맨 유령들의 AI

루리웹에서 예전에 올렸던 글이 링크되었길래 봤는데, 팩맨 유령들은 다 이름이 있고 제각기 다른 전략으로 움직인다는 내용이다. 마침 작년에 이걸 제대로 설명한 Retro Game Mechanics Explained의 영상을 본 적이 있었기에 그 내용을 소개하고자 한다. 제목에서의 AI는 게임 상에서 등장하는 적이나 NPC 등의 액션 알고리즘을 뜻하고 일반적인 인공지능과는 좀 괴리가 있을 수 있지만 보통 게임에서 이 프로그래밍된 […]

Read More 팩맨 유령들의 AI

터키어 문자 ı와 보안 취약점

해커뉴스를 통해 재밌는 글을 읽었다. case mapping collision이라고 해서, 자바스크립트에서 ‘ß’.toLowerCase()가 ‘ss’가 되는 등 유니코드 일부 문자의 대소문자가 일반 로마자와 같은 것으로 취급된다고 한다. 터키어의 ‘ı'(“점 없는 i”)의 경우 소문자로 변환하면 ‘i’와 같아진다고 한다. 그래서 다음과 같은 상황이 벌어질 수 있다고 한다. 예컨대 깃허브에서는 패스워드 리셋을 요청할 때, string으로 입력받은 이메일 주소에 toLowerCase를 씌워 소문자로 […]

Read More 터키어 문자 ı와 보안 취약점

스테이지 vs. 면(面)

게임에서 보통 레벨이나 스테이지에 해당하는 단어를 일본에서는 面(멘, 이하 ‘면’으로 부름)이라고 부른다. 예컨대 1면, 2면 이런 식으로. 어쩌다 그렇게 됐는지 궁금해서 찾아보니 위키피디아에 장황한 설명이 있었다. 출처에도 등장하는 한 인터넷 기사를 다소 참조한 것으로 보인다. 해당 설명에서는 이 ‘면’이란 단위의 기원을 1978년 등장한 <스페이스 인베이더>로 보고있다. 한 화면에 등장한 적을 전부 없애는 것으로 다음 phase로 […]

Read More 스테이지 vs. 면(面)