요깨비'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에서부터 그루핑한 값중 최적의 ..

저의 DFS로 풀려는 아이디어로는 시간 초과와 1000 이상의 값에서는 절대 돌아가지 않을 것 같다는 판단에 다른 분들의 아이디어를 보고 이해한 후에 배껴서 풀었습니다. 아이디어 잘 생각 하시는 분들 보면 정말 부럽... 하지만 재능이 나무에서 뚝 떨어지신 분들도 많겠지만 저에게는 그러한 재능이 없기에.. 꾸준히 높이 뛰기해서 쟁취해야겠죠 잡설이 길었습니다. 조건 두 개를 주었습니다. 표의 가로나 세로 크기가 1일 경우 => 이 경우, 정사각형의 원리에 의해 1인 값이 하나라도 있으면 넓이는 1일 수 밖에 없습니다. 모두 0 이면 당연히 0을 출력하겠죠 가로 세로 모두 2 이상일 경우, 1,1에서 부터 시작한다. => 정사각형의 한변의 크기를 구하는 원리에 의해 출처: https://blog.sonim1..

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