요깨비's LAB

처음에는 2차원 배열에 맵을 담아서 방향 그래프를 따른 우선 순위큐 기반의 다익스트라를 구현하였습니다.(여기까지는 스스로 아이디어 생각해내서 하루종일 걸려서 구현까지 했지만... import java.util.*; public class Main { static int V,E; public static void main(String[] args ) { Scanner scr = new Scanner(System.in); final int INF = 10000; V = scr.nextInt(); E = scr.nextInt(); int startV = scr.nextInt(); int[][] map = new int[V+1][V+1]; int[] result = new int[V+1]; for(int i=1;i

1. 아이디어 1. 입력값을 받을 때마다 해당 번째 위치에서 1번째까지 반복하며 조를 만들면서 최적의 값을 비교하여 가장 좋은 값을 선택 (1)우선 dp[0] = 0, dp[1] = 0으로 초기화 해줍니다. 0번째와 1은 자기자신이기 때문에 값의 차이가 자기자신 - 자기자신 = 0 (2)dp[2]인 경우 [1] 자기자신 그루핑한 값 + 직전의 그루핑한 값 중 최적의 값 [2] 자기자신과 바로 직전값 1과 그루핑한 값 + 1의 직전의 그루핑한 값중 최적의 값 dp[3]인 경우 [1] 자기자신 그루핑한 값 + 2에서 그루핑한 값 중 최적의 값 [2] 자기자신과 바로 직전값 2와 그루핑한 값 + 1에서부터 그루핑한 값중 최적의 값 [3] 자기자신과 1번째 까지 그루핑한 값 + 0에서부터 그루핑한 값중 최적의 ..

문제 풀이 1. 다이나믹 프로그래밍을 적용할 수 있는 문제인지 확인 - 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹치는지? (Overlapping SubProblem) - 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. (Optimal Substructure) 2. 자료구조에(실무를 제외하고 일반적인 문제 해결과정에서는 보통 배열사용) 어떤 값을 저장할 것인지 문장으로 정리 - memoization[N] = "N개의 물건을 묶음 및 단일 조합을 통해 구매하여 지불할 수 있는 최대 금액" 3. memoization[N]의 값을 어떤 규칙을 통해 찾을 수 있는지 생각하기(점화식..

1. 개념 "하나의 문제는 한번만 풀도록 하는 알고리즘" - 핵심 다이나믹 프로그래밍은 문제의 답이 이용되는 구조를 이용한 알고리즘이다. 큰 문제를 작은 문제로 나눈다는 측면에서 분할정복(divide and conquer)알고리즘과 비슷하지만 다음과 같은 차이점이 존재한다. DAC DP 문제가 절반으로 줄어듬 문자게 -1로 줄어듬 Function problem 최적화 문제 결과가 한번 사용 결과가 여러번 사용됨 분할이 성능 향상 결과 재사용이 성능 향상 다이나믹 프로그래밍 알고리즘을 적용하기 위해서는 두가지 조건을 만족해야 한다.- 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹치는지? (Overlapping SubProblem) 문제를 작은..