CS/알고리즘

문제 https://www.acmicpc.net/problem/15988 풀이 n의 경우의 수를 구하기 위해 n보다 작은 값들의 경우를 저장해놓고 n의 경우의 수를 구할 수 있다. -> dp 문제 1. 반복되는 패턴에서 점화식을 세운다. 2. 점화식을 구현 5까지 경우의 수를 나열해보면 반복되는 패턴을 찾았고 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 점화식을 찾을 수 있다. const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n').map(Number); const T = input.shift(); const dp = new Array(T+1); dp[1] = 1; dp[2] = 2; dp[..

문제 링크 풀이 dp 유형에 어려움을 겪고 있었는데 처음으로 한번에 맞춘 문제이다. n개의 정수로 이루어진 임의의 수열이 주어지고 한 개 이상 연속된 수를 선택해서 구할 수 있는 최대합을 구해야한다. 다음 임의의 수열이 주어졌다고 하자. sequence = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1] 해당 수열에서 가장 큰 합은 12 + 21 2개를 선택한 합 33이 최대합이다. 떠올린 풀이과정은 핵심 아이디어는 sequence 배열의 각 인덱스마다 최대합을 구하고 마지막에 가장 큰 인덱스 값을 뽑아 내는 것이다. 각 인덱스마다 최대합을 구하여 저장 해놓고 다음 인덱스에서 최대합을 구할 때 활용해야한다. -> dp 활용 dp라는 배열을 만들어 sequence 각 인덱스의 최대합을 ..

문제 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다. 중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다. 떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다. JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자. 풀이 재귀함수를 이용한다. 코드 const input = require('fs').readFileSync('/dev/stdin'); const num = +input; ..

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 풀이 Fn = Fn-1 + Fn-2 피보나치 공식을 이용한다. 코드 (node.js) const input = require('fs').readFileSync('/dev/stdin'); function fibonacci(n..