DP9 [백준 11660] 구간 합 구하기 5 / 자바 / 누적합 문제 레벨: 알고리즘: 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/116601 번째 시도 이 문제는 이차원배열의 누적합이다.알고 가야 할 것은 일차원 배열의 누적합과 배열에 담기는 값이 다른 거이다. 혹시 O 위치의 담길 값이 ---->를 다 더한 값이라고 생각할 수 있다. 그건 틀렸다. ----------->O우린 1,1,를 좌상 꼭지점으로 O을 우하 꼭지점으로 삼는 직각삼각형의 합으로 생각해야 한다.합을 화살표 표시하고 그림으로 나타내면 아래와 같다------ --->O 위 그림을 보면서 배열에 들어가는 값을 이해해보자.빨간색 위치에 배열값은 초록색 + 파란색 - 노란색(겹치는 부분)이다. 이 공식으로 배열을 채우면 된다. .. 2024. 6. 12. [백준 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. [백준 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. [백준] 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. [백준] 내리막길/자바 문제 레벨: G4알고리즘: DFS + DP 풀이시간: 40분 힌트 참조 유무: 유https://www.acmicpc.net/problem/15201 번째 시도 1. 먼저 (0,0) 위치에서 시작하므로 dp[0][0]값을 0으로 초기화한다.2. (0,0) 위치에서 상하좌우로 이동하면서 map[x][y] > map[nx][ny]인 위치에 대해서만 DFS 메소드를 재귀호출3. 재귀호출을 통해 (M-1, N-1)위치에 도달하는 경로의 개수를 찾는다.4. 이렇게 찾은 경로의 개수를 dp[0][0] 값에 더해준다.5. 모든 이동 가능한 위치에 대해 위 과정을 반복6. dp[0][0] 값이 결정되면 해당 값을 리턴한다.위와 같은 과정을 거쳐서 dp[0][0] 값을 찾게 된다. 만약 dp[0][0].. 2024. 5. 13. [백준] 1로 만들기/자바 문제 레벨: S4알고리즘: DP풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/14631 번째 시도 귀여운 수준의 구현이어서 바로 작성해보았다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()); int cnt = 0; .. 2024. 5. 9. 이전 1 다음
