DP15

• [DP]백준 9095 1, 2, 3 더하기 & 15988 1, 2, 3 더하기 3 package DP; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class boj_15988_123더하기3 { private static int testcaseNumber, dp[], testcaseArr[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); testcaseNumber = Integer.parseInt(br.readLine()); test.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 1.

• [DP]백준 14501 퇴사, 15486 퇴사 2 package DP; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; public class boj_14501_퇴사 { // 1. 뒤에서 부터 For문을 돌기 // 2. 해당 배열 순서 + 경과 기간 >= N 이면 넘기기 // 3. 합의 최댓값 으로 갱신 해두기 static class Consult { int time; int profit; Consult(int time, int profit) { this.time = time; this.profit = profit; } } public static void main(Str.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 12. 1.

• 

  백준 1520 java - 내리막길(DP, 동적계획법) 해당 문제는 자력으로 푼 건 아니고 다른 분의 풀이를 참고하여 푼 것이다. 왜 Queue를 사용한 bfs는 안되는 걸까 생각하다가 힙을 쓰면 된다고 생각하니 풀렸다. 정석으로는 탑다운 방식의 DP였다. 1. 내리막길의 개념은 현재 방문한 곳의 높이(값) 보다 다음에 방문할 곳의 값이 더 낮은 경우이다. 2. BFS+DP또는 DFS+DP로 풀면 된다. 3. 두 가지 접근법이 있는데 0,0(시작점-바텀업) 부터 아래로 쌓거나, M-1, N-1(도착점-탑다운)부터 쌓으면 된다. 4. 해당 문제는 dp다 보니까 탑다운, 바텀업 전부 되지만 나는 바텀업(0,0 부터 쌓기)방식으로 풀었다. 5. PriorityQueue를 쓰지 않으면 주변 내리막길이란 내리막길은 다 가기 때문에내리막길 다음의 그다음 제일 큰 내리막.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 23.

• 

  백준 11049 java - 행렬 곱셈 순서(DP/동적계획법) 해당 문제는 거진 3일? 4일? 생각했다가 파일합치기를 응용하면 된다는 것은 알지만 점화식이 도출안돼서 답답해하다가 범죄도시 2 영화 보고 카페와서 깨닫고 풀 수 있게 된 문제이다. 파일합치기에서 응용이므로 참고하면 좋을 것 같다. 2022.05.08 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11066 java - 파일합치기(DP) 백준 11066 java - 파일합치기(DP) 해당 문제의 경우 1주일 정도 붙잡고 있다가 결국 구선생님의 도움으로 풀게 된 문제이다. 아이디어 자체는 생각할 수 있었는데 그게 맞는 건지, 구현을 어떻게 해야하는 지 감이 오질 않았다. dp chaaany.tistory.com 1. 두 개의 파일을 합칠 때 필요한 비용 = .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 22.

• 

  백준 11066 java - 파일합치기(DP) 해당 문제의 경우 1주일 정도 붙잡고 있다가 결국 구선생님의 도움으로 풀게 된 문제이다. 아이디어 자체는 생각할 수 있었는데 그게 맞는 건지, 구현을 어떻게 해야하는 지 감이 오질 않았다. dp의 세계는 정말 무궁무진한 것 같다. 1. 두 개의 파일을 합칠 때 필요한 비용 = 두 파일 크기의 합 2. 최종파일 만드는 데 합치는 횟수 = 총 파일 -1 3. 서로 인접한 파일들끼리만 합칠 수 있음 4. 테스트케이스 관찰 결과 C1 + C2 / C1 + C2 + C3 / C1 + C2 + C3 + C4 = 3*C1 + 3*C2 + 2*C3 + C4 = 9 / 3 3 2 1 C1 + C2 / C3 + C4 / C1 + C2 + C3 + C4 = 2*(C1 + C2 + C3 + C4) = 8 = 2 2 2 2 C.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 8.

• 

  백준 12865 - 평범한 배낭 JAVA 해당 문제는 DP의 대표적인 냅색(Knapsack-짐싸기)문제라고 한다. 하지만 본인은 1주일 동안 손을 대지 못하고 있었다. 왜냐하면 무게 W에 대해 중복된 가치를 가질 수 있는가에 대한 의문이 들었기 때문이다. 하지만 그건 기우였다. 중복된 가치가 되든 말든 상관이 없었다..! 드디어 동적 계획법 1까지 단계별로 풀기를 싹 밀었다! 하지만 5개월~6개월 전부터 시작해서 앞부분에 힘겹게 풀었던 것을 또 다시 풀라고 하면 풀 수 있을지는 의문이다. 내 머릿속의 지우개ㅜㅜ 이상한 소리 하지 않고 바로 문제 풀이/접근과정과 소스코드 공유하겠슴다. 1. 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 12.

• 

  백준 1912 - 연속합 JAVA 해당 문제는 손으로 끄적여가면서 풀다가 탁 깨달은 시점에서 술술 풀어나간 문제이다. 생각보다 매우 간단한 로직이지만 그동안 풀었던 문제들 + 단계별로 풀기 끝에 있다는 것을 감안해서 스스로 어려운 문제일 것이다라고 되뇌다가 시간이 오래 걸린 문제이다. -> "생각보다 쉬웠다"라는 뜻 1. n개의 정수, 1 1 + 2 가 최대고 -1,000일 때는 굳이 안 더해주는 게 나을지도? 3. 그렇다면 합한 수가 0보다 낮아지지 않는 시점까지는 연속합(누적합)을 해주다가 0보다 낮은 경우에는 그냥 연속합(누적합)에 넣는 것을 포기하고 다시 0보다 큰 수가 나오는 시점부터 합해주면 좋을 듯 하다. 4. 동시에 max값은 유지하면서 n번 째까지 다 돌았을 때의 max값이 답일 것이다. 일반적으로 입력을 받을 때 로직을.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 3.

• 

  백준 2565 - 전깃줄 JAVA 해당 문제를 처음 접했을 때는 점화식을 구하기 보다 구현으로 해결하려고 했었다. 그래서 아래와 같이 Comparator를 두 번이나 오버라이딩 해서 썼다. 하지만,,, 결과는 9퍼에서 틀림! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { // 전깃줄 .. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 1.

• 

  백준 11054 - 가장 긴 바이토닉 부분 수열 - JAVA 바로 직전에 풀었던 백준 11053 문제의 응용편이다. 11053 풀땐 3시간이 걸렸지만 바로 응용해서 푸니 10분? 20분만에 푼 것 같다. 어쩐지 정답률이 높더라... 2022.03.31 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11053 - 가장 긴 증가하는 부분 수열 JAV 백준 11053 - 가장 긴 증가하는 부분 수열 JAV 쉬운 것 같아서 점화식 짜고 대충 구현해서 풀다가 3시간 만에 풀었던 DP문제다. 매 순간 긴장을 놓치면 안 된다는 것! 자만하면 안 된다는 것을 다시 한번 일깨워준 문제...! 시간 복잡도 계산 정 chaaany.tistory.com 1. 1부터 n까지는 오름차순인 증가하는 최장 수열 길이 찾아서 dp[n][0]에 할.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 31.

• 

  백준 11053 - 가장 긴 증가하는 부분 수열 JAV 쉬운 것 같아서 점화식 짜고 대충 구현해서 풀다가 3시간 만에 풀었던 DP문제다. 매 순간 긴장을 놓치면 안 된다는 것! 자만하면 안 된다는 것을 다시 한번 일깨워준 문제...! 시간 복잡도 계산 정확하게 안 하고 점화식은 몇 분만에 구하고 시간 복잡도 터질까봐 배제했던 코드가 답이었다!.. ㅜㅜ 2차원 배열 선언하고 Comparator 재정의해서 정렬하고... 별짓을 다했다 1. 1 n번쨰 까지의 최장 길이 수열 = n번째 수 > n-1 일 경우 n번째 수를 넣은 수열 or // 10 20 10 30 20 50 // O O X O X O // 8 6 9 1 4 6 7 4 3 7 4 7 2 5 2 10 1 // 1 1 2 1 2 3 4 2 2 4 3 4 2 4 2 5 1 // 8 // O // 8 6 /.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 31.

• 

  백준 2156 - 포도주 시식 JAVA 처음에 딱 보고??? 이거 계단 오르기 아닌가? 라고 생각 했지만 역시나 아니었다. 이유는 문제 풀이 과정에서! 1. 포도주 잔 선택 시 무조건 다 마셔야 함 2. 3잔 연속으로 놓여 있는 잔을 마실 순 없음 -> 연속 +1, +1은 불가 3. 1 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 29.

• 

  백준 10844 - 쉬운 계단 수 JAVA 해당 문제는 실버 1이었지만 단계별로 풀이 문제 중에 실버2, 3문제랑 비교해봤을 때 상대적으로 쉬웠던 문제로 보인다. 티어는 그저 거들뿐 .. !! 아닌가? DP + Padding + 모듈러연산을 사용한 것이니 응용버전인 것으로 보이긴 한다... 잡담은 그만하고 DP + Padding(딱 맞는 크기의 배열을 선언하기 보다 적절히 빈 배열을 만들어서 활용하는 기법)+ 모듈러 연산을 통해서 문제를 풀었다. 문제 푸는데 소요시간 : 대략 50분 문제 접근/풀이 과정 1. 계단 수란 인접한 모든 자리의 차이가 1인 경우 2. n번 째 m으로 시작하는 수의 경우의 수 = n-1번째 m-1로 시작하는 수의 경우의 수 or n-1번째 m+1로 시작하는 수의 경우의 수 3. 추가적으로 고려해야할 부분 = 맨 앞의 수.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 28.