욕심쟁이 알고리즘 (2)

대표적인 알고리즘 설계기법 중 하나인 욕심쟁이 방법을 적용한 데이크스트라 알고리즘, 작업 스케줄링 문제, 작업 선택 문제, 그리고 허프만 코딩의 원리와 동작, 그리고 성능과 특징을 학습한다.

 

1. 단일 출발점 최단 경로를 구하는 데이크스트라 알고리즘의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

1. 작업 스케줄링 문제의 개념, 동작, 그리고 성능을 이해할 수 있다.

---

1. 작업 선택 문제의 개념, 동작, 그리고 성능을 이해할 수 있다.

---

1. 허프만 코딩의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

데이크스트라 알고리즘

• 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로
• 욕심쟁이 방법
• O(|V|^2)
• 음의 가중치를 갖는 간선이 없다고 가정
• 거리 d[v]
  • 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 결로의 길이
  • 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법
  • 초기화 -> 출발점 d[s]=0, 나머지 모든 정점 v의 d[v]=무한대, 선택 정점 집합 S={}
  • * 미선택 정점 집합 V-S에서 d[]가 가장 작은 정점 u를 선택
    • u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새로운 거리값으로 조정
• 성능
  • 최소인 정점을 선택, u에 인접한 모든 정점 v에 대해서 for문
    • 인접 행렬 -> O(|V|^2)
    • 인접리스트 + 힙 => O((|V|+|E|)log(|V|)) : 최소 신장 트리를 구하는 프림 알고리즘과 같음
• 특징
  • 음의 가중치를 갖는 간선이 없어야 함

작업 스케줄링 문제

• 가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
  • 작업의 집합, T={t1,t2,...,tn}, t_i = (s_i, f_i) (1<=i<=n)
    • s_i : 작업 시작 시간, f_i : 작업 완료 시간
  •  작업이 시작되면 중단됨 없이 해당 기계에서 완료되어야 함
    • 작업 간 충돌 -> 한 기계에서 두 개 이상의 작업이 동시에 수행되는 것
    • 충돌을 피하기 위해 만족해야 할 조건 -> f_i<=s_j  또는 f_j<=s_i
  • 기본 아이디어
    • 각 단계에서 시작 시간이 빠른 작업을 우선적으로 선택
      • 충돌이 발생하지 않으면 해당 기계에 배정
      • 충돌이 발생하면 새로운 기계에 할당
      • 시작시간의 오름차순으로 정리
  • 성능
    • 작업을 시작 시간의 오름차순으로 정령 O(nlogn)
    • for 문 n, 작업 수행시간 logn -> O(nlogn)

작업 선택 문제

• 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제
• 기본 아이디어
  • 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택
    • 충돌이 발생하지 않으면 기계에 배정
    • 충돌이 발생하면 해당 작업을 버림
  • 완료시간의 오름차순으로 정리
• 성능
  • 정렬하는 만큼 O(nlong)

허프만 코딩

• 문자의 빈도 또는 확률 정보를 이용하는 통계적 압축 방법
  • 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
    • 출현 빈도수가 높은 문자 -> 짧은 코드
    • 출현 빈도수가 낮은 문자 -> 긴 코드
• 개념과 원리
  • ababcdbad
    • 8비트 아스키 코드로 표현하는 경우 -> 9문자x8비트 = 72비트
    • 고정 깅리 변환 코드로 표현하는 경우 -> 9문자x2비트 = 18비트
      • 문자 집함 = {a,b,c,d} -> a:00,b:01,c:10,d:11
    • 빈도수에 따른 가변 길이 변환 코드로 표현하는 경우
      • 빈도수 -> a:3,b:3,c:1,d:2
      • a->0,b->1,c->00,d->01 
        • -> 디코딩 불가
  • 접두부 코드 prefix code
    • 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드
  • 허프만 코드
    • 접두부 코드, 최적 코드
      • 최적 코드 -> 인코딩된 메시지의 길이가 가장 짧은 코드
    • 인코딩 과정
      
      • 1) 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
      • 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진코드를 부여
      • 주어진 텍스트의 각 문자를 코드로 변환하여 압축 텍스트를 생성
  • 허프만 트리
    • 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진 트리
      • 욕심쟁이 방법 적용
      • 리프 노드가 각 문자를 표시하는 전 이진트리
    • 각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복
      • 각 노드는 빈도수로 표시
      • 좌우의 두 간선은 각각 0과 1로 레이블 됨
      • 합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성
        • 부모 노드의 빈도수는 두 자식 노드의 빈도수의 합
    • 빈도수 F[]에 따라 최소 힙 Q 생성 ...
    • 예
      • abracadabra
      • a : 5, b : 2, r : 2, c : 1, d : 1
      • 허프만 트리는 유일하지 않음
    • 비트 스트링의 디코딩 과정
      • 압축된 스트링을 처음부터 차례대로 읽으면서 주어진 접두부 코드와 일치하는 코드가 나오면 해당 문자로 변환
    • 성능
      • 허프만 트리를 만드는 과정 : O(nlogn)
      • 인코딩 시간 : O(m)
    • 특징
      • 각 문자의 빈도수를 모르는 경우 주어진 텍스트를 두 번 읽음
        • 각 문자의 빈도수를 계산할 때
        • 텍스트를 읽으면서 실제 인코딩할 대
          • 이 경우 속도가 상당히 느려져 실용성이 없음
      • 압축된 데이터를 디코딩하려면
        • 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요
          • 압축된 데이터의 헤더로서 필요한 정보 제공 -> 실제 압축률 저하

