자바127 [백준 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. [백준 1339번] 단어 수학 / 자바 / 그리디 ** 문제 레벨: G4알고리즘: 그리디풀이시간: 50분힌트 참조 유무: 유(아이디어 참조)https://www.acmicpc.net/problem/1339 1 번째 시도 [알고리즘 선택 과정]입력 제한을 보니 DFS도 가능하다.그러나 Greedy문제이기 때문에 Greedy로 풀어보겠다. [Greedy란?]탐욕적 알고리즘이라고도 불린다.현재의 단계에서 최적을 선택해 마지막의 최적의 정답을 도출한다는 아이디어이다.근시안적으로 현재만 보고 선택하는 것이 탐욕적 알고리즘이라고 불리는 게 어울린다. [Greedy 과정]알파벳이 주어진 순대로 탐색할 것이다. 납득이 가는 과정일 것이다. 그렇다면 어떨 때 알파벳의 숫자를 바꿔줘야 할까?새로운 알파벳이 해당 숫자의 알파벳보다 자릿수가 높을 때 숫자를 바.. 2024. 6. 3. [백준] 수 찾기 / 자바 문제 레벨: S4알고리즘: 이분 탐색풀이시간: 10:29힌트 참조 유무:https://www.acmicpc.net/problem/19201 번째 시도 import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.Arrays;import java.util.StringTokenizer; public class Main { public static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp.. 2024. 6. 2. [백준] 숫자 찾기 / 자바 문제 레벨: 알고리즘: 이분탐색풀이시간: 40분힌트 참조 유무: 유https://www.acmicpc.net/problem/10816 1 번째 시도 [upper-bound, lower-bound 차이]lower bound, 즉 하한은 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 의미한다. upper bound, 즉 상한은 찾고자 하는 값을 초과한 값을 처음 만나는 위치다. 중복 원소에 대한 길이 = (상한 - 하한) mport java.util.Arrays;import java.util.StringTokenizer;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;.. 2024. 6. 1. 이전 1 ··· 8 9 10 11 12 13 14 15 다음
