동적 계획법 백준 1,2,3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 동적 계획법 DP 를 떠올리며 문제를 풀기는 쉽지 않다. import java.util.Scanner; public class 백준1_2_3더하기 { /* ex ) 3 4 7 10 */ static int[] dp = new int[11]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); dp[1] = 1; dp[2] = 2; //..
👌 동적 계획법. 핵심은 top down / bottom up 방식에서 중복되는 연산을 피하는 것. -> O(2^n)의 시간복잡도를 가지게 될 경우 ( 재귀 함수 ) -> 연산의 횟수가 늘어난다. -> 콜 스택이 많이 늘어나므로 성능이 안좋아진다. 성능뿐만이 아닌 한계점까지 갈 경우 에러도 발생한다. 이미 연산을 한 과정을 다시 연산하는 부분이 생겨난다. 😔 피보나치 수열로 예시를 많이 든다. public class pbnc { public static void main(String[] args) { int n = 10; } // 반복되는 연산을 고려하지 않음. static int ffibo1( int x ) { if (x == 1 || x== 2) { return 1; } return ffibo1(x-..
import java.util.*; public class Lis { public static void main(String[] args) { // Scanner sc = new Scanner(System.in); // int size = Integer.parseInt(sc.nextLine()); // String arrays = sc.nextLine(); // String[] ttee = arrays.split(" "); // int[] target = Arrays.stream(ttee).mapToInt(Integer::parseInt).toArray(); int size = 6; int[] target = {10,20,10,30,20,50}; int sol = 0; int[] dp = new int[..
