욕심쟁이 방법 알고리즘

알고리즘 바로가기

# 욕심쟁이 방법의 원리

• 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구하는 방법
  • “greedy” -> 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘

동적 프로그래밍 / 욕심쟁이 방법 비교

1. 두 알고리즘 모두 최적화 문제 해결에 주로 사용되고 최적성의 원리가 적용 된다, 그 예로는 최솟값이나 최댓값을 구하는 문제 등이 있다.
2. 동적 프로그래밍의 경우 소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 되는 방식으로 항상 전체적인 최적해를 구한다. 이에 반해 욕심쟁이 방법은 소문제에 대해서 하나의 최적해만 고려하게 되므로 전체적인 최적해를 구하지는 못한다.

욕심쟁이 방법의 한계

• 각 단계에서만의 최적해를 구하므로 해당 단계에서는 최고의 선택이지만 전체적으로 봤을 때는 가장 최고의 선택이라고 할수는 없다. 그러므로 전체적으로 봐야하는 문제에서는 욕심쟁이 방법으로 해를 구할 수 없는 문제도 많다.

1. 동전 거스름돈 문제

• 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제
• 기본 접근방법
  • 거스름돈의 액수를 초과하지 않는 조건
  • 단순히 액면가가 큰 동전부터 ‘욕심을 부려서’ 거스름돈을 만듦

알고리즘 구성

입력 T : 고객에게 돌려줄 거스름돈, 
입력 n : 동전의 종류
C[0 .. n-1] : 동전의 액면가를 감소순으로 저장 (500 -> 100 -> 50 -> 10)
출력 X[0 .. n-1] : 거스름돈으로 돌려줄 i번째 동전의 개수

1. 동전의 갯수만큼 반복문 생성
2. 액면가가 큰 동전부터 최대 갯수를 뽑고
3. 전체금액에서 계산된 잔돈을 빼고 다시 반복

성능 분석

• 동전의 종류 만큼(n) 시간이 걸리게 된다 그래서 빅오 표기법으로는 O(n) 의 시간복잡도를 가지게 된다.

특징

• 동전의 액면가가 임의로 주어지는 일반적인 경우
  • 동전의 종류 : 500원, 120원, 100원, 50원, 10원
• 동전의 액면가가 임의로 주어진다면 거스름돈 문제는 욕심쟁이 방법으로 해결이 불가능 하다. 즉 최적해를 찾을 수가 없다. 이를 해결하기 위해서는 동적프로그램 방법으로 해결해야 한다.

2. 배낭 문제

• 최대 용량 M(kg)인 하나의 배낭과 n개의 물체
  • 각 물체 i에 무개 w_i와
  • 해당 물체를 배낭에 넣을 떄 얻을 수 있는 이익 p_i
• 배낭의 용량을 초과하지 않는 범위내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법을 구하는 문제
  • 물체를 쪼개서 넣을 수 있다고 가정
• 기본 아이디어
  • 물체의 무게는 적으면서 이익이 가장 큰 물체부터 ‘욕심을 내어’ 최대한 넣음

알고리즘 구성

입력 p[i], w[i]: 물체 i의 이익(p[i]) / 무게 w[i]
                (단위 무게당 이익이 감소하는 순으로 정렬)
n, M : 각 물체의 갯수와 배낭의 용량
출력: X[i] : 배낭에 들어간 물체i의 비율
각 변수 들이 필요하다

1. 각 물체의 이익(p[i]) 나누기 무게(w[i])를 해서 계산하여 단위 무게당 이익을 각 물체별로 계산한다.
2. 가장 단위 무게당 이익이 가장큰 순서대로 정렬한 후 용량 (W)에 욕심내서 채워주면 된다!!
3. 마지막으로 최대 이익을 계산해서 출력해주면된다!

성능 분석

• 입력으로 주어지는 물체의 무게 w[]와 이익 p[]가 단위 무게당 이익에 따라 정렬되어 있다고 가정하면 물체의 개수에 해당하는 n번 만큼 반복 하므로 O(n)의 시간복잡도를 갖는다. 그런데 정렬되어 있지 않는 다면 정렬에 걸리는 시간까지 포함하여 O(n log n) 시간이 걸린다.

특징

• 물체를 쪼갤 수 없는 형태의 0/1 배낭 문제의 경우
• 욕심쟁이 방법을 적용하게 되면 딱 맞아 떨어지는 무게가 존재 하지 않을 경우
• 욕심쟁이 방법 적용이 불가능 하다. 그렇기 때문에 물체를 쪼갤 수 있다는 가정이 반드시 있어야 한다.

2. 최소 신장 트리

• 신장트리 : 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 트리
• 주의 사항
  • 정점이 n개이면, 트리에는 n-1개의 간선이 존재
  • 사이클이 형성되어서는 안된다.
• 최소 신장 트리 알고리즘
  • 크루스칼 알고리즘
  • 프림 알고리즘

크루스칼 알고리즘

• 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으며 추가하는 방법을 반복 실행 한다.
  • 서로 다른 연결 성분에 속하는 정점을 잇는 최소 가중치의 간선을 선택

1. 가중치가 가장 작은 순으로 정렬을 한다.
2. 가중치가 가장 작은 간선부터 모든 간선의 반복문을 실행하면서 
  두 정점이 서로 다른 연결성분이 있는지를 검사
3. 다른 연결 성분이라면 두 정점의 연결 성분을 합침

- 성능 
각 정점의 갯수만큼 반복 하는 O(|V|) 
가중치가 증가하는 순으로 모든 간선을 정렬 O(|E|log|E|)
두 정점이 서로 다른 연결 성분에 있는지 여부를 검사하는 
가장빠른 알고리즘은 상수시간으로 취급 할 수 있다. 따라서 크루스칼 알고리즘의 시간 복잡도는 O(|E|log|E|) 이다

프림 알고리즘

• 임의의 한 정점에서 시작해서 가중치가 최소인 간선을 하나씩 선택해 나가는 방법
• 성능

정점의 갯수만큼 반복한다.
미선택된 정점과  선택된 정점을 연결하는 간선 중에서 가중치가 최소인 간선을 선택 하는데
이 경우 어떤 자료구조를 사용하느냐에 따라 성능이 달라진다.
인접행렬을 이용해서 그래프를 표현 할 경우 : O(|V|^2)
인접리스트로 그래프를 표현하고, 가중치를 선택하는데 힙 구조를 사용할 경우 : O(|V|+|E|) log |V|