본문 바로가기

Algorithm43

[Algorithm] 다익스트라 알고리즘(자바) 다익스트라 : 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘 특히, 다익스트라 알고리즘은 음수의 간선 가중치를 허용하지 않습니다. 한 정점에서 다른 정점으로 가는 최단 거리의 문제를 접한 경우 양의 가중치가 있으면 다익스트라 문제이다!!!! 다익스트라 과정 다음은 다익스트라 알고리즘을 통해 최단 경로를 구하는 과정입니다. 1. 초기 상태 저는 1번 정점부터 시작하겠습니다. 1 2 3 4 5 0 INF INF INF INF 1 2 3 4 5 0 4 INF INF INF distance[2] > distance[1] + 4입니다. 이는 distance[2] = distance[1] + adjMatrix[1][2]를 의미합니다. 1 2 3 4 5 0 4 INF 10 IN.. 2022. 10. 30.
[SWEA] 1952. [모의 SW 역량테스트] 수영장(자바/dfs) 출력 각 이용권의 요금과 각 달의 이용 계획이 입력으로 주어질 때, 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램 문제 해결 방법 1년의 경우 dfs를 탐색할 필요가 없으므로, dfs 탐색을 돌기 전에 1년 비용을 미리 세팅합니다. dfs 탐색은 달을 기준으로 탐색하게 되며, 1일, 1달, 3달을 기준으로 돌게 됩니다. 12월까지이므로 cnt가 13이 되었을 때가 기저 조건이 됩니다. 이때 최소 비용을 갱신하며 결과값을 도출하게 됩니다. //package swea.p1952; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja.. 2022. 10. 28.
[백준 BOJ] 14501 퇴사(DP/자바) 문제 접근 방법 1. DP 2. 현재 일 수 + 상담에서 걸리는 시간(Ti)가 N+1보다 크면 퇴사하므로 상담을 할 수 없습니다. 따라서, 이에 대한 경우 0으로 세팅했습니다. 3. 1일을 선택하면 4일이 되어야 4일-1일 >= 3일이 되므로 4일 최대 금액은 4일 금액 + 1일 금액이 됩니다. 점화식 - 현재 일수에서 나올 수 있는 최대 금액 = Math.max(현재 일 수 금액, 현재 전까지에서 나올 수 있는 일수 금액 중 최대); - dp[i] = Math.max(dp[i], dp[j] + prices[i]) public class Main { public static void main(String[] args) throws NumberFormatException, IOException { Buff.. 2022. 10. 19.
[백준 BOJ] 14916번 거스름돈 (자바/DP) 문제 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 접근 방법 1. DP 문제 2. 점화식 : dp[i] = Math.min(dp[i-2], dp[i-5) + 1 3. 초기화 dp[2] = 1(2원 짜리 하나를 사용하여 거슬러 줄 수 있으므로) dp[5] = 1(5원 짜리 하나를 사용하여 거슬러 줄 수 있으므로) dp[4] = 2(2원 짜리 2개로 거슬러 줄 수 있으므로) /* * boj 14916 거스름돈 * dp 문제 * */ public class Main_14916 { public static void main(String[] args) { Scanner.. 2022. 10. 18.

티스토리툴바