https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 - bottom-up 방식으로 품 // SUCCESS const input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); const n = Number(input[0]); const dp = new Array(n+1).fill(0); for(let i = 2; i

동적 프로그래밍 (DP, Dynamic Programming) - 통산적으로 메모리를 더 사용하여 시간 복잡도 개선할 때 많이 사용됨 - DP로 문제를 해결하기 위해 '점화식'을 찾는 것이 핵심 과정 동적 프로그래밍은 아래의 두 조건을 만족할 때 사용가능하다 1. 최적 부분 구조(optimal substructure) 큰 문제를 유사한 형태의 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다. 2. 반복되는 부분 문제(overlapping sub-problem) 동일한 작은 문제를 반복적으로 해결해야 한다. 점화식 - 인접한 항으로 현재 값을 결정하는 관계식을 의미함 - 점화식은 "재귀 함수"로 표현가능 예) 파보나치 수열 점화식 An = (An-1) + (An-2) (이때 초기값..