huhsae's day huhsae's day

벨만포드 알고리즘이 글은 GeeksforGeeks의 Bellman–Ford Algorithm | DP-23를 번역한 글입니다. 그래프와 그래프의 source 정점 src를 고려하여, src부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라와 차이점은 그래프의 간선이 음의 값을 가질 수 있다는 점이다. 최단 거리문제는 다익스트라를 활용하여 해결할 수 있다. 다익스트라 알고리즘은 그리디 알고리즘 이며 피보나치 힙을 사용한다면 O(VlogV)의 시간 복잡도를 가졌다. 하지만 다익스트라는 음의 값을 가진 그래프에서는 사용할 수 없으며, 벨만포드를 사용하여야 한다. 벨만포드는 다익스트라보다 간단하며 분산 시스템에 잘 맞다. 하지만 시간 복잡도는 O(VE)로 다익스트라보다 복잡하다.알고리즘Input : 그..

플루이드 와샬 알고리즘GeeksforGeeks의 Floyd Warshall Algorithm | DP-16를 번역한 글입니다.플루이드 와샬은 모든 쌍의 최단거리를 구하는 문제이다. 주어진 가중치가 있는 방향 간선에서 모든 정점 사이의 최단거리를 해결하는 문제이다. 첫번째로 그래프 메트릭스와 같은 솔루션 메트릭스를 초기화 한다. 그 다음 모든 정점을 중간 정점으로 고려하면서 솔루션 메트릭스를 갱신할 것이다. 이 알고리즘의 아이디어는 모든 정점을 하나하나 선택하여 모든 최단거리를 갱신하는 것인데, 선택된 정점을 중간 정점으로 포함하는 것이다. 정점 K를 중간 정점으로 선택한다면, 이미 {1,2,3, ... k-1}의 정점들은 중간 정점으로 구려된 후이다. 모든 정점의 쌍 (i, j)을 시작점과 끝점으로 여긴..

다익스트라 최단거리 알고리즘geeksforgeeks - Dijkstras shortest path algorithm 을 번역한 글입니다.그래프와 그래프 속에 시작점(source vertex)이 주어진다면, 그래프안에서 시작 정점으로부터 모든 정점까지의 가장 짧은 거리를 찾는 알고리즘 다익스트라의 알고리즘은 프림의 최단 신장트리 알고리즘과 닮았다. 프림의 최단 스패닝트리(Minimum spanning tree - MST)처럼, 주어진 시작점을 루투로 하여 최단 길이 트리(Shortest path tree-SPT)를 만들 것이다. 알고리즘의 모든 스탭에서 소스로부터 가장짧으면서 아직 포함되지 않은 set에 있는 정점을 찾을 것이다. 다음은 다익스트라 알고리즘에서 가장 짧은 길을 찾기위한 자세한 step이다...

Huffman Coding Huffman Coding허프만 코드는 손실이 적은 데이터 압축 알고리즘이다. 기본 아이디어는 가변길이 코드를 문자로 할당하는 것이다. 할당된 코드의 길이는 일치하는 문자의 빈도에 기본으로 한다. 가장 빈도수가 많은 문자는 가장 작은 코드를 할당 받고 가장 빈도가 적은 문자는 큰 코드를 할당 받는다. 입력문자에 할당 된 가변 길이 코드는 접두사 코드이다. 이는 한 문자에 할당된 코드가 다른 문자에 할당 된 코드의 접두사가 아닌 방식으로 코드가 할당되었음을 의미한다. 이것은 허프만 코딩가 생성 된 비트 스트림을 디코딩 할 때 애매함이 없는지 확인하는 방법이다. 카운터 예제로 접두사 코드를 이해해보자. a,b,c,d의 카운터가 있고 각각 일치하는 코드는 00, 01, 0, 1이다...

GeeksforGeeks의 글을 해석한 포스트 입니다.Optimal Substructure Property in dynamic Programing / DP-2 이전 글에서 살펴 본것 처럼, 다음은 다이나믹 프로그래밍을 사용해서 풀수 있는 문제의 특성이다. 1) Overlapping Subproblems2) Optimal Substructure 먼저 이전 글에서 첫번째 특성은 알아 보았다. 다음으로 두번째 속성에 대해서 알아보도록 하자2) Optimal Substructure: 부문문제의 최적의 솔루션을 사용해서 주어진 문제의 최적의 해를 구할 수 있다면 이를 최적의 하부구조 속성이라고 한다. 예를 들어 최소 길이 문제는 Optimal substructure 속성을 따른다. 만약에 노드 x가 시작점 u에서..

GeekforGeek-dp1 페이지를 해석한 포스트입니다. 다이나믹 프로그램에서 부문문제 오버랩핑 특성 다이나믹 프로그래밍은 주어진 복잡한 문제를 부분문제로 나눠 문제를 해결하고 같은 결과를 다시 계산하는 것을 피하기 위해 부문문제의 답을 저장하는 알고리즘 패러다임이다. 다음은 다이나믹 프로그래밍으로 풀 수 있는 문제의 두가지 특징이다. 이번 포스트에서는 첫번째 특징( Overlapping Subproblems)을 자세히 살펴볼 것이다. 두번째 특징은 다음장에서 알아볼 것이다.Overlaping SubproblemsOptimal Substructure 1) Overlapping Subproblems: 분할 정복처럼, 다이나믹 프로그래밍은 부분문제의 해결책을 조합한다. 다이나믹 프로그램은 주로 반복되는 부..

2188 축사 2188 축사https://www.acmicpc.net/problem/2188 분류네트워크 유량애드몬드-카프 알고리즘BFS이분 매칭 TIPS포드 - 풀거슨 알고리즘을 풀 때, v -> u로 가는 용량이 주어진다면, u -> v로 가는 용량 0의 간선을 만들어 주어야 한다.코드에서는 capacity[][] 배열을 사용해서 그래프를 나타내준다면, 초기값이 0이기 때문에 1번의 내용을 생각해줄 필요가 없다. 하지만 간선 찾는 시간을 단축시키기 위해 인접리스트로 그래프를 표현했다면, 꼭 인접리스트에 반대로 가는 가상의 간선을 만들어주어야한다. 처음부터 그래프를 배열로 했다면 상관없다.이분 매칭은 source와 sink가 여러개인 네트워크 유량문제에서 super source와 super sink를 ..

1504 특정한 최단 경로백준 특정한 최단 경로 Tip다익스트라 알고리즘 활용다익스트라 알고리즘은 출발점에서 모든 정점에 대한 최단거리를 구하는 알고리즘이다.꼭 들려야 하는 정점을 끝나는 지점으로 하는 다익스트라를 여러번 돌려 원하는 값을 찾을 수 있다. CODE​ximport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;​public class BOJ_1504 {​ static final int INF = 800000; static List[] map; static int node; static int edge;​ public static void main(Strin..