[방송대 알고리즘]그리디 알고리즘

※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다.

그리디 알고리즘

해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함

동적 프로그래밍 방법과의 공통점

• 최적화 문제 해결에 주로 사용
• 최적성의 원리가 적용된 방법

차이점

• 동적 프로그래밍 방법은 항상 전체적인 최적해를 구함
• 욕심쟁이 알고리즘은 각 단계에 대해서 하나의 최적해만 고려, 전체적인 최적해를 구하지 못할 수 있음

그리디의 한계

가장 좋은 바지, 가장 좋은 넥타이, 가장 좋은 자켓을 입는다고 가장 멋쟁이라고 할 수 있는가?

동전문제

• 그리디로 해결하기 위해서 다음 크기 동전이 이전 크기 동전의 배수여야함
• 일반적인 경우 거스름돈 문제는 욕심쟁이 방법으로 해결 불가

배낭문제

최대용량 M인 하나의 배낭과 n개의 물체

• 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 구하는 문제
• 그리디로 해결하기 위해서는 물건을 쪼개 넣을 수 있어야 함
• 부분 배낭 문제

물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 욕심을 내어 최대한 넣어서 해결한다.

→ 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복

성능: O(n)

입력을 정렬해야하는 경우 성능: O(nlogn)

0/1 배낭 문제

• 물체를 쪼갤 수 없는 형태의 배낭 문제

최소 신장 트리

신장 트리(spanning tree)

• 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리
• 정점이 n개이면 n-1개의 간선이 존재
• 이중 모든 간선의 가중치의 합이 최소인 트리를 최소 신장 트리라고 한다.

최소 신장 트리 알고리즘

• 크루스칼 알고리즘
• 프림 알고리즘

크루스칼 알고리즘

• 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면서 추가시키는 방법
• 서로 다른 ‘연결 성분’에 속하는 정점을 잇는 최소 가중치의 간선을 선택
• 같은 연결 성분끼리 연결하게 되면 사이클이 생겨 신장 트리가 아니게 되버림

성능: O(ElogE)

프림 알고리즘

• 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법
• 이미 선택된 정점에 부수된 가중치가 최소인 간선을 추가하는 방법
• 힙을 이용

최단 경로

데이크스트라 알고리즘

• 하나의 정점에서 다른 모든 정점까지의 최단 경로
• 기본적으로 인접 행렬 사용시 O(V^2)
• 인접 리스트와 힙 사용시 O((V+E)logV)
• 음의 가중치를 갖는 간선이 없다고 가정

거리 d[v]

• 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
• 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법

phi[]: 최단 경로를 만드는 선행 정점

특징

• 음의 가중치를 갖는 간선이 없어야 함

작업 스케줄링 문제

가장 적은 개수의 기계를 사용하여 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제

• 작업 간의 충돌이 없어야 함 → 충돌: 한 기계에서 두 개 이상의 작업이 동시에 수행되는 것
• 작업 i와 j가 충돌을 피하기 위한 조건 → f_i ≤ s_j, 또는 f_j ≤ s_i
• 각 작업이 시작되면 중단됨 없이 해당 기계에서 완료되어야 함
• O(nlogn)

기본 아이디어

• 각 단계에서 시작 시간이 빠른 작업을 우선적으로 선택
• 충돌이 발생하지 않으면: 해당 기계에 배정
• 충돌이 발생하면: 새로운 기계에 배정

작업 선택 문제

하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제

• O(nlogn)

기본 아이디어

• 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택해서
• 충돌이 발생하지 않으면 기계에 배정
• 충돌이 발생하면 작업을 버림

허프만 코딩

• 허프만 코딩 자체가 욕심쟁이 방법이 적용됬다기 보다는 허프만 트리를 만드는 과정에서 적용됨

---

• 텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
• 출현 빈도수가 높은 문자: 짧은 코드
• 출현 빈도수가 낮은 문자: 긴 코드

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

• 각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드
• 허프만 코딩은 접두부 코드이자 최적 코드이다.
• 최적 코드: 인코딩된 메시지의 길이가 가장 짧은 코드

인코딩 과정

• 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
• 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여
• 주어진 텍스트의 각 문자를 이진 코드로 변환하여 압축된 텍스트를 생성

허프만 트리

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

특징

• 각 문자의 빈도수를 모르는 경우 → 주어진 텍스트를 2번 읽음
• 이 경우 속도가 상당히 느려 실용성이 없음
• 압축된 데이터를 디코딩하려면 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요 → 압축된 데이터의 헤더로써 필요한 정보를 제공하여 실제 압축률 저하를 초래