조금씩 앞으로

최단 경로 알고리즘에는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드 와샬 알고리즘이 있다. 다익스트라 알고리즘(Dijkstra's algorithm) 그래프의 어떤 정점 하나를 시작점으로 선택 -> 나머지 정점들로의 최단경로를 모두 구한다. 정점 개수 V, 간선 개수 E일 때 시간 복잡도: O(ElogV) weight(cost)의 값은 항상 0 이상이어야 한다. 만약 0 미만인 경우 벨만-포드 알고리즘을 사용하면 된다. 참고: https://m.blog.naver.com/kks227/220796029558 벨만-포드 알고리즘(Bellman-Ford Algorithm) 그래프의 어떤 정점 하나를 시작점으로 선택 -> 나머지 정점들로의 최단경로를 모두 구한다. 정점 개수 V, 간선 개수 E일 때 시간..

떠오르는 풀이대로 손코딩을 했다. 아래 코드는 그 코드를 컴퓨터로 옮겨적은 것이다. import java.util.*; class Solution { private class Min { int number; int idx; public Min(int number, int idx) { this.number = number; this.idx = idx; } } public String solution(String number, int k) { String answer = ""; List list = new ArrayList(); for (int i = 0; i < number.length(); i++) { list.add(number.charAt(i) - '0'); } int cnt = k; int idx ..

이 문제는 전형적인 DP 문제이다. 문제를 푸는 팁은 포도주는 최대 3개까지만 연속으로 마실 수 있기 때문에 점화식에서 d[i-1], d[i-2]+amount[i], d[i-3]+amount[i-1]+amount[i] 중 최댓값을 구하여 d[i]에 넣어주어야 한다는 것이다. 그래서 정답 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

저는 2021년을 맞아 하루에 백준 한 문제씩 풀기를 실천하고 있는데요. 자료구조와 알고리즘 공부가 아직 덜 되어서(무작정 스택, 큐 문제 푸는 건 해봤는데 큰 의미가 없는 것 같더라고요...) 일단 인텔리제이로 자바 프로그래밍하는 것에 익숙해지자! 라는 의미로 입출력 문제를 풀고 있습니다. solved.ac에서 입출력 문제는 거의 다 브론즈더라고요 ^^;; 이번에 풀어본 입출력 문제는 다음과 같습니다. 이 문제를 보면... 1. 문자열을 입력 받는다. 2. 입력 받은 문자열을 10개씩 끊어 출력한다. 라는 해결 방법이 생각납니다. 그렇다면 이걸 자바로 어떻게 구현해야 할까요? 우선, 저는 요즘 속도와 상관없이 익숙한 Scanner로 사용자 입력을 받고 있습니다. 사용자 입력을 받은 뒤에는 문자열을 10..