[알고리즘] 그리디 알고리즘(Greedy Algorithm)

츨처: unsplash.com

 

그리디 알고리즘이란?

그리디 알고리즘(탐욕법)이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 뜻한다.

 

그리디 알고리즘은 동적 프로그래밍(DP)을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안해 고안되었다.

 

그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택해 나가는 방식의 알고리즘 설계 기법이다.
하지만 이 가장 좋은 결과는 항상 최종적인 결과 도출에 대한 최적해를 보장해 주는 것은 아니다.

 

출처: https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

위 그림에서 가장 큰 값이 최적의 값일 때, 그리디 알고리즘은 현재 상황에서 가장 최적의 값을 구하기 때문에

최종적인 답은 23이 나오게 된다(최적의 값: 128).

그리디 알고리즘은 항상 최종적인 결과 도출에 최적해를 보장해 주는 것이 아니기 때문에 상황에 맞게 사용해야 한다.

 

 

그리디 알고리즘의 특징

그리디 알고리즘은 다음과 같은 특성을 가지는 문제들을 해결하는 데 강점이 있다.

탐욕 선택 속성(greedy choice property)
최적 부분 구조(optimal substructure)

 

최적 부분 구조는 DP로 문제를 풀기 위한 조건에 언급된 적이 있다.

최적 부분 구조에 대한 설명은 DP 포스팅에 잘 나와 있으므로 여기에서 언급하지는 않겠다.

 

여기서 탐욕 선택 속성이 무엇인지 간단하게 설명하자면,

탐욕적인 선택은 항상 안전이 보장되어야 한다.
여기서 안전하다는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있는 경우여야 한다는 뜻이다.

 

그림으로 간단히 설명하자면 다음과 같은 도로가 있다.

출처: 나무위키

 

서울에서 부산까지 최단 경로로 가고자 할 때, 우리는 탐욕적인 선택으로 인해 서울에서 대구로 가는 가장 짧은 길인 200km를 선택했다.

이 선택으로 인해 최종적인 답에 더 가까워졌으면 탐욕 선택 속성의 만족으로 그리디 알고리즘을 사용할 수 있다.

위 예시는 최적 부분 구조도 만족하는 예시이다.

 

그리디 알고리즘 사용하기

그리디 알고리즘을 입문하기 좋은 문제를 몇 개 소개하겠다.

(백준) 동전 0, Silver 4

https://www.acmicpc.net/problem/11047

 

동전의 종류 N과 만들어야 하는 금액 K가 주어질 때, 제각각인 동전의 가치 A가 N개가 주어질 때, A를 사용해 K를 만들기 위한 최솟값을 구하는 문제이다.

동전의 개수를 최소한으로 이용해 K를 구해야 하는데 작은 동전부터 큰 동전 순으로 구하는 방법과 큰 동전부터 작은 동전 순으로 구하는 방법 2가지가 있다.

 

개인적으로 나는 큰 동전부터 시작해 작은 동전 순으로 구하는 것이 편했다.

예를 들어 K가 4790이고, A가 1, 5, 10, 50, 100, 500, 1000, 5000이 있을 때, 4790원을 만들려면 1000원 4개, 500원 1개, 100원 2개, 50원 1개, 10원 4개가 필요하므로 4790원을 만드는 최솟값은 12개이다.

 

만약 해결하지 못한 문제라면 위 힌트를 보고 문제를 잘 해결해 보길 바란다. 정답 코드는 첨부하지 않겠다.

 

 

정리

그리디 알고리즘의 개념을 간단히 공부해 보았다.

그리디 알고리즘도 DP처럼 많은 문제를 풀어봐서 자신이 그리디를 써서 풀어도 되는지 판단하는 능력과 그리디를 어떻게 활용할 수 있는지 생각하는 능력을 길러 봐야겠다.

 

 

참고한 글

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕법(그리디) 알고리즘

https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