5624번: 좋은 수 (acmicpc.net) 정수 배열에서 현재 위치 i번째 수 앞에 있는 수들 중 세 수의 합이 현재 위치 i번째 수와 같게 되는 경우, 그러한 수의 개수를 구하는 문제 "세 수"는 중복해서 선택해도 좋다 예를 들어 [-1,2,0]이면 0은 -1 -1 + 2 = 0이므로 이 조건에 만족하는 수이다 n이 최대 5000인데, 단순하게 짜면 $O(N^{4})$이라 매우 느리다 대충 이런 느낌 for i in range(n): a = A[i] for j in range(i): for k in range(i): for w in range(i): ..
matrix나 tensor는 linear transformation이다. 1차원의 [0,1]의 선분을 linear transformation T(x)=3x를 통해 변환하면 3배 늘어난 선분 [0,3]이 된다 주어진 2차원의 정사각형 ABCD를 linear transformation 을 통해 변환하면 2배 늘어나고 회전된 정사각형 A’B’C’D’이 된다 조금 더 복잡하게 주어진 정사각형을 늘리거나 회전시키거나 비틀어버리거나 하더라도 linear transformation 수학적으로 vector space V,W에 대하여 f: V → W가 linear map이라는 것은 임의의 vector u,v ∈ V와 scalar c가 $f(u+v)=f(u)+f(v)$ , $f(cu)=cf(u)..
1. 일렬로 앉은 경우 먼저 n명의 사람이 일렬로 앉아있다고 생각해보자. a1, a2, a3, ... , an이 일렬로 앉아있고, 여기서 서로 인접하지 않게 b1,b2,...,bk를 선택한다고 생각해보자. b1,b2,...,bk가 서로 인접하지 않다는 것은 무슨 뜻일까? 먼저 선택한 k명 b1,b2,...,bk 사이의 선택받지 못한 x1,x2,x3,..,xk,xk+1에 대해, x1+x2+...+xk+1 = n-k이다. 왜냐하면 n명중 k명 b1,b2,..,bk를 선택하고 나서 남은 사람은 n-k명이니까 여기서 b1,b2,..,bk가 서로 인접하지 않을려면 그 사이에는 사람이 최소 1명이상 있어야한다. 즉, x2,x3,...,xk는 최소 1 이상이고 x1,xk+1은 0이상이다. 그러므로 구하고자 ..
1. 중복조합 n종류가 있을 때, k개를 선택하는데 종류의 중복을 허용해서 선택하는 방법의 수를 구하고 싶다. 예를 들어 a,b,c 3개의 문자 중 5개를 중복을 허용해서 선택한다면 (a,a,a,a,a) (a,a,a,a,b) (a,a,a,b,c) .... (b,b,b,c,c) 등등이 있다. 이러한 방법의 수를 어떻게 찾을 수 있을까? 5개의 빈칸에 a,b,c를 결정하면 되는데 2개의 칸막이를 이용해서 다음과 같이 구별하는 방법의 수로 이해할 수 있다 x1,x2 2개의 칸막이를 적당히 옮겨서 첫번째 영역에는 a를 전부 넣고, 두번째 영역에는 b를 전부 넣고 세번째 영역에는 c를 전부 넣는다. n종류를 구분할려면 필요한 칸막이의 개수는? n-1개이다. 1개를 놓으면 2 영역이 생기고 2개를 놓으면 3 ..
C - Sigma Problem (atcoder.jp) C - Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp f(x,y) = x + y를 $10^{8}$로 나눈 나머지라고 정의 모든 i = 1,2,3,...,n-1, i 예를 들어 3 50000001 50000002이면... (3, 50000001), (3, 50000002), ( 50000001, 50000002)가 있고... 50000004, 50000005, (100000003 % 100000000 = 3)이 된다. 이들을 합하면 10000..
13904번: 과제 (acmicpc.net) 과제의 기간 제한이 있고 해당 과제를 수행했을 때 얻는 가치가 서로 다르다 하루에 하나씩 과제만 처리할 수 있다. 주어진 과제들을 적절히 처리해서 최대 가치를 구한다면? --------------------------------------------------------------------------------------------------------------------------- 처음에는 과제 점수가 높은 순서대로 내림차순 정렬해서 현재 날짜랑 비교해서 처리할 수 있는 과제면 일단 가져가고 날짜랑 비교했을 때 처리할 수 없는 과제면.. 지금까지 가져간 과제들 비교해서... 실제 처리할 수 있는지 체크해보는것? 4 604 401 202 503 304 1..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
