티스토리 뷰

algorithm

[algorithm] 그리디 알고리즘

tonirr 2021. 4. 25. 03:12
  • 최단경로
    • 가중방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
    • 플로이드 알고리즘
      • 모든 정점 간의 최단 경로
      • 동적 프로그래밍 방법 적용
      • O(|V|^3)
      • 가중치의 합이 음수인 사이클이 없다고 가정
플로이드 Floyd 알고리즘 다익스트라 Dijkstra 알고리즘
모든 정점 간의 최단 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로
(단일 출발점 최단 경로)
동적 프로그래밍 방법 적용 그리디 방법 적용
O(|V|^3) O(|V|^2)
가중치의 합이 음수인 사이클이 없다고 가정 음의 가중치를 갖는 간선이 없다고 가정
  •  
    • 다익스트라 알고리즘
      • 거리 d[v]
        • 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
      • 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법
        • 초기화 -> 출발점 d[s] = 0, 나머지 모든 정점 v의 d[v] = ∞, 선택 정점 집합 S= {}
        • 미선택 정점 집합 V-S에서 d[] 가 가장 작은 정점 u를 선택
          • u의 인점 정점에 대해서 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새로운 거리값으로 조정
      • 특징
        • 음의 가중치를 갖는 간선이 없어야 함
  • 작업 스케줄링 문제
    • 가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
      • 작업의 집합 T = {t1, t2, ... , tn}, ti = (si, fi) (1<=i<=n)
        • si: 작업 시작 시간, fi: 작업 완료 시간 
      • 작업간의 충돌이 없어야 함
        • 작업 간의 충동 -> 한 기계에서 두개 이상의 작업이 동시에 수행되는 것
        • 작업 i와 j가 충돌을 피하기 위한 조건 -> fi<=sj 또는 fj<=sj
      • 각 작업이 시작되면 중단됨 없이 해당 기계에서 완료되어야 함
    • 기본 아이디어
      • 각 단계에서 시작시간이 빠른 작업을 우선적으로 선택해서
        • 충돌이 발생하지 않으면 -> 해당 기계에 배정
        • 충돌이 발생하면 -> 새로운 기계에 배정
    • 성능 분석
      • O(nlogn)
  • 작업선택
    • 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제
      • 작업의 집합 T = {t1, t2, ... , tn}, ti = (si, fi) (1<=i<=n)
    • 기본 아이디어
      • 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택해서
        • 충돌이 발생하지 않으면 -> 기계에 배정
        • 충돌이 발생하면 -> 해당 작업을 버림
    • 성능 분석
      • O(nlogn)
  • 호프만 코딩
    • 문제의 빈도 또는 확률 정보를 이용한 통계적 압축 방법
      • 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
        • 출현 빈도수가 높은 문자 -> 짧은 코드
        • 출현 빈도수가 낮은 문자 -> 긴 코드
    • 텍스트 "ababcdbad"
      • 8비트 아스키 코드로 표현하는 경우 -> 9문자 * 8비트 = 72비트
      • 고정 길이 변환 코드로 표현하는 경우 -> 9문자 * 2비트 = 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' 
            • 인코딩: 010100011001
            • 디코딩하는 경우 여러가지 해석이 가능하여 모호성이 발생
      • 모호성 없이 디코딩하려면 접두부 코드 prefix code이어야 함
        • 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드
      • 허프만 코딩
        • 접두부 코드, 최적 코드
          • 최적 코드 -> 인코딩된 메시지의 길이가 가장 짧은 코드
        • 인코딩 과정
          • 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
          • 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여
          • 주어진 텍스트의 각 문자를 이진 코드로 변환하여 압축된 텍스트를 생성
        • 허프만 트리
          • 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진트리
            • 그리디 알고리즘 방법 적용
            • 리프 노드가 각 문자를 표시하는 전 이진트리
          • 각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복
            • 각 노드는 빈도수로 표시
            • 좌우의 두 간선은 각각 0과 1로 레이블됨
            • 합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성
              • 부모 노드의 빈도수는 두 자식노드의 빈도수의 합으로 표시
          • 예제
            •  "abracadabra"

 

  •  
    •  
      •  
        •  
          • a: 0, b: 100, c: 110, d: 111, r: 101 
          • 01101010110011101001010: 23비트
          • 디코딩 과정
            • 압축된 스트링을 처음부터 차례대로 읽으면서 주어진 접두부 코드와 일치하는 코드가 나오면 해당 문자로 변환
          • 성능 분석
            • O(nlogn) + O(m)
              • n: 문자 집합의 크기
              • 길이 m인 텍스트의 실제 인코딩 시간
              • O(nlogn + m)
          • 특징
            • 각 문자의 빈도수를 모르는 경우 -> 주어진 텍스트를 2번 읽음
              • 각 문자의 빈도수를 계산할 때
              • 텍스트를 읽으면서 실제 인코딩 할 때
                • 이 경우 속도가 상당히 느려 실용성이 없음
            • 압축된 데이터를 디코딩하려면
              • 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요
                • 압축된 데이터의 헤더로써 필요한 정보를 제공 -> 실제 압축률 저하를 초래
  • 최단 경로
    • 단일 출발점 최단 경로 -> "다익스트라 알고리즘"
      • 성능: 인접행렬 O(|V|^2), 인접리스트 O((|V| + |E|)log|V|)
      • 음의 가중치를 갖는 간선이 없는 경우에 적용 가능
    • 작업 스케줄링 문제
      • 가장 적은 개수의 기계를 사용해서 충돌 없이 모든 작업을 할당하는 문제
        • 성능: O(nlogn) (n: 작업의 개수)
    • 작업 선택 문제
      • 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 할당하는 문제
      • 성능: O(nlogn) (n: 작업의 개수)
    • 허프만 코딩
      • 접두부 코드, 최적 코드, 허프만 트리(그리디 알고리즘 방법, 전 이진트리)
        • 성능: O(nlogn+m) (n: 문자 집합의 크기, m: 텍스트의 길이)
        • 각 문자의 빈도수를 모르는 경우 텍스트를 두 번 읽음
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함