cf)

① 플로이드 알고리즘의 시간 복잡도는 O(|V|3)이고, 데이크스트라 알고리즘의 시간 복잡도는 O(|V|2)이다.

② 플로이드 알고리즘은 모든 정점 간의 최단 경로를 구하는 것이고, 데이크스트라 알고리즘은 단일 출발점 최단 경로를 구하는 알고리즘이다.

④ 플로이드 알고리즘은 동적 프로그래밍 방법을 적용한 것이다.

 

허프만 트리는 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 전 이진트리(리프 노드를 제외한 모든 노드가 두 개의 자식 노드를 갖는 트리)이다

 

허프만 트리는 최적의 코드이므로 어떤 허프만 트리가 생성되더라도 동일한 텍스트에 대한 인코딩된 메시지의 길이는 모두 동일하다.

 

 정리하기

• 단일 출발점 최단 경로
  - 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 → 욕심쟁이 방법을 적용한 데이크스트라 알고리즘으로 구함
  - 데이크스트라 알고리즘 : 음의 가중치를 갖는 간선이 없는 경우에 적용 가능 → 거리 d[v] : 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 → 출발점에서 시작해서 미선택 정점 집합 V-S에서 거리 d[]가 최소인 정점 u를 선택하고, u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리를 비교해서 작은 값을 새로운 거리값으로 조정하는 과정을 반복
  - 성능 : 인접 행렬로 구현하면 O(|V|^2), 인접 리스트로 구현하고 힙을 사용하면 O((|V|+|E|)log|V|)

---

• 작업 스케줄링 문제
  - 가장 적은 개수의 기계를 사용하여 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제 → 각 단계에서 시작 시간이 빠른 작업을 우선적으로 선택해서, 충돌이 발생하지 않으면 해당 기계에 할당하고 충돌이 발생하면 새로운 기계에 할당하는 과정을 반복
  - 성능(n : 작업의 개수) : O(nlogn)

---

• 작업 선택 문제
  - 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제 → 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택해서, 충돌이 발생하지 않으면 기계에 할당하고 충돌이 발생하면 해당 작업을 버리는 과정을 반복
  - 성능(n : 작업의 개수) : O(nlogn)

---

• 허프만 코딩
  - 문자가 텍스트에서 출현하는 빈도수를 이용하여 출현 빈도수가 높은 문자는 짧은 코드를 부여하고, 출현 빈도수가 낮은 문자는 상대적으로 긴 코드를 부여해서 전체 텍스트의 길이를 줄이는 방법 → 접두부 코드, 최적 코드
  - 인코딩 과정 : ① 주어진 텍스트에서 각 문자의 출현 빈도수를 계산, ② 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여, ③ 주어진 텍스트의 각 문자를 이진 코드로 변환하여 인코딩된 텍스트를 생성
  - 허프만 트리 : 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 욕심쟁이 방법을 적용하여 상향식으로 만들어지는 전 이진 트리 → 각 문자는 리프 노드에 나타나며, 각 노드는 빈도수로 표시하고, 좌우의 두 간선에는 각각 0과 1로 레이블함 → 각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 큰 트리를 생성(합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성, 부모 노드의 빈도수는 두 자식 노드의 빈도수의 합으로 표시)하는 과정을 반복 → 허프만 트리는 유일하지 않음
  - 디코딩 : 압축된 텍스트를 1비트씩 읽으면서 허프만 트리의 루트 노드로부터 따라 내려오다가 리프 노드에 도착하면 리프 노드에 해당하는 문자를 출력하고, 루트 노드로부터 반복
  - 성능(n: 문자 집합의 크기, m: 텍스트의 길이) : O(nlogn+m)
  - 각 문자의 빈도수를 모르면 텍스트를 두 번 읽어야 함 → 실용성 결여
  - 디코딩을 위해 필요한 정보를 인코딩 메시지의 헤더에 포함시켜야 함 → 실제 압축률 저하