728x90 Algorithm/알고리즘 기본27 [Algorithm] Huffman Coding 1: 개념 Huffman Coding 무손실 압축 알고리즘이다. Huffman Coding 예시 파일 안에는 a,b,c,d,e,f 의 단어만 있다고 가정한다. 파일의 크기는 100,000 개 이고 각 문자의 등장 횟수는 다음과 같다. Fixed-length code: 문자를 표현하기 위해 3bit 가 필요하므로 300,000비트가 된다. Variable-length: 가변길이를 가용하면 224,000 비트가 된다. Prefix Code FIxed-length 와 Variable-length 어떻게 구할까? prefix code로 구한다. 어떤 codeword도 다른 codeword의 prefix가 되지 않는 코드 (여기서 codeword란 하나의 문자에 부여된 이진코드를 말함) 각각의 고유번호를 가지고 있기 때문에.. 2021. 10. 1. [Algorithm] Shortest Path 4: Floyd-Warshall Floyd-Warshall 최단 경로를 찾는 알고리즘중 하나이다. 모든 쌍들간의 최단 경로 길이를 구한다. Floyd-Warshall 특징 노드의 개수가 N 개이면 노드들의 번호는 1~N 이어야 한다. Floyd-Warshall 동작 방식 i~j 까지 가는데 최단 길이를 찾는 다고 가정해보자. k 라는 노드를 거쳐 갈수도 안 거쳐 갈 수도 있다. Floyd-Warshall 구현하기 위한 필요한 값들 d k [i,j]: i~j 까지의 거리 값이다 1~K 까지 속한 노드들만 거쳐간다. - 즉 K+1 은 지날수 없다. d k [i,j] 를 구하는 공식은 다음과 같다. - d k [i,j] = min(d k-1 [i,j], d k-1 [i,k]+d k-1 [k,j]) - 당황하지 말자 아래에서 설명하려 한다. .. 2021. 10. 1. [Algorithm] Shortest Path 3: Dijkstra Dijkstra 다익스트라 알고리즘 역시 최단거리를 찾는 알고리즘이다. Dijkstra 특징 음수가 없다는 전제하에 구현되었다. 노드들 중에서 distance 값이 최소인 노드를 찾고 relax 연산을 수행한다. 벨만포드와 다른점은 벨만포드는 모든 노드를 다익스트라는 최소의 값을 가진 노드에 대해 relax 연산을 한다. 수행단계 1. 시작노드 선택 2. 선택된 노드를 집합 S 에추가 (파랑색) 3. 선택된 노드와 인접한 노드 값 업데이트(빨간색) 4. 선택된 노드들과 인접한 노드중 제일 작은 delta 값을 가진 노드 선택 5, 2~4 번을 반복한다. 모든 노드가 집합 S 에 추가 되면 종료한다. 구현 코드 package algorithm.dijkstra; import java.util.ArrayLis.. 2021. 9. 29. [Algorithm] Shortest Path 2: Bellman-Ford Bellman-Ford 알고리즘 벨만포드 알고리즘은 최단거리를 찾을때 사용한다. 다익스트라와 차이점이 있다면 음수의 가중치를 취급한다는 것이다. 하지만 속도 면에서는 다익스트라가 빠르다. Bellman-Ford 특징 음수의 가중치를 처리할수 있다. 모든 노드에 대해 Relaxation 을 수행한다. 수행단계 모든 노드를 선택해 최단거리를 구한다. S 에서 모든 노드를 방문하면서 relaxtion 연산을 수행한다. 그리고 다음노드를 선택하고 또 모든 노드를 relaxtion 연산을 수행한다. n-1 노드만큼 반복해준다. 구현 package algorithm.bellmanford; import java.util.ArrayList; import java.util.List; public class Bellman.. 2021. 9. 28. 이전 1 2 3 4 5 ··· 7 다음 728x90 반응형
