1. 키타마사 법(kitamasa method) 수열 $a_{n}$의 점화식을 이전의 몇개 항으로 정의한다면, 귀납적 정의, 재귀적 수열 등으로 부른다. $$a_{n} = \sum_{i = 1}^{k} w_{i}a_{n-i}$$ 이런 형태로 정의되는 대표적인 수열은 피보나치 수열이다. $$a_{n} = a_{n-1} + a_{n-2}, w_{1} = w_{2} = 1, k = 2$$ 이 피보나치 수열의 가장 빠른? 해법중 하나는 행렬을 이용하는 방법이다. https://deepdata.tistory.com/760 행렬을 이용한 피보나치 수열 문제의 해법 1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + ..
1. 다항식의 곱셈 두 다항식의 곱셈은 구현하는 방법이 많이 있지만... 당장은 어려우니 일단 $O(k^{2})$으로 naive하게 구현 해보자. 다항식은 각 항의 계수를 배열에 저장하면 되는데 $f(x) = 2x^{2} + x + 1$이라고 한다면, a = [1,1,2]로 저장하면 된다. 곱셈하고자 하는 다항식이 $g(x) = x + 5$라고 한다면 b = [5,1]이고 두 다항식의 곱셈은 $f(x)g(x) = 2x^{3} + 11x^{2} + 6x + 5$로 [5,6,11,2]가 나와야한다. f(x)가 len(a)-1차수 다항식이고 g(x)가 len(b)-1차수 다항식이면, f(x)g(x)는 len(a)+len(b)-2차수 다항식이다. 위에서 len(a) = 3, len(b) = 2이고 각각 2차 1..
1. 사칙연산 C++에서 사용되는 사칙연산 덧셈, 뺄셈, 곱셈, 나눗셈은 각각 +,-,*,/으로 구할 수 있다. #include using namespace std; int main() { int a = 9, b = 4; cout
1. 문제 27965번: N결수 (acmicpc.net) 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 2. 풀이1 쉽다는데... 솔직히 까다로운 문제같다 n이 10의 7제곱까지라 n결수를 만들면 당연히 시간초과일거고 (애초에 만들어지지도 않음) 그 전에 근본적으로 나눗셈 연산을 어떻게 하는지 생각을 해보면.. 1234를 5로 나누는 것은 어떻게 할까? 1을 5로 나눠보고.. 몫이 0이고 나머지가 1이니까 ..
1. 문제 N개의 정수들이 있습니다. 이 중 정확히 앞에서부터 K개를 삭제하고 난 후, 남아있는 정수 중 가장 작은 숫자 하나를 제외한 평균을 구한다 했을 때 이 평균값이 최대가 될 때의 값을 구하는 프로그램을 작성해보세요. 단, K는 1이상 N - 2 이하까지만 고려하도록 합니다. 아니 쉬운문제 같은데 메모리,시간제한 도저히 안되는데..? 2. 풀이 K=1부터 시작해서, 배열에서 1개 지우고 나머지 N-1개에서 최솟값을 찾아 지우고, 평균을 구하고 K=2이면, 2개 지우고 나머지 N-2개에서 최솟값을 찾아 지우고, 평균을 구하고. ... K=N-2이면, N-2개 지우고 나머지 2개에서 최솟값 찾아 지우고, 평균 구하고 이렇게하면, 최솟값 찾는 과정에서 우선순위 큐에 매번 N-1개의 원소넣고 최솟값 찾고..
1. 나눗셈 연산의 몫과 나머지 나머지는 %연산으로 구할 수 있지만 몫을 구하는 연산은 python과는 다르게 따로 존재하지 않는다 몫을 구할려면 나눗셈 결과 a/b를 int형 변수에 저장하면 된다 1-1) 형변환에 주의 첫번째 (double)a / b는 a를 double로 바꾼 9.0을 4로 나눈 2.25를 내놓지만 (double) (a/b)는 a/b 결과인 2를 double로 바꾼 2.0을 내놓는다. 그런데 a/b 결과가 왜 2냐고? 정수 a,b끼리의 나눗셈 / 연산은 실수가 아니라 정수로 내놓는다. 나눗셈 연산에서 두 항이 모두 정수형이면 / 연산 결과는 정수형(몫)이 나온다. public class Main { public static void main(String[] args) { int a =..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
