1. 문제 25214번: 크림 파스타 (acmicpc.net) 25214번: 크림 파스타 각 \(A_i\)가 추가된 직후의 문제의 답 \(N\)개를 공백으로 구분하여 출력한다. www.acmicpc.net 2. 풀이 그냥 단순하게 생각해서 배열 원소의 최댓값과 최솟값을 기억해두고, n개의 원소를 처음부터 순회해서, A[i]가 최대인지 검사하고 최대라면 최댓값을 갱신한다음에, dp[i]에 최댓값 - 최솟값을 넣어주면 되는거 아녀? 새로 들어온 값이 최댓값이 아니라면, dp[i]는 이전에 구한 dp[i-1]과 같을거고 최댓값이 아닌 경우에 당연히 A[i]가 최솟값이 될 자격이 있으니까 A[i]가 최솟값인지 검사하고 A[i]가 최솟값이라면 최솟값을 갱신해준다 여기서 $i \leq j$인 i,j에 대하여 A[j..
1. 문제 2247번: 실질적 약수 (acmicpc.net) 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1부터 n까지 각각 약수들 중 1과 자기 자신을 제외한 약수들의 합들의 누적합을 구하는 문제 2. 방법1 가장 쉬운 방법은 1부터 n까지 순회해서 각 자연수를 i라고 한 다음, i에 대한 모든 약수를 구해서 1과 자기 자신을 제외하고 더하면 된다 약수는 $O(\sqrt{n})$ 알고리즘으로 모두 나눠보는 방식으로 구한다 그런데 p = 1부터 시작하면, i를 1로 나누면 1과 i를 더하게 되는데 실질적 약수라면 1과 i를 제외한 나머지들의 합을 구해야하니 p = 2부터 시작하는게 핵심 n = int(input()) ans..
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. 문제 19947번: 투자의 귀재 배주형 (acmicpc.net) 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 2. 풀이 아주 기본적인? 다이나믹 프로그래밍.. 근데 어떻게 하는건지 잠깐 기억이 안났었다는게 함정 dp를 길이가 y+1인 배열 [0]*(y+1) 초기화할테고 dp[0] = h여서.. y년 후의 금액이 dp[y]라고 해서.. 1년,3년,5년 투자 방식중 최댓값을 골라 dp에 저장할텐데 이거 어떻게 하더라... 잠깐 정적.. ------------------------------..
1. 문자열의 부분 문자열 중 가장 긴 palindrome의 길이 찾기 abaccaba와 같이 뒤집었을 때 결과가 동일하다면, 그러한 문자열을 palindrome이라고 부른다. 문자열이 하나 주어졌을때, 해당 문자열의 부분 문자열 중 가장 긴 palindrome의 길이를 구하고자 한다. 예를 들어 bananac의 부분 문자열 중 가장 긴 palindrome은 anana로 길이가 5이다. 1-1) 완전탐색($O(N^{3})$) 이 문제를 가장 쉽게 해결하는 방법은 문자열을 순회하면서 가능한 모든 경우에 대해 완전탐색을 수행하는 것이다. 문자열을 앞에서부터 순회하면서, 시작점 후보를 정하고, 나머지 모든 문자 각각을 끝 점 후보로 설정할 때, 좌우대칭인지 여부를 판별해서 길이가 가장 긴 후보를 구하는 방법 ..
1. 라그랑주의 네 제곱수 정리 모든 자연수 n은 많아야 음이 아닌 4개의 정수의 제곱수 합으로 표현할 수 있다. $$n = a^{2} + b^{2} + c^{2} + d^{2}$$을 만족하는 0 이상의 정수 a,b,c,d가 존재한다. 증명은 매우 까다롭다.. 너무 길어서 따라하기도 힘들다.. https://jjycjnmath.tistory.com/295 [퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명 ※ 출처 - http://kevin0960.tistory.com/ 디오판토스의 저서 '산학'에는 '모든 양의 정수는 네 제곱수의 합으로 표현될 수 있다.' 라는 내용이 담겨 있다. 예를 들어, \[ \begin{aligned} 3 &= 1^2 + 1^2 + 1^2 + 0..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
