dp

문제링크https://www.acmicpc.net/problem/9461문제풀이dp[i] = dp[i - 1] + dp[i - 5]; 라는 점화식만 도출하면 쉽게 풀 수 있는 문제이다.( i 번째 삼각형의 한변의 길이 =  i-1번째 변의 길이 + i-5번째 변의 길이 ) let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");const testCaseCount = Number(input.shift());input = input.map((n) => Number(n));let dp = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]; // P(1) P(2) P(3) P(4) p(5..

문제https://www.acmicpc.net/problem/11727 풀이문제의 핵심은 다음과 같은 점화식을 구하는 것이다. dp[i] = dp[i-1] + dp[i-1]*2  dp[i] 는 2xI 직사각형의 타일을 채우는 방법이다.  해당 점화식만 도출하면 쉽게 풀 수 있다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim();let N = Number(input);let dp = Array(N + 1).fill(0);dp[1] = 1;dp[2] = 3;for (let i = 3; i

문제https://www.acmicpc.net/problem/1463 문제풀이dp로 접근하지 않으면 시간초과가 나는 문제였다. 문제풀이의 핵심은 아래 점화식이다. 여기서 dp[i] 는 i를 만들기 위해서 필요한 연산 횟수이다. ( dp[1]=0, dp[2]=1, dp[3]=1 이다 )   1 ) i가 3의배수이고 2의 배수일 때dp[i] = Math. ( dp[i/3] +1 , dp[i/2] +1 , dp[i-1] +1 )    2 ) i가 3의 배수이고 2의 배수가 아닐때dp[i] = Math. ( dp[i/3] +1 , dp[i-1] +1 )    3 ) i가 2의 배수이고 3의 배수가 아닐때dp[i] = Math. ( dp[i/2] +1 , dp[i-1] +1 )     let fs = requir..

문제https://www.acmicpc.net/problem/12865 풀이let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [N, K] = input[0].split(" ").map((num) => Number(num));let arr = [];for (let i = 1; i Number(num)));}let dp = Array.from({ length: N + 1 }, () => { return Array(K + 1).fill(0);});for (let row = 1; row = weight) { dp[row][col] = Math.max(dp[ro..

문제https://www.acmicpc.net/problem/9251내풀이LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.이 문제는 유명한 문제라고 하는데 처음에 어떻게 접근할 지 몰라 다른사람들의 풀이를 참고하였다.간단하게 ACAYKPCAPCAK두문자의 LCS를 찾으려면 아래와 같은 2 차원 배열을 만들고 채워서 가장 큰 수를 확인하면 된다.       A  C  A  Y  K  P     C   A   P   C   A  K    이렇게 2차원 배열을 만들고 채우면 된다. 위 2차원배열을 dp라고 칭하면 dp[0][3] 은 문자열 C와 문자열 ACAY 의 LCS길이로 채워진다...

문제https://www.acmicpc.net/problem/9095 풀이dp로 푼 문제풀이이다. 이 풀이가 최적화된 풀이이고 밑에 보면 dfs로도 푼 문제가 있다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");input = input.map((n) => Number(n));for (let i = 1; i   처음에 dfs로 접근했는데 그럴 필요가 없었다. 참고차 남겨둔다. let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");input = input.map((n) ..

문제https://www.acmicpc.net/problem/1916 풀이처음에 dfs로 접근해서 풀었는데 시간초과로 틀려서 dp를 이용했다. 일단 map이라는 2차원 배열을 구현한다. 이 2차원 배열의 map[ i ][ j ] 는 i도시에서 j 도시로 갈 시 가장 가격이 싼 버스 요금을 나타 낸다. 만약 map[ i ][ j ] = Infinity 이면 해당 루트는 버스가 다니지 않는다고 생각하면 된다.  그리고 dp라는 2차원 배열을 구현한다. dp[ i ][ j ] 는 i 도시에서 j 도시로 가는 루트는 가장 버스요금이 싼 루트의 요금을 나타낸다.우리는 모든 경로를 탐색하면서 2차원 배열 dp를 완성시키고 최종적으로 dp[출발점][도착점] => 최소비용 을 구하면 된다.  const fs = req..

문제링크https://www.acmicpc.net/problem/11660 문제풀이이 문제는 언뜻보면 쉬어보인다. 하지만 단순하게 풀면 연산횟수가 너무 많아 시간초과가 난다. 연산횟수를 확인히 줄이기 위해 dp(동적계획법-dynamic programming)를 이용해야 한다. dp를 생각하는 순간 문제는 쉬어진다.let fs = require("fs");let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let [tableInfo, ...arr] = input;let [N, M] = tableInfo.split(" ").map((num) => Number(num));let table = [];for (let i = 0; i N..

🔥문제링크https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🔥첫번째 풀이 ( 테스트 케이스 모두 통과 but 시간초과 )처음에 내가 작성한 코드이다. ( 하단 참조 ) 이 코드는 테스트 케이스는 모두 통과지만 시간초과 테스트에서 모두 시간초과가 나왔다😭 다른사람들의 코드를 참고해보니 재귀가 아닌 dp ( dynamic programming : 최적화 ) 문제였던 것 같다.function solution(n, money) { let answ..

🔥문제링크https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  🔥풀이프로그래머스 홈페이지 코딩테스트 문제목록 위에 보면 AI 가 나를 분석해 추천해주는 문제가 있어서 그 문제를 풀어보았다. 알고리즘의 카테고리는 동적계획법으로 분류 되어 있었는데 정확히 동적계획법이 뭔지 궁금해서 찾아보니 ... 이렇다고 한다. 계산화 최적화라고 생각하면 될 것같고 dynamic programming (DP) 이라고 한다자 이제 진짜 풀이이다. function sol..