[ALGOS STUDY] 2023-1-WEEK4 그리디

Greedy Algorithm

- 개념 : 최적화 문제를 해결하기 위한 알고리즘

• 각 단계에서 최적의 선택을 하면서 동작함.
• 각 단계에서의 선택은 지역적으로 최적이지만(local solution 제공), 전체적으로는 최적 해를 보장하지 않음(global solution 보장 x)
• 매우 간단하고 직관적인 방식이나 매 상황에서 최적해를 제공하지 않음.
• 그리디 알고리즘이 최적해를 보장하기 위해서는 다음의 두 조건을 만족해야 한다.

 

- 조건

• 탐욕적 선택 속성 (Greedy-choice property)
  • 앞의 선택이 이후의 결과에 영향을 주지 않는 경우
  • 탐욕적으로 선택해도 최적해를 구할 수 있음.
  • 현재 순간의 최적해를 선택하면 번복하지 않음.
• 최적 부분 구조 (Optimal substructure)
  • 전체 문제의 최적해가 각 부분 문제들의 최적해로 이루어진 경우
  • 부분 문제에서구한 최적의 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않음.

 

- 그리디 알고리즘의 문제 해결 과정

1. 전체 문제를 작은 부분 문제로 나누기
2. 부분의 최적해를 찾기
3. 부분 최적해가 정당한지 증명
4. 구현

 

- 그리디 알고리즘 vs 동적 계획법(DP)

• 그리디 알고리즘
  • 부분 최적해를 구할 때 탐색 범위를 줄여서 탐욕적으로 선택
  • 항상 최적해를 보장하지 않음. (정당성 증명 과정이 필요함.)
  • 대개 동적계획법보다 빠르다.
  • 부분 최적해를 떠올리는 것을 직관에 의존해야 하며, 부분 최적해의 정당성을 증명해야 함.
• 동적 계획법
  • 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 결과를 저장하고, 그 결과를 큰 문제를 해결할 때 이용
  • 부분 최적해를 구할 때 탐색 범위를 줄이지 않음.
  • 항상 최적해를 보장함.

 

- 그리디 알고리즘으로 해결할 수 있는 대표적인 문제의 종류

• 거스름돈 문제
  • 조건 : 동전 중 큰 단위가 항상 작은 단위의 배수여야 함.
  • 가장 작은 수의 동전으로 거스름돈을 주는 문제
  • 가장 큰 단위의 동전부터 차례로 사용하면서 거스름돈을 주면 됨.
  • 조건을 만족하지 않는 경우 (ex. 500원, 400원, 100원을 사용해서 800원 거슬러주기)  
    • 400원 * 2개이므로 실제 정답은 2
    • 그리디를 사용하면 500원*1 + 100원*3으로 4가 답으로 도출됨. 
• 활동 선택 문제
  
  • 한 시간동안 하나의 활동만 할 수 있는 상황에서 주어진 시간 내에 최대한 많은 활동을 선택하는 문제
  • 활동들을 종료 시간 기준으로 정렬한 뒤에 가장 빨리 종료되는 활동부터 선택
• 다익스트라 알고리즘
  • 하나의 시작 정점에서 모두 다른 정점으로의 최단 경로를 찾는 문제
  • 각 단계에서 가장 가까운 정점을 선택해 최단 경로 갱신
• 최소 신장 트리 문제
  • 주어진 그래프에서 모든 정점을 연결하면서 가장 작은 비용으로 트리를 형성하는 문제
  • ex. 크루스칼의 알고리즘, 프림의 알고리즘 
• 분할 가능 배낭 문제
  • 제한된 용량을 가진 배낭에 물건을 담을 때, 물건들의 일부를 분할해서 담을 수 있는 문제
  • 물건의 단위 가치 계산 후 단위 가치가 높은 물건부터 배낭에 담아서 해결 가능

 

- 문제 풀이 예시 : 백준 11399 ATM (https://www.acmicpc.net/problem/11399)

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int n, p[1000], sum = 0, result=0;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i];
	sort(p, p + n);
	for (int i = 0; i < n; i++)
	{
		sum += p[i];
		result += sum;
	}
	cout << result;
	return 0;
}

---

 

해당 주차는 제가 발표를 맡은 주였습니다. 발표를 준비하며, 그리고 글을 작성하며 참고한 글의 출처들은 다음과 같습니다.

 

<출처>

https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Greedy-Algorithm-%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://exponential-e.tistory.com/51
https://4legs-study.tistory.com/76
https://hongjw1938.tistory.com/47
https://velog.io/@falling_star3/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm
https://gamedevlog.tistory.com/60
파이썬으로 배우는 자료구조 프로그래밍 (유석종)