전체 글
-
피보나치 타일링(Fibonacci Tilings)알고리즘 2022. 4. 20. 04:32
한국에서는 2×N 타일링 문제로 많이 알려져있는 문제이다. 세로 길이 2, 가로 길이 n인 직사각형에 대하여 세로 2, 가로 1인 타일과 세로 1, 가로 2인 타일로 채우는 방법의 수를 구하는 문제이다. n=8인 경우의 예시는 다음과 같다. 이 문제는 어떻게 풀어야하는가? 간단하게 점화식을 이용하여 풀 수 있는데, 제목에서 알 수 있듯이 결론적으로 이는 피보나치 수의 형태를 띄게 된다. 함께 보도록 하자. 가로 길이가 n일 때 채울 수 있는 총 방법의 가짓 수를 a_n이라고 한다면 다음과 같이 표현 될 수 있다. 여기서 중요한 점은 바로 "과연 모든 가짓 수를 표현 하는가?" 이다. 이 점을 잊지 않고 생각을 해보도록 하자. a_n-2의 다른 가짓 수 1개 즉, 세로로 2개가 세워지는 경우는 a_n-1에..
-
몬티홀 문제(Monty Hall problem)에 관하여 - 6편(完)수학 2020. 12. 15. 01:17
드디어 내가 계획한 마지막 파트에 도달하였다. 마지막 6편에서는 전통적인 몬티홀 문제의 일반화에 대해서 알아보며 마무리를 지을 것이다. 만약 문이 n개면 어떻게 될까? 그리고 좀 더 나아가 문이 n개이고 사회자가 문을 k개씩 개방하면 어떻게 될지 알아볼 것이다. 문이 n개일 때는 몬티홀 문제를 어떻게 해결해야하는가? 마찬가지로 경우의 수의 방법으로 접근을 해보자. 여전히 대칭성이 있으므로 자동차의 배치가 [자동차, 염소, 염소, ... , 염소]라고 가정을 하고 시작해도 되지만 이번에는 좀 더 자세히 해보기 위해 모든 경우에 대해서 고려해보자. 자동차의 배치에 대한 가능한 경우의 수는 그렇다면 [자동차, 염소, 염소, ..., 염소] ~ [염소, 염소, 염소, ..., 자동차] 까지 총 n가지를 가질 것..
-
몬티홀 문제(Monty Hall problem)에 관하여 - 5편수학 2020. 12. 14. 02:48
우리는 1~4편을 통하여 몬티홀 문제에 대해서 심도있게 다뤄보았다. 그렇다면 우리는 이제 몬티홀 변형 문제에 대해서 유사한 방법으로 접근해볼 수 있다. 이번 5편에서는 웹서핑 도중 발견한 몬티홀 변형 문제에 대해서 같이 해결해보고 후반부에는 몬티홀에 관한 몇가지 설명에 대해서 고찰을 해볼 것이다. Problem: 세개의 문이 있고 , 두개의 문에는 염소, 한개의 문에는 자동차가 있다. 사회자는 어느 문 뒤에 무엇이 있는지 모두 알고 있으며 이때 참가자 A, B 두 명이 각자 다른 문을 선택하였다. 모든 정보를 가지고 있는 사회자는 두 사람중에서 염소를 고른사람 한명을 먼저 공개하기로 한다. 사회자가 한 참여자의 문이 염소임을 공개하고는, 다른 참가자에게 물어본다. 현재의 선택을 고수하시겠습니까? 아니면 ..
-
몬티홀 문제(Monty Hall problem)에 관하여 - 4편수학 2020. 12. 12. 01:49
지금까지 우리는 1~3편을 통해 몬티홀 문제에 대해서 자세히 알아보았다. 하지만 우리는 이 문제에서 당연하다는 듯이 사용해왔던 원리 하나에 대해서 알아볼 필요가 있다. 우리는 몬티홀 문제를 해결하는데 있어서 암묵적으로 사용해온 원리가 하나 있는데 이 원리는 바로 '이유 불충분의 원리(Principle of indifference)' 이다. 즉, '자동차가 있는 문이 선택되었을때 나머지 문들에 대한 사회자 몬티의 선호도는 같음' 등등이 암묵적으로 전제되어있음을 알 수 있다. 아무런 정보가 없으니 이유불충분의 원리로 각각에 대한 확률이 동등하다고 가정하겠다는 것이다. 그렇다면 이유 불충분의 원리란 무엇인지 좀 더 이야기를 해보도록 하자. 우선 우리는 이유 불충분의 원리를 설명하기 전에 상호배타(Mutual ..
-
몬티홀 문제(Monty Hall problem)에 관하여 - 3편수학 2020. 12. 11. 01:55
1,2편에서 우리는 전통적인 몬티홀 문제에 대해서 자세히 알아보았다. 그렇다면 이제는 몬티홀 문제를 조금 더 심화하여 문이 3개가 아니고 확장하여 문이 4개일 때는 어떻게 되는지 한번 알아보도록 하자. 진행 순서는 1편(https://escape-portal.tistory.com/4)에서 설명한 것과 동일하고 문이 1개 추가되었다. 그렇다면 이제 시작해볼 수 있다. 자동차는 어떻게 배치되어 있을까? 배치하는 경우의 수는 다음과 같다. 4가지의 배치순서 : (자동차, 염소, 염소, 염소), (염소, 자동차, 염소, 염소), (염소, 염소, 자동차, 염소), (염소, 염소, 염소, 자동차). 문이 3개일 때와 마찬가지로 여전히 대칭성이 유지되므로 결정된 한가지의 배치에 대한 확률만 구하면 된다. 따라서, 왼..
-
몬티홀 문제(Monty Hall problem)에 관하여 - 2편수학 2020. 12. 10. 01:26
1편에서(https://escape-portal.tistory.com/4) 전통적인 몬티홀 문제에 대하여 자세히 알아보았다. 2편에서는 1편에서 구한 결론이 적절한지 비교해보기 위하여 몬테카를로 방법(Monte Carlo Method)을 이용하여 설명을 진행해보겠다. 이 때 몬테카를로 방법이란 무작위 추출된 난수를 이용하여 함수의 값을 계산하는 통계학적인 방법으로, 사용한 프로그래밍 언어는 파이썬(Python)을 이용하였다. 우선, 몬테카를로 방법에서 중요한건 모집단(Population)이란 개념으로 이는 가능한 경우들의 전체집합이다. 이런 모집단으로부터 전체가 아닌 부분집합을 뽑아 표본을 만들고 표본의 통계를 이용하여 모집단을 추론하게 된다. 이때 중요한 사실은 무작위로 표본을 추출하면 그 표본이 모집..
-
몬티홀 문제(Monty Hall problem)에 관하여 - 1편수학 2020. 12. 8. 21:26
몬티 홀 문제는 미국의 TV 게임 쇼 《Let's Make a Deal》에서 나온 문제로 일반적으로 상당히 직관에서 벗어나는 문제라고 알려져 있으며 실제로 설명들을 읽어보아도 아리송한 설명들이 매우 많다. 그래서 한번 자세히 풀어보고자 한다. 몬티홀 딜레마 라고도 불리는 그 유명한 몬티홀 문제는 다음과 같다. Problem: 세 개의 문 중에 하나를 선택하여 문 뒤에 있는 선물을 가질 수 있는 게임쇼에 참가했다. 한 문 뒤에는 자동차가 있고, 나머지 두 문 뒤에는 염소가 있다. 이때 어떤 사람이 예를 들어 1번 문을 선택했을 때, 게임쇼 진행자 몬티는 3번 문을 열어 문 뒤에 염소가 있음을 보여주면서 1번 대신 2번을 선택하겠냐고 물었다. 참가자가 자동차를 가지려 할 때 원래 선택했던 번호를 바꾸는 것이..