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. 피보나치 수열 $F_{1} = F_{2} = 1$이고 3이상의 자연수 n에 대하여, $F_{n} = F_{n-1} + F_{n-2}$를 만족하는 수열 $F_{n}$을 피보나치 수열이라고 부른다. 2. 피보나치 수열을 만드는 방법 어떤 자연수 n이 주어졌을때, $F_{n}$을 O(1)에 바로 계산할 수 있는가? 1,1,2,3,5,...로 더해나가 n번째 피보나치 수열의 항을 구하는 것이 아니라 n만 알면 n번째 피보나치 수를 바로 구할 수 있는지? 3. 선형점화식의 특성방정식(characteristic equation) 선형점화식 $$f(n) = a_{n+k} + c_{1}a_{n+k-1} + c_{2}a_{n+k-2} + ... + c_{k}a_{n}$$에 대하여, 모든 i = 0, 1, 2, ....
1. 문제 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 주어진 수열의 점화식에서 A[N]을 구하는 문제 2. 풀이 처음에 그냥 이게 문제?하면서 점화식 그대로 작성했는데 메모리 초과남.. from sys import stdin n,p,q = map(int,stdin.readline().split()) dp = [0]*(n+1) dp[0] = 1 for i in range(1,n+1): dp[i] = dp[i//p]+dp[i//q] print(dp[n]) n의 최대 범위는 $10^{12}$인데 메모리 제한은 128mb라서 그런 것 같다 근데 dp[n]을 구할려면, dp[n//p]와 d..
1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..
1. 재귀함수 DFS/BFS를 구현하려면 재귀함수도 이해하고 있어야한다 재귀함수는 자기 자신을 다시 호출하는 함수 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 이 코드를 실행하면 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다 물론 어느정도 출력하다보면 오류 메시지를 출력한다 재귀의 최대 깊이를 초과했다는 애용으로 파이썬 인터프리터가 호출 횟수의 제한이 있기 때문이다 무한대로 재귀 호출을 할 수는 없으며 애초에 그런 문제 또한 출제될리는 없다 2. 재귀함수 예시 어느 한 컴퓨터공학과 학생..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
