동적계획법8 백준 9465 - java 스티커(동적계획법) 1. 손으로 그려가며 가능한 조합이 어떻게 되는 지 확인 O X O X O X 또는 O X O X X O 뿐이라는 것을 확인 2. 앞의 결과가 뒤에도 영향을 미친다는 것을 인식 3. DP인 것을 어렴풋이 느낌 4. 점화식을 세워보았음 dp[0][n] = max(arr[0][n] + dp[1][n-1], arr[0][n] + dp[1][n-2]) dp[1][n] = max(arr[1][n] + dp[0][n-1], arr[1][n] + dp[0][n-2]) 5. 결국 답은 dp값을 구한 후 Max값을 출력하는 것임 6. 이 생각까지 다다르는 데 약 20분이 걸리고 코드 작성은 10분 가량 걸린 것으로 추정 해당 문제를 풀고 제출한 후 속도가 시간이 단순 System.out.println과 StringBui.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 28. 백준 24416 java - 피보나치 수1(동적계획법/DP) 백준 단계별로 풀기에서 동적계획법1이 all solve이었는데 갑자기 한 문제가 추가 되어서 풀게 된 문제이다. 브론즈 1이지만 DP의 효율성을 알 게 해주는 아주 귀중한 문제이다. 수도 코드가 이미 있어서 따라 치기만 해도 된다. package 동적계획법; import java.util.*; import java.io.*; public class Boj_24416_알고리즘수업_피보나치 { static int a, b, dp[]; public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n+1]; dp[1] = 1; dp[2] = 1.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 17. 백준 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. 백준 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. 백준 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. 이전 1 다음 728x90
