[알고리즘] : 알고리즘 기초 설명

그리디(greedy) 알고리즘

- 최적화 문제를 해결하는 알고리즘입니다.

- 욕심쟁이, 탐욕 알고리즘으로도 불립니다.

- 데이터 간의 관계를 고려하지 않고 수행 과정에서 욕심내어 최소값 또는 최대값을 가진 데이터를 선택합니다.

 # 근시안적인 선택이라고도 합니다.

 

크러스컬(kruskal) 알고리즘

- 가중치가 가장 작은 간선이 사이클을 만들지 않을 때, 욕심내어 그 간선을 추가 시킵니다.

 

프림(prim) 알고리즘

- 임의의 점 하나를 선택한 후 (n-1)개의 간선을 하나씩 추가시켜 트리를 생성합니다.

- 간선이 누적 된다는 표현을 많이 씁니다. (누적형이지만 최소 가중치 값은 올라가고 있습니다.)

 

다익스트라(dijkstra) 알고리즘

- 방향성이 있습니다.

- 출발 지점이 있습니다.

- 출발 지점부터 목적지까지의 최단 거리를 구합니다.

 

허프만 압축

- 파일의 각 문자가 8bit

- 압축의 기본은 엔트로피 코딩을 사용합니다.( jpg에서 주로 사용합니다.)

- 허프만의 2진 트리를 그려서 파일의 크기를 압축합니다.

- 좌측엔 작은 수, 우측엔 큰 수를 지정해서 (0,1) 트리를 타고 내려가면 허프만 코드가 완성됩니다.