알고리즘 8강 :: 욕심쟁이, 최단경로, 작업스케쥴, 작업 선택

알고리즘 8강을 보며 배운내용

 

 

들어가기 전

7강 욕심쟁이 방법 강의를 듣고

욕심쟁이 알고리즘 문제를 풀었는데

강의를 들을 때처럼 꽤 직관적으로 해결됐다

 

포인트는

1. 최솟값 or 최댓값

합이나 축적된 값을 반환해야 된다면

2. 반복문 or 동적 프로그래밍처럼 값 저장

 

상기는 이렇게 마치고 8강 시작!!

 

 

정리(TL;DR)

각 단계에 충실하는 욕심쟁이 알고리즘으로

문제를 풀 수 있어보인다

최단 경로를 생각하면 지도 앱이 생각나기도

작업 스케쥴링, 작업 선택 문제를

욕심쟁이 방법을 모르고 처음 접했을 때

어버버 했던 기억도 난다

알고나니 간단하구나

 

한 정점에서 가는 모든 정점의 최단 경로

=> Dijkstra 알고리즘

 

모든 작업 마무리하는 최소 기계 개수 구하기

=> 작업 스케쥴링

 

한 기계로 할 수 있는 최대의 작업 개수 구하기

=> 작업 선택 

 

 

최단 경로

그래프에서 두 정점을 연결하는 경로 중

간선의 가중치 합이 가장 작은 경로

 

6강 동적 프로그래밍 플로이드 알고리즘 사용했었다

플로이드 알고리즘은

모든 정점 간의 최단경로, 동적 프로그래밍 적용 그리고

가중치 합이 음수인 사이클이 없다고 가정했다

 

여기선 데이크스트라 알고리즘으로 한다

 

 

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

• 출발점에서 거리 d[ ]가 최소인 정점을 차례대로 선택
• 하나의 정점에서 다른 정점으로 최단 경로 구한다
  - 단일 출발점 최단 경로
• 가정: 음의 가중치 갖는 간선은 없다 

 

d[v]란?

출발점 => 선택된 정점 집합 S => 정점 v

출발점에서 현재까지 선택된 정점 집합 S를 지나서 정점 v까지 최소 경로의 길이

 

초기화

출발점 d[s] = 0 / 나머지 모든 정점 d[v] = ∞ / 선택 정점 집합 S = [ ]

 

🤖 코드

 

 

작업 스케줄링

작업 간의 충돌 없도록 모든 작업 할당할 때 사용되는 최소의 기계

작업 간의 충돌 => 기계 하나에서 동시에 두 개이상 작업

 

⌛ 시간 복잡도

O(nlogn)

 

✅ 어떻게?

1. 시작 시간이 빠른 작업을 우선 선택
2. 다음 작업 선택
   충돌 생기면 => 다른 기계 사용
   충돌 없으면 => 같은 기계 사용

 

🤖 코드

 

 

작업 선택

기계 하나만 사용해서 할당할 수 있는 최대 작업 개수

 

⌛ 시간 복잡도

O(nlogn)

 

✅ 어떻게?

1. 완료 시간이 빠른 작업을 선택
2. 다음 작업 선택
   충돌 없으면 => 기계에 배정
   충돌 생기면 => 해당 작업 스킵

 

🤖 코드 

 

 

허프만 코딩

문자의 빈도 or 확률을 이용한 통계적 압축 방법

원래는 욕심쟁이 방법 아니다
허프만 트리를 만들 때 욕심쟁이 방법 적용

 

출현 빈도수 높은 문자 => 짧은 코드

출현 빈도수 낮은 문자 => 긴 코드

 

허프만 코딩은

디코딩에 모호성을 없애기 위해 접두부 코드 사용

그리고 최적 코드다

 

• 접두부 코드(prefix code)
  다른 문자에 붙인 이진 코드의 접두부가 아닌 코드
• 최적 코드
  인코딩된 메시지 길이가 가장 짧은 코드

 

✅ 인코딩 과정

1. 각 문자의 출현 빈도수 계산
2. 각 빈도수 이용해서 허프만 트리 만들고, 각 문자에 이진 코드 부여
3. 주어진 메시지 각 문자를 이진 코드로 변환해서 압축된 메시지 완성

 

 

허프만 트리

• 허프만 코딩에서 각 문자에 이진 코드 부여하기 위해 만든 상향식 이진 트리
• 욕심쟁이 방법 사용
• 리프 노드가 각 문자를 표시하는 완전 이진트리(Compelte Binary Tree)

 

⌛ 시간 복잡도

O(nlogn + m)

 

✅ 어떻게?

1. 각 문자 개별 트리인 상태로 시작
2. 빈도수가 작은 두 트리 합쳐서 큰 트리 생성하는 과정 반복
   - 각 노드는 빈도수로 표시
   - 좌우의 두 간선은 각각 0, 1
   - 합쳐지는 두 트리를 자식으로 갖는 부모 노드 생성

 

🤖 코드

 

특이점

힙이라는 자료구조를 사용한다

 

한계점

• 각 문자 빈도수 모르면 => 주어진 메시지 2번 읽는다
  1. 각 문자 빈도수 계산할 때
  2. 메시지 읽으면 실제 인코딩 할 때
• 압축된 메시지 디코딩하면 빈도수, 허프만 트리 정보, 문자 정보 필요
  => 위의 필요한 정보 제공하기에, 실제 압축률 저하

 

위의 한계점 때문에 

실생활 문제에서 사용될 일 거의 없다고 한다!!?

아마 특별한 경우에만 쓰이는 알고리즘일듯?

 

 

 

greed by Henley Design #unsplash