욕심쟁이 방법 알고리즘02

알고리즘 바로가기

최단 경로(데이크스트라 알고리즘)

• 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
• 플로이드 알고리즘(동적프로그래밍 빙법)과 다른점은 플로이드 알고리즘은 모든 정점간의 최단 경로를 구하고 성능은 O(|V|^3), 데이크스트라(욕심쟁이 방법) 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로(“단일 출발점 최단 경로”)를 구한다 성능은 O(|V|^2).

데이크스트라 알고리즘

• 거리 d[ v ] : 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 V에 이르는 최소경로 길이
• 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법
  1. 초기화 : 출발점 d[ s ]=0, 나머지 모든 정점 v의 d[ v ]=무한, 선택 정점 집합 S={}
  2. 미선택 정점 집합 V-S에서 d[]가 가장 작은 정점 u를 선택
  • u의 인접 정점에 대해서 u를 경유하는 거리와, 기존 거리 중에서 작은 것을 새로운 거리 값으로 조정

성능 분석

• 어떤 자료구로를 사용하느냐에 따라서 성능이 달라진다. 프림알고리즘과 동일한 시간 복잡도를 가지고 있다.

특징

• 음의 가중치를 갖는 간선이 없어야한다 : 음수를 갖는 가중치가 있는 경우 정점들이 갖는 실제 가중치의 합과 달라질수 있기 때문에 음의 가중치를 갖는 간선은 없어야 데이크스트라 알고리즘을 사용할 수 있다.

작업 스케줄링 문제

• 가장 적은 개수의 기계를 사용해서 작업간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
  • 잡업의 집합 T={t₁ … t_n}
  • 각각의 작업 t_i의 요소로는 s₁ : 작업 시작 시간, f₁: 작업 완료 시간
  • 작업이 시작되면 중단됨 없이 해당 기계에서 완료되어야 함
• 기본 아이디어
  1. 각 단계에서 시작 시간이 빠른 작업을 우선적으로 선택
  2. 출돌이 발생하지 않으면 해당 기계에 배정, 충돌이 발생하면 새로운 기계에 할당

접근 방법

1. 작업의 시작 시간의 오름차순으로 정렬
2. 기계 1에 최초 작업 할당, 작업 시간이 중복되면 새로운 기계를 생성하여 작업을 할당
3. 최종적으로 몇개의 기계가 사용됬는지 리턴을 해준다.

성능 분석

• 작업을 시작시간 순으로 오름차순으로 정렬하는 과정 O(n log n),
• 작업의 갯수만큼 반복하면서 작업을 수행할 기계에 할당하는 과정 O(n log n)
• 결과적으로 O(n log n)의 시간복잡도를 가진다.

작업 선택 문제

• 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 할당하는 문제
• 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택
  • 충돌이 발생하지 않으면 기계에 배정
  • 충돌이 발생하면 해당 작업을 버림

접근 방법

1. 작업을 완료 시간의 오름차순으로 정렬
2. 작업의 개수 만큼 반복하면서 작업이 충돌하는지 체크 충돌하지 않으면 기계에 할당
3. 결과로 하나의 기계에서 처리할 수 있는 최대 작업 개수를 리턴해준다.

성능 분석

• 작업완료 시간의 오름차순으로 정렬하는 과정 O(n log n), 작업의 개수 만큼 반복하는 과정 O(n) 총 O(n log n) 만큼이 걸린다.

허프만 코딩

• 문자의 빈도 또는 확률 정보를 이용하는 통계적 압축 방법
• 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
  • 출현 빈도수가 높은 문자 : 짧은 코드
  • 출현 빈도수가 낮은 문자 : 긴 코드
• “ababcdbad”를 허프만 알고리즘을 사용해서 압축을 하면?
  • 8비트 아스키코드로 표현하는 경우 -> 9문자 X 8비트 = 72 비트
  • 고정길이 변환 코드로 표현하는 경우 : 문자집합 총 4개 {a, b, c, d} => a:00, b:01, c:10, d:11 = 18 비트
  • 빈도수에 따른 가변 길이 변환 코드로 표현하는 경우 = 12비트
    • a:0, b:1, c:00, d:00 => 인코딩은 가능하지만 디코딩이 불가능 하다.
• 접두부 코드
  • 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드
• 허프만 코드
  • 접두부 코드이면서 최적 코드( 인코딩된 메시지의 길이가 가장 짧은 코드) 이다.
  • 인코딩 과정
    1. 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
    2. 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여
    3. 주어진 텍스트의 각 문자를 코드로 변환하여 압축된 텍스트를 생성
• 허프만 트리
  • 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진 트리
  • 이 떄 욕심쟁이 방법을 적용하게 된다.
  • 리프 노드가 각 문자를 표시하는 전 이진트리로 구성된다
  • 각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복
    • 각 노드는 빈도수로 표시
    • 좌측 간선은 0, 우측 간선은 1로 레이블 됨
    • 합쳐지는 부모노드를 생성 할 경우 자식 노드 2개의 합을 표시한다.

알고리즘

입력 F[1..n] : 문자 c의 빈도수
n : 문자 집합의 크기 c ...
출력 Q : 허프만 트리

1. 빈도수 F[]에 따라 최소 힙 Q 생성 => 힙을 생성하는 이유는 최소값을 삭제하는데 용이한 자료구조이기 때문.
2. 입력 문자 크기 n 만큼 반복문을 실행하면서 빈도가 가장 낮은 2개의 노드를 삭제 하면서 부모 노드 x를 새로 생성 하면서 두 빈도수를 더한 값을 할당해 준다.

특징

• 빈도수가 같을 때 어느것을 먼저 합쳐주냐에 따라서 허프만 코드가 여러가지 경우로 나올 수 있으므로 허프만 트리는 유일하지 않다. 하지만 어떤 코드를 사용해서 인코딩을 하더라도 결과적으로는 가장 짧은 길이로 인코딩이 되므로 방식은 아무거나 사용해도 상관 없다.
• 각 문자의 빈도수를 모르는 경우 각 문자의 빈도수를 계산할 때 한번, 텍스트를 읽으면서 한번 실제 코딩할 하는 경우 총 2번 주어진 텍스트를 읽는다. 이 경우 속도가 상당히 느려 실용성이 없다.
• 압축된 데이터를 디코딩 하려면 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요하므로 실제 압축된 데이터의 헤더로 인해 실제 압축률이 저하되는 문제도 가지고 있다.

성능 분석

• 빈도수 F[]에 따라 최소 힙 생성하는 과정 O(n), 문자 집합의 크기 만큼 반복하면서 최소값을 삭제 및 새로운 노드를 삽입 하는 과정 O(n log n), 길이 m인 텍스트의 실제 인코딩 시간 O(m) 결과적으로 O(n log n + m)의 시간복잡도를 갖는다.