Minjeong Lee

Minjeong Lee

I have experience working as a Software System Developer, and I am currently pursuing further knowledge and skills through my studies in Data Science.

Greedy Algorithm(2)



최단경로

  • 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로

데이크스트라(다익스트라) 알고리즘

  • 거리(d[v])
    • 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
  • 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법
    • 초기화 → 출발점 d[s]=0, 나머지 모든 정점 v의 d[v]=무한대, 선택 정점 집합 S = {}

    • 미선택 정점 집합 V-S에서 d[]가 가장 작은 정점 u를 선택

      → u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새로운 거리값으로 조정

  • 알고리즘

      Dijkstra (G, s) {
  	S = Ø; 
  	d[s]=0;
  	for (모든 정점 v≠s) d[v] = ∞;
  	for (모든 정점 v에 대해서) phi[v] = Null; 
  	while ( S != V ) {
  		d[u]가 최소인 정점 u∈V-S를 선택
  		S = S ∪ { u };
  		for ( u에 인접한 모든 정점 v에 대해서 )
  			if ( d[v] > d[u] + (u,v)의 가중치 ) {
  					d[v] = d[u] + (u,v)의 가중치; 
  					phi[v] = u;
  			} 
  	}
  	return d[], phi[]; 
  }

  • 성능

    인접행렬 → O(|V|2)

    인접 리스트 + 힙 → O((|V|+|E|) log|V|)

    (* 프림알고리즘과 성능이 같음)

  • 특징
    • 음의 가중치를 갖는 간선이 없어야 함. (음수 가중치 x)

작업 스케줄링 문제

  • 가장 적은 개수의 기계를 사용, 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제
    • 작업의 집합 T = {t1, t2, …, tn}, ti = (si, fi)
      • si : 작업 시작 시간, fi : 작업 완료 시간
    • 작업 간의 충돌이 없어야 함
      • 작업 간의 충돌? : 한 기계에서 두 개 이상의 작업이 동시 수행
      • 작업 i와 j가 충돌을 피하기 위한 조건 → fi ≤ sj OR fj ≤ si

    → 기본 아이디어: 각 단계에서 시작 시간이 빠른 작업을 우선적으로 선택

    • 충돌 미발생시 > 해당 기계에 배정
    • 충돌 발생시 > 새로운 기계에 배정

  • 알고리즘

      TaskScheduling (T[][], n) {
  	작업을 시작 시간의 오름차순으로 정렬; // O(nlogn) 
  	m = 1;
  	for (i=0; i<n; i++) { // O(n)
  		if ( 작업 ti를 수행할 기계 p (1≤p≤m)가 있으면 ) // O(nlongn) 
  			작업 ti를 기계 p에 할당;
  		else {
  			m = m + 1;
  			작업 ti를 새 기계 m에 할당; 
  		}
  	}
  	return m; 
  }

  • 성능

    → O(nlogn)

작업 선택 문제

  • 개념과 원리
    • 하나의 기계만 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제
      • 작업의 집합 T = {t1, t2, … tn}, ti = (si, fi)
  • 기본 아이디어
    • 각 단계에서 ‘완료 시간이 빠른 작업’을 우선적으로 선택
      • 충돌 미발생시 → 기계에 배정
      • 충돌 발생시 → 해당 작업 버림

  • 알고리즘

      ActivitySelection (T[][], n) {
  	작업을 완료 시간의 오름차순으로 정렬; //O(nlogn)
  	m = 0;
  	for (i=0; i<n; i++) //O(n)
  		if ( 작업 ti가 충돌을 일으키지 않으면 ) { 
  			m = m + 1;
  			작업 ti를 기계에 할당; 
  		}
  	return m; 
  }

  • 성능 분석

    → O(nlogn)

허프만 코딩

  • 이 코드를 만들기 위해 과정 중에 호프만 트리를 만듦, 이 트리를 만드는 과정에 욕심쟁이 방법이 적용됨
  • 문자의 빈도 또는 확률 정보를 이용한 통계적 압축 방법
    • 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
      • 출현 빈도수가 높은 문자 → 짧은 코드
      • 출현 빈도수가 낮은 문자 → 긴 코드
  • 개념과 원리
    • ex) 텍스트 “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’

          → 010100011001

          문제: 디코딩하는 경우, 본래 문자와 달라질 수 있음(경우의 수 때문에). 모호성 문제

  • 모호성 없이 디코딩하려면 접두부 코드prefix code이어야 한다

    • 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드

      → 따라서, 인코딩 할 때 접두부 코드로 만들어야 한다.

  • 허프만 코딩
    • 접두부 코드이자 최적코드
      • 최적코드? 인코딩된 메시지 길이가 가장 짧은 코드

  • 인코딩 과정

    1) 주어진 텍ㅌ스트에서 각 문자의 출현 빈도수 계산

    2) 각 문자의 빈도수를 이용하여 허프만 트리를 생성, 각 문자에 이진 코드를 부여

    3) 주어진 텍스트의 각 문자를 이진 코드로 변환하여 압축된 텍스트를 생성

  • 허프만 트리
    • 허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진 트리
      • 욕심쟁이 방법을 적용
      • 리프 노드가 각 문자를 표시하는 전 이진트리
    • 각 문자가 개별적인 트리인 상태에서 시작, 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복
      • 각 노드는 빈도수로 표시
      • 좌우의 두 간선은 각각 0과 1로 레이블 됨

      • 합쳐지는 두 트리를 자식 노드로 갖는 부모 노드 생성

        → 부모 노드의 빈도수는 두 자식 노드의 빈도수의 합으로 표시

    • 알고리즘

        HuffmanTree (F[], n) {
  	빈도수 F[]에 따라 최소 힙 Q 생성; // O(n)
  	for (i=0; i<n; i++) { // O(n)
  		u ← 힙 Q에서 최솟값 삭제; // O(logn)
  		v ← 힙 Q에서 최솟값 삭제;
  		새 노드 x를 생성하여 u와 v를 x의 두 자식 노드로 지정; 
  		노드 x의 빈도수 ← u의 빈도수 + v의 빈도수;
  		노드 x를 힙 Q에 삽입;
  	}
  	return Q; 
  }

      ex) “abracadabra”

      a - 5, b - 2, r -2, c - 1, d -1

      스크린샷 2022-04-03 오후 4.01.00.png

      문자 코드
      a 0
      b 100
      c 111
      d 110
      r 101

      최적화기 때문에 비트는 동일함 (합치는 순서가 다르더라도)

      → 허프만 트리는 유일하지 않음

    • 디코딩 과정
      • 압축된 스트링을 처음부터 차례대로 읽으면서 주어진 접두부 코드와 일치하는 코드가 나오면 해당 문자로 변환

    • 성능

      → O(nlogn) (호프만트리를 생성하는 코드 *n:문자집합크기)

      +O(m) (길이 m인 텍스트의 실제 인코딩 시간)

      ⇒ O(nlogn + m)

  • 특징

    • 각 문자의 빈도수를 모르는 경우

      → 주어진 텍스트를 두 번 읽음

      1) 각 문자의 빈도수를 계산하는 경우

      2) 텍스트를 읽으면서 실제 인코딩하는 경우

      → 이 경우 속도가 느림, 성능의 문제가 있음

    • 압축된 데이터를 디코딩하려면?

      • 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요
        • 압축된 데이터의 헤더로써 필요한 정보를 제공 → 실제 압축률 저하 초래

    → 호프만 코드가 사용되는 경우는 실생활에서 거의 없음.