hansjour 개발일지

문제 파악-주어진 k부터 n까지 최소 거리를 구하는 문제-다익스트라 함수 구현하기-가중치 = 시간접근 방법-Edge, Entry 클래스로 구조체형태 만들기-우선순위 큐를 활용해 거리가 짧은 노드들부터 순회-큐에 들어간 원소를 전부 비워낼 때까지 while문 돌며 distance가 최소거리인지 체크-(+) 그와 연결 된 노드들과의 거리도 최소거리인지 체크-절대적인 최솟값 거리를 저장하는 distances 배열 통째로 리턴⇒ 왜? 특정 노드 n까지의 최소거리가 아니라, 모든 노드를 순회할 때의 최솟값이기 때문.(순서가 있는 그래프가 아니므로 n까지 != 최댓값임)-리턴받은 최솟값 모음 배열을 돌며 가장 그 중 가장 오래 걸린 시간을 찾는다.(max)코드 구현import java.util.*;class Sol..

문제 파악-dp활용  제한 사항1 1 0 접근 방법-0~n까지 현재 금액 누적해가기(for문)-금액 도달 전까지 누적해가며 dp 수행, 수행하면서 대상 값을 업데이트해가며 돌려줌(amount-coin)-완전탐색으로도 구현이 가능하나 효율성에서 문제 발생!!-메모이제이션 활용) n번째 계단처럼, n번째 값까지의 최소값을 하나하나 메모해두고계산하지 않은 것만 dp수행, 이미 계산된 것은 배열 안에서 골라서 result값 갱신하기코드 구현import java.util.*;class Solution { public int solution(int[] coins, int amount) { int[] memory = new int[amount+1]; Arrays.fill(memory,I..

문제 파악-dp를 이용해 구현한다.Constraints:2 0 접근 방법-bottom-up 방식으로 구현한다.-n(cost.length) 계단까지 최소비용을 구하기 위해 최소비용 배열 선언하여 메모하기-마지막 계단에 해당하는 최소 비용 리턴코드 구현import java.util.*;class Solution { public int minCostClimbingStairs(int[] cost) { //memoization initialization int[] dp = new int[cost.length+1]; for(int i=2;i배우게 된 점처음에 첫 계단 혹은 둘째 계단에서 시작할 수 있으므로 둘 다 비용 계산 의미 없음고로 2번째 계단에서부터 ..