뚜비두밥 삽질 저장소

안녕하세요. 훈스입니다. 이번에 푼 문제는 백준 알고리즘 1759 문제 '완전탐색' 문제입니다. https://www.acmicpc.net/problem/1759 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 package psh_1759; import java.util.Arrays; import java.util.Scanner; /* * 문제 : https://www.acmicpc.net/problem/1759 * ..

안녕하세요. 훈스입니다. 이번에 푼 문제는 백준 알고리즘 11057번 문제 다이나믹 문제입니다. https://www.acmicpc.net/problem/11057 dp 문제이기 때문에 d[][] 2차원 배열의 앞부분은 입력으로 들어올 n의 최대 값인 1000까지 잡았습니다. 그 다음 뒷부분에 올 수 있는 값은 0~9까지의 숫자인 10으로 잡았습니다. 이번 문제를 해결하는 키워드는 d[i][j]에서 j에 오는 값 즉 수열의 i번쨰 자리에 j의 값이 무엇인지에 따라서 그 전 값인 i-1의 값을 찾을 수 있습니다. 예를 들어 수열의 3번째 자리에 5가 왔다면 오름차순을 유지하기 위해서는 2번쨰 자리는 5이하의 숫자가 와야합니다. 따라서 1번째 자리에 올 수 있는 값에 따라서(0~9) 다음자리에 올 수 있는 ..

안녕하세요. 훈스입니다.이번에 푼 문제는 백준 알고리즘 9095번 문제 다이나믹 문제입니다. 다이나믹이란 동적계획법이라고도 불리는 알고리즘중에 하나인데요. 어떤문제가 반복저이고 최적 하위 구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법입니다...너무 어렵네요. 쉽게 설명하면 다들 아시는(?) 피보나치 수열 문제가 바로 다이나믹 프로그래밍에 아주 자주 등장하는 예시 입니다. 그럼 본론으로 들어가서 9095번 문제는 바로 이런 다이나믹 프로그래밍을 통해서 풀 수 있는 문제인데요 출처 : https://www.acmicpc.net/problem/9095 우선 처음 접근했던 방법은 위의 정의에서 나온것처럼 하위 구조에 있는 부분 답을 기반으로 전체 문제를 푸는 방식으..