8강 욕심쟁이 알고리즘(2)

최단 경로

• 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
• 데이크스트라 알고리즘
  • 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 문제 (음의 가중치를 갖는 간선이 없다고 가정한다)
  • 거리 d[v]
    출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
  • 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법이다.

작업 스케줄링 문제

• 가장 적은 개수의 기계를 사용하여 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
• 각 단계에서 ‘시작 시간이 빠른 작업’을 우선적으로 선택해서 충돌이 발생하지 안흥면 해당 기계에 배정하고 충돌이 발생하면 새로운 기계에 배정한다.
• 성능
  O(nlogn)

작업 선택

• 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제
• 각 단계에서 ‘완료 시간이 빠른 작업’을 우선적으로 선택해서 충돌이 발생하지 않으면 기계에 배정하고 충돌이 발생하면 그 작업은 제외시킨다.
• 성능
  O(nlogn)

허프만 코딩

• 문자의 빈도 또는 확률 정보를 이용하여 통계적으로 압축하는 방법
  주어진 텍스트에서 각 문자가 출현하는 빈도수에 따라 서로 다른 코드를 부여한다(빈도수가 높은 문자 → 짧은 코드, 빈도수가 낮은 문자 → 긴 코드)
  모호성 없이 디코딩 하여면 접두부 코드 이여야 한다. (각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드)
• 허프만 코딩
  접두부 코드이자 최적 코드 이다.
  (최적코드: 인코딩 된 메세지의 길이가 가장 짧은 코드)
• 허프만 코딩의 인코딩 과정
  1. 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
  2. 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여
  3. 주어진 텍스트의 각 문자를 이진 코드로 변환하여 압축된 텍스트를 생성
• 허프만 트리
  허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진트리
  각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 가장 작은 두 트리를 합쳐서 큰 트리를 생성하는 과정을 반복한다.
• 성능
  O(nlogn+m) (n: 문자 집합의 크기, m: 텍스트의 길이)