728x90 Algorithm77 [Algorithm] Complete Binary Tree Complete Binary Tree 완전 이진 트리라고 한다. 이번글에는 Insert 와 순회만 구현하려고 한다. Complete Binary Tree 특징 부모는 최대 2개의 자식을 가질 수 있다. 마지막 레벨에서 왼쪽부터 차례대로 채워져 있는 트리다. 중간에 비어있는 트리가 있으면 안된다. 트리는 Root, Parent, Child 로 구성 되어 있다. Complete Binary Tree 완전이진트리이다. 마지막 레벨 에 하나의 노드 만 빼고 꽉 차있다. 구현 사실 트리 구조는 노드와 insert 연산 탐색 연산이면 충분하다. 하지만 insert 할때 순서대로 채우려면 어떻게 해야될까? 고민을좀 했다. queue를 이용해서 다음에 채워야할 노드를 저장하고 있으면 될것 같다. 구현 구현코드 pack.. 2021. 10. 3. [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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 20 다음 728x90 반응형
