DP

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; class Solution { public int solution(int n, int[][] results) { int answer = 0; int[][] graph = new int[n + 1][n + 1]; // 인접 행렬 // 이기는 경우의 수 입력 for(int i = ..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import java.util.*; class Solution { static final int mod = 1_000_000_007; public int solution(int n) { int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; if(n

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import java.util.*; class Solution { static final int mod = 1_000_000_007; public int solution(int m, int n, int[][] puddles) { int[][] dp = new int[n + 1][m + 1]; // dp 배열 초기화 dp[1][1] = 1; for(int[] puddle ..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.*; class Solution { static int MAX = 987654321; public int solution(int x, int y, int n) { int answer = 0; int[] dp = new int[y + 1]; Arrays.fill(dp, MAX); // 충분히 큰 값으로 초기화 dp[x] = 0; for(..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.*; class Solution { public int solution(int[][] triangle) { int[][] dp = new int[501][501]; dp[0][0] = triangle[0][0]; int max = 0; // 끝자리에 위치한 칸들 처리 for(int i = 1 ; i

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 해결 아이디어 1) 최장 공통 부분 수열 LCS (DP) • 최소 편집 거리로 두 문자열 같게 만들기 = A에서 삭제를 진행해 A와 B의 LCS를 만들고, 삽입을 진행해 B를 만드는 것 - dp[i][j] : 문자열 A의 i번째까지와 문자열 B의 j번째까지를 활용해 만들 수 있는 LCS 길이 • 삭제 횟수 = A 길이 - LCS 길이 • 삽입 횟수 = B 길이 - LCS 길이 ➡ 정답 = 삭제 횟수 + 삽입 횟수 2) 최소 편집 거리 String Matching (DP) 활용 ✅ - dp[i..

🧩 필요한 최소 동전의 수 (은행) ⇨ i : 지금까지 선택한 동전의 합 ⇨ dp[i] : 필요한 최소 동전 수 🧩 배낭 문제 (Knapsack) dp[ i ][ j ] : 가능한 보석 가치의 최대값 • i번째 보석까지 고려했고, 지금까지 선택한 보석 무게의 합은 j ⇨ i번째 보석을 가방에 넣었는지 / 넣지 않았는지 구분해 점화식

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLi..

🔺 문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine(..