28828번: Упражнения в умножении (acmicpc.net) $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제 n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다 v1 = 1for i in range(n): v1 *= A[i]v2 = 1for j in range(m): v2 *= B[j]print(v1//v2) 곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다 $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{..
14108번: Umnozak (acmicpc.net) n자리 자연수중에서 짝수 위치의 자리수들의 곱과 홀수 위치의 자리수들의 곱이 서로 같게되는 그러한 자연수들의 개수를 구하는 문제 첫번째 자리는 홀수 위치라고 가정 1자리 자연수는 홀수 위치밖에 없으니 0개 2자리 자연수는? 11,22,33,44,55,66,77,88,99로 9개 3자리 자연수는? 100부터 999까지 전수조사해보는게 나을 것 같다 count = 0for i in range(100,1000): s = str(i) a = 1 b = 1 for j in range(len(s)): if j % 2 == 0: a *= int(s[j])..
https://atcoder.jp/contests/abc363/tasks/abc363_d D - Palindromic NumberAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다 그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다 0,1,2,3,4,5,6,7,8,9 >>> 10개 11,22,33,44,55,66,77,88,99 >>> 9개 101, 111, 121, 131, 141, ... ,191202,212,222,232,..., 292303..
1. motivation 우연히 넷플릭스 시스템의 변화로 전체 영화들의 평점 평균이 급격히 상승한 사건이 관측 되었다. 심지어 영화의 평점은 출시일 이후부터 관측해보면 상승하는 경향이 있었음 어떤 영화로 인해 팬이 되면서 오랜 출시일이 지난 영화를 찾아본다거나 입소문이 나면서 평이 좋은 영화를 추천 받아서 본다거나 추천시스템이 좋다고 하는 것을 계속 보거나 2. idea 영화의 평점이 시간에 영향을 받는다는 것을 알았으므로 사용자의 편향과 상품의 편향이 시간의 함수라고 가정함 위 모형을 바탕으로 앞에서와 같이 모형의 복잡도까지 고려한 loss function을 구성하고 경사하강법으로 loss를 줄이면서 최적화시켜 사용자편향, 상품편향, 사용자 embedding, 상품 embedding을 ..
1. 편향(bias) 사용자의 편향은 해당 사용자가 매긴 평점들의 평균과 전체 상품들의 평점평균의 차이 전체 평점평균에 대해 이 사용자는 얼마나 평가를 후하게 하는지 박하게 하는지 알 수 있다. 나연은 전체 상품들의 평점평균에 비해 0.3점 정도 더 주는 경향이 있다. 상품의 편향은 해당 상품이 받은 평점들의 평균과 전체 상품들의 평점평균의 차이 해당 상품이 전체 상품의 평점평균에 비해 얼마나 좋은 평가를 받는지 나쁜 평가를 받는지 알 수 있다. 식스센스는 전체 상품들의 평점평균에 비해 0.8점정도 긍정적으로 평가 받는다 사용자와 상품의 편향은 현재 주어진 데이터로부터 계산한 예측값이다. 그러니까 정확한 상수가 아니라는 뜻이다. 데이터가 추가되면 사용자의 평점이나 상품의 평점은 바뀌기 때문에..
1. motivation UV decomposition이라고도 부른다. (SVD라고도 부르나 수학에서 말하는 SVD랑은 조금 차이가 있음) 사용자와 상품그래프에서 사용자와 상품 node를 embedding vector로 잘 표현하는 것이 핵심이다. 2. example of embedding 사용자와 영화의 정보를 바탕으로 embedding한 예시 빨간색 네모부분 사람은 영화 브레이브하트와 리쏄 웨폰과 가까워서 이 영화를 추천하겠다 그러나 latent factor model의 핵심은 위와 같은 고정된 인수(액션, 로맨스 영화 등등)를 가지는 차원이 아닌 사용자와 상품의 정보를 효과적으로 학습하여 가장 추천을 잘 해줄법한 latent factor를 찾아내 그곳으로 embedding하겠다는 것이다...
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
