개발 무지렁이

동전1 🪅. dp에서 '메모이제이션'을 할 때, M[k]를 구하려면 M[1]부터 구해야한다. (1 지금 구하려는 값이 이전의 기록과 비교해서 어떤 점이 달라졌는지에 초점을 맞춘다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class B2293_동전1 { static int n; static int k; static int[] coins; static int cnt; static int[] M; public static int dp(int r, int ..

🪅. 문제를 보고 DP를 생각하고, 구현할 수 있느냐 => 답을 구하는 과정을 일반화할 수 있느냐, 예외를 if문으로 처리할 수 있느냐 🪅. 문제를 보는 시각을, 윗줄 데이터가 아랫줄 데이터를 선택하는 것이 아닌, 아랫줄 데이터가 윗줄 데이터 중 큰데이터를 선택하는 시각으로 볼 수 있느냐 🪅. 역순으로 정렬하기 위해, int[]를 Integer[]로 변환할 수 있느냐 정수 삼각형 [시간초과로 통과 못한 코드.java] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.S..

계단 오르기 🪅. dp(동적 프로그래밍)을 구현할 줄 아느냐 => '메모이제이션**' 🪅. 문제의 조건에 맞는 정확한 '점화식'을 세울 수 있느냐 => 1일때부터 조건에 맞는 답을 구해본다. 🪅. 점화식을 만들기 위해 1부터 몇 개까지 값에 대한 정의를 해야하는지 알 수 있는가? => 몇개부터가 이전의 기록으로 해결할 수 있는가를 본다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class B2579_계단오르기 { static int N; static int[] steps; static int[] ..

동적계획법(Dynamic Programming)의 전제와 정의 ⚠️ 큰문제를 동일한 형태의 작은문제로 나눌 수 있어야 한다. ⚠️ 작은문제에서 구한 값이 그것을 포함하는 큰문제에서도 동일하다. . 하나의 문제는 단 한번만 풀도록 하는 알고리즘을 말한다. 그러기 위해서 이미 구한 답을 잠시 기록해두는 과정을 '메모이제이션'이라고 한다. 🕑 시간복잡도: O(N) 동적계획법(Dynamic Programming)과 피보나치 수열 ❓ 피보나치 수열이란 : 모든 항이 바로 앞 두 항의 합인 수열을 말한다. (단, 첫번째항과 두번째항은 1 이다) import java.util.*; class Main { static int[] A = new int[100]; public static void main(String[]..