꺼내먹는지식 준

베이즈는 이미 2번 정리를 했지만, 여러번 볼 수록 좋기에 한번 더 정리를 한다. Supervised Learning Unsupervised Learning Label이 있는 learning (분류, regression) label 없이 주어진 데이터로 패턴 파악(clustering, Filtering) Unsupervised Learning 예시: 주어진 신문기사 4만개에서 10개로 분류해보아라. labeling 과정을 거칠 필요가 없이 clsutering 하면 된다. 이항 분포 이산 확률 분포 $$\textrm{n번중 k번 성공}$$ $$f(k;n,p) = P( K = k ) = \binom{n}{k} \, p^k (1-p)^{n-k}$$ $$\binom{n}{k} = \frac{n!}{k! (n-k..

베이지안 라이브러리가 필요한 이유 베이지안이 어려운 이유는 실제로 conjugate distribution 을 찾기 어렵기 때문이다. 이로 인해 MCMC 샘플링을 사용하는 방식을 많이 사용하고 대표적인 library 로 PYMC3 가 있다. 복잡한 과정을 모두 대신해준다. 생각보다 듀토리얼이 없어서 아주 간단한 이론적 배경과 사용법을 정리해본다. 해당 글을 읽었을 때의 유익 저자는 본 글을 읽고나서 베이지안 사고방식이 어떤 의미인지, 그리고 해당 사고방식을 어떻게 접목해야하는지 깨달을 수 있는 기회가 되었다. 해당 내용은 https://nbviewer.org/github/markdregan/Bayesian-Modelling-in-Python/blob/master/Section%201.%20Estimati..

베이즈를 활용해서 연구도 해봤고, 어느정도 이해했다고는 생각하지만 항상 약간만 깊이 들어가면 내가 아무것도 모르는 구나를 깨닫게 된다. 이론적으로 완벽할 필요는 없지만 어느정도 구조에 대한 파악이 필요하다고 생각한다. 아래 블로그는 웹서핑 과정 중에서 만난 여지껏 어떤 블로그보다 베이즈에 대한 개괄을 잘 작성해놓은 블로그이다. 본 글은 내 사전지식에 맞춰 좀 덜거나 더해 작성되었기에 해당 글을 읽는 것보다 아래의 블로그 글을 읽는 것이 더 좋을 것 같다. 물론 나랑 사전 지식이 비슷하다면 이 글이 오히려 좋을 수도 있다. http://posterior.egloos.com/9606941 베이즈 정리 (일반적 형태) 앞의 글들에서 베이즈 정리의 의미와 그 사용 예시를 살펴보았다. 이제 본격적인 베이지안 추론..

정규분포의 확률밀도함수 유도정도는 이해하고 있어야 추후 여러 수학 공식 이해가 쉬울 것으로 보인다. https://www.youtube.com/watch?v=sFMjrnI93b4  아래와 같은 과녁 중심을 향해 화살을 쏜다고 가정하자. 목표가 과녁 중심이기에 아래가 성립한다. 1. 과녁의 중심에서 멀어지면 확률이 낮다. 2. 중심에서 거리가 같은 곳에 맞출 확률은 같다. 3. x좌표와 y좌표는 독립적이다. x, y 좌표에 의해 확률이 정해지므로 $f(x,y)$ : (빨간 점에 맞을 확률) (x, y는 서로 독립이므로) $f(x,y) = f(x \cap y) = f(x)f(y)$ 과녁을 중심으로 같은거리의 점들은 모두 맞을 확률이 같으므로, 반지름 r 만으로 확률이 정해진다. 빨간점에 맞을 확률: $g..

동전 1 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 4 MB 45880 20871 15733 45.615% 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 예제 입력 1 복사 3..

동전 2 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 52312 15520 10880 28.955% 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불..

LCS 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.1 초 (하단 참고) 256 MB 56865 23037 16944 40.292% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 예제 입력 1 복사 ACAYKP CAPCAK 예제 출력 1 복사 4 출처 Knapsack 문제이다. ACAYKP CAPCAK..

평범한 배낭 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 75395 27716 18066 35.260% 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알..

병사 배치하기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 6064 2393 1834 41.093% 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다...

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 예제 입력 1 복사 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 예제 출력 1 복사 30 위와 같이 삼각형 문제를 풀 때면 항상 in..