로또는 우리 인생에서 확률이라는 보이지 않는 수를 몸으로 체감할 수 있는 좋은 기회다.하지만 늘 조작이라는 의심이 따르는 편이다.오늘은 문득 로또를 구매하다가 역대 당첨 기록으로부터 조작의 증거를 발견할 수 있을까 하는 생각이 들었다.그렇다. 혹시 벤포드의 법칙이 통할 것인가 궁금해서 확인해보려다가, 조금 더 생각해보니까 아니라는 생각이 들었다.로또는 어떤 흐름 속에서 연속되는 수들이 있는 게 아니라, 매 회차별로 독립 시행이다.그렇다면 큰 수의 법칙을 따를테니 정규 분포가 보이지 않을까 생각해봤다.간단하게 확인할 방법을 궁리해봤는데, 간단하지 않을 것 같았다.각 회차별로 등장하는 당첨 숫자는 7개(보너스 숫자도 포함)이다. 그럼 변수가 7개이므로 각 $p(X_1)$ 부터 $p(X_7)$ 에 대한..

Logit logit 함수를 이해하려면 odds 를 알아야한다. logit 함수는 $logit(p) = log(odds)$ 이기 때문이다. Odds odds 는 어떤 사건이 발생할 확률과 발생하지 않을 확률을 비교한 값이다. 일반적으로는 성공 확률을 실패 확률로 나누어서 계산한다고 한다. $$odds = \frac{p}{1-p}$$ 여기에 로그를 씌운 함수를 logit function 이라고 부른다. $$logit(p) = log(odds) = log(\frac{p}{1-p})$$ 이 logit function 을 x=[0, 1] 에 대해서 그래프를 그려보면 아래와 같이 생겼다. Sigmoid sigmoid 함수는 logit function의 역함수이다. 즉, x와 y를 뒤집은 그래프라는 ..

문제 이번 문제는 문제적남자 4화에 나온 뇌풀기문제이다. 6개의 9를 사용해서 100을 만드는 수식을 찾는 문제인데, DFS로 모든 경우의 수를 탐색하면 되는 전형적인 문제로 보인다. 숫자들 사이에 수식을 끼워 모든 경우의 수를 만들어보고, 파이썬의 eval 함수로 계산한 결과가 100 이 되는 경우만 세어보면 될 것 같다. 9와 사칙연산만 사용하기 6개의 9 사이마다 사칙연산을 끼워넣어서 100이 만들어지는 경우를 찾아본다. 4개의 연산자를 5개의 공간에 끼워넣으므로 경우의 수는 $4^5 = 1024$ 가지밖에 되지 않는다. 정답은 12개로 생각보다 많은데, 이건 순열이 달라서 세어진 것이고 조합으로 보면 단 하나이다. (정답 아래에 적음) 정답 9+9+9/9+9*9 = 100.0 9+9+9*9+9..

링크: https://www.acmicpc.net/problem/2133 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 풀이 3×N 벽을 채우는 경우를 $f(n)$, 한 칸이 빈 3×N 벽을 채우는 경우를 $g(n)$ 라고 하자. 왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다. $g(0)$와 $g(2)$는 타일을 채울 방법이 없으므로 $g(0) = g(2) = 0$ 이다. 이것을 식으로 나타내면 이렇다. $$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$ $$g(n) = \begin{cases} 1 & \text{i..

성능 테스트 코드를 작성하다가, 평균을 실시간으로 구하는 방법을 글로 정리해볼까 한다. (직관으로) 어렸을 적에 이게 당연한 줄 알았다. 근데 몇개의 반례를 찾고는 틀렸다고 생각했다. 그런데 학부 시절에 교수님께서 '그런 것이 있다'고 말씀해주셨다. 이름은 Moving average이고, 한국어로는 모르겠다. 나는 데이터 범위에 따라 점진적으로 평균을 구해간다는 느낌으로 점진적 평균 또는 실시간 평균으로 부르고 싶지만, 통계쪽에서 "이동 평균"으로 부르는 모양이다. 아무튼, 본디 평균을 구하는 식은 전체 합 $S_n$에서 데이터의 개수 $n$만큼 나눈 $S_{n} / n$ 이다.그럼 이것이 뭐가 문제인가?$n$개를 전부 더하거나 카운팅 하지 않으면 평균을 구할 수 없다. 어떤 실험 \(X_..

링크: https://www.acmicpc.net/problem/1699문제주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다. 문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다. 백준 온라인 저지에 문제로도 등장했다. BOJ 3933 - 라그랑주의 네 제곱수 정리 요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다. $x^a + y^b + z^c + w^d = N$ 에서 $a,~b,~c,~d$ 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 $a,~b,~c$를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다. 즉, 3중첩 반복문으로 해결 가능하다.코드

링크: https://www.acmicpc.net/problem/11447문제문제에서 정의되는 x, y, z 방향으로 1000을 넘지 않는 길이만큼 C번 움직인 후에, 마지막에 완성된 그림 속에 채워지는 삼각형의 수는 몇 개인지 맞추는 문제이다.삼각형들은 빈 공간이 없이 빽빽하게 채워져있고, 다시 시작점으로 돌아오지 않는 잘못된 입력은 주어지지 않는다. 처음에는 x,y,z 방향을 2차원 x,y 평면으로 적당히 전사시켜서 그 넓이를 구하는 방식으로 해야하나? 라는 생각을 했다. 그 외에도 문제를 변형시키는 별 생각을 다 했는데 결국 풀이는 다각형의 면적을 구하는 문제였다.풀이다각형을 이루는 꼭짓점들이 주어지면, 그 다각형의 면적을 구하는 문제이다. 이건 신발끈 공식으로 해결할 수 있다. 다각형의 각 꼭짓점..

링크: https://www.acmicpc.net/problem/15719문제자료형의 비트를 이용하여 배열을 압축하여 사용하는 방법과, 수학으로 푸는 2가지 풀이를 소개하려 한다.풀이 1 (비트)표현할 정수의 범위는 [0, 10000000]이다. 그리고 필요한 정보는 각 숫자들이 사용되었는가/아닌가 이다.사용되지 않았다면 0, 사용되었다면 1로 표현한다면 숫자 하나의 사용 여부를 하나의 비트로 관리할 수 있다. 즉, 32비트 정수 하나에 32개의 수의 상태를 담을 수 있다.그럼 배열의 크기는 $\lceil 10~000~000 / 32 \rceil = 312~500$만큼 필요하다. 코드는 훨씬 간단하다.코드 풀이 2 (수학)1부터 $n-1$까지의 수가 골고루 등장한다. 등장한 모든 수의 합을 \(S..