알고리즘/DP10 [백준 2133] 타일 채우기 / 자바 / dp 문제 레벨: G4알고리즘: dp(업데이트 기준x + 일차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/21331 번째 시도 확실히 dp는 고급 알고리즘이다. 이 만큼 내 머리를 아프게 하는 알고리즘은 없다. 전에도 말했지만 dp의 시작은 점화식을 세우는 것이고점화식을 세우는 것은 직접 예시를 구해보는 것이다. 그리고 그 사이에 관계를 찾아내는 것이다.이문제는 너비가 4이후부터 특수모양의 경우의 수가 2개 생긴다는 것을 기억해야 한다.아래 링크에서 그림을 참고해봐라.찾아본 것 중 가장 이해가 쉽게 될 그림이다.https://january-diary.tistory.com/entry/BOJ-2133-%ED%83%80%EC%9D%BC-%.. 2024. 6. 11. [백준 2225] 합분해 / 자바 / dp ** 문제 레벨: G5알고리즘: dp(업데이트 기준 2개 + 이차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/22251 번째 시도 [의문점]1. 바로 숫자 N까지 가졌을 때를 구하면 되지 않나? ....N-2,N-1,N 차례차례 누적합으로 구해야 하나? arr[N-1]가 arr[N] 만드는데 영향을 미치나? 2. 바로 K일 때를 구하면 되지 않나? ....K-2, K-1,K 차례차례 누적합으로 구해야 하나? 예를 들어 생각해보자 N = 3 K =3 K가 0인 상황을 먼저 구해보자면arr[0] = 0arr[1] = 0 arr[2] = 0 arr[3] = 0K가 1인 상황을 먼저 구해보자면 arr[0] = 1 {0} arr[1] = .. 2024. 6. 10. [백준 2294] 동전2 / 자바 / dp 문제 레벨: G5알고리즘: dp(업데이트 기준 1 개)풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/22941 번째 시도 동전1과는 다르게 dp배열에 만들 수 있는 가지수가 들어가는 것이 아닌 최소한의 동전 개수가 들어가야 한다.동전1과 마찬가지로 업데이트 기준은 1가지이다. dp는 점화식을 세우는 것이 시작이자 제일 중요하다 arr[j] = Math.min(arr[j], arr[j - coin[i]] + 1);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Mai.. 2024. 6. 9. [백준 11054] 가장 긴 바이토닉 부분 수열 / 자바 /dp 문제 레벨: G5알고리즘: DP풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/110541 번째 시도 위 문제는 LIS와 LDS 합친 문제이다.참고로 LDS는 LIS를 거꾸로 구현하면 된다.[1. LIS 구하는 법: O(N^2)]dp배열에는 LIS 순서가 담긴다.dp[i]를 구할 때마다 i-1까지 탐색한다.// N은 배열의 크기for (int i = 0; i [2. LIS 구하는 법: O(NlogN)]dp배열에는 LIS 원소가 담긴다.아이디어 컨셉: 숫자마다 간격이 좁을 수록 가장 긴 LIS이다.원본 배열을 탐색할 때마다 이분 탐색(O(logN))을 해야한다. 그래서 O(NlogN)이다int len=0; int idx=0; for(int i=0;.. 2024. 6. 8. [백준 12865] 평범한 배낭/자바/dp ** 문제 레벨: G5알고리즘: DP ( dp 업데이트 기준 2개 + 이차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/128651 번째 시도 시작에 앞서, 이 알고리즘을 이해하기 힘들 것임을 미리 말한다. 배열에 들어가는 것이 행과 열이 일치하는 값이 아니라 기존까지 구했던 것 중에서 최적의 답, 최대값(누적값)이 들어감을 알아야 한다.이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다. 배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 .. 2024. 6. 6. [백준 2293] 동전1 / 자바 / dp 문제 레벨: G4알고리즘: dp ( dp 업데이트 기준 1개 + 일차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/22931 번째 시도 [잘못된 알고리즘]이문제는 dp문제이다. 왜 dp일까?1원일 때 경우의 수 dp =[1] 2원일 때 경우의 수 = {1,1}(1을 만들 수 있는 경우의 수 x 1을 만들 수 있는 경우의 수) {2,0}(2를 한 번에 만 들 수 있는 경우 수) .. 2024. 6. 5. [프로그래머스 LV3] 연속 펄스 부분 수열의 합 / 자바 / DP 문제 레벨: LV3알고리즘: DP(쉬운버전 / cause: 1차원배열 사용)풀이시간: 1시간힌트 참조 유무: 유https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1 번째 시도 [문제 설명](1) 2 3 -6 1 3 -1 2 4 전체 연속배열 x -1 1 -1 1 -1 1 -1 1 펄스배열----------------------------- -2 3 6 1 -3 -1 -.. 2024. 6. 4. [백준] LCS/자바 문제 레벨: G4알고리즘: DP풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/92511 번째 시도 import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str1 = br.readLine().toCharArray(); char[] str2 .. 2024. 5. 20. [백준] ACM Craft/자바 문제 레벨: G3알고리즘: 위상정렬 + DP 풀이시간: 2시간힌트 참조 유무: 유https://www.acmicpc.net/problem/10051 번째 시도 입력을 받을 때마다 해당번호의 짓는 시간을 업데이트를 해줬다.결과는 실패이유는 입력 순서가 차례대로일거라고 가정했기 때문이다.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.. 2024. 5. 16. 이전 1 2 다음
