[코테 합격자 되기] 16장 그리디

# 그리디 알고리즘이란?

매 순간 가장 좋아 보이는 답을 선택해서

특정 조건이 만족하는 경우 최적해를 보장하는 알고리즘이다

 

# 그리디 알고리즘의 특성

아래의 두 가지 특성이 지켜져야

그리디 알고리즘을 사용할 수 있다

1. 탐욕적 선택 속성

각 단계에서 가장 좋은 것을 선택한 것이

다음 해를 구하는데 영향을 주지 않아야 한다 (독립적)

 

2. 최적 부분 구조

문제의 최적 해결책이 하위 문제의 최적 해결책으로
구성되는 경우를 의미한다
예를 들어,

현재 해(N의 해)를 구할 때, 이전 해(N-1의 해)로 해결 가능한 경우이다

 

# 예시 1 - 동전 거슬러주기

문제 1)

 

해결)

가장 적은 동전 개수로 거슬러 주기 위해서

화폐가 큰 동전부터 최대한 활용하면 되지 않을까?

이는 곧 정답으로 그리디 알고리즘을 사용하니 풀렸다

 

문제 2)

 

해결)

문제 1번의 해결법처럼

화폐가 큰 동전부터 최대한 활용을 하면

아래의 왼쪽 그림처럼 된다

하지만, 정답은 아래의 오른쪽 그림으로 그리디 알고리즘을 사용하니 틀렸다

 

정리)

문제 1번은 그리디로 풀 수 있지만

문제 2번은 그리디로 풀 수 없다

 

그 이유는

문제 1번은 각 화폐 간 단위가 배수관계인 경우(ex. 1, 2, 4원)이다

4원은 2원의 조합이고 2원은 1원의 조합이다

즉, 앞의 동전을 최대한 사용해도 뒤의 동전 사용에 영향을 미치지 않는다

따라서, 그리디 탐욕적 선택 속성을 지켰고 그리디로 최적해가 보장된다

 

반면,

문제 2번은 각 화폐간 단위가 배수관계가 아닌(ex. 5, 4, 1원) 경우이다

5원을 최대한 사용해서 거슬러 준다면

4원을 사용하지 못하는 경우가 발생한다

즉, 이후 동전 선택에 영향을 미치게 된다

따라서, 그리디 탐욕적 선택 속성을 지키지 않았고 그리디로 최적해가 보장되지 않는다

 

# 예시 2 - 최소 신장 트리

배경 지식)

신장트리란?

모든 정점이 간선으로 연결되어 있고, 간선 개수가 정점 개수보다 하나 적은 그래프이다

최소신장트리란?

신장트리 중 가중치의 합이 최소인 것만 선택한 것이다

문제)

최소신장트리 구하기

 

해결)

여기서는 프림 알고리즘을 사용한다

해결하는 과정은 아래와 같다

1. 임의 정점 하나를 최소신장트리에 기준으로 설정한다

 

2. 최소신장트리로 연결된 정점 중 가장 가중치가 적은 정점을

최소신장트리에 추가한다 (단, 순환을 형성하지 않도록 한다)

 

3. 2번 과정을 신장트리 조건을 만족할 때까지 반복한다

 

정리)

최소신장트리를 만드는 방식을 보면

그리디 알고리즘의 속성인 탐욕적 선택 속성과 최적부분 구조를 만족하고,

현재 상황의 최적의 해를 통해

최종적인 정답을 만들어 가는 그리디 알고리즘을 이용한 것을 알 수 있다

 

# 코테에 그리드가 나오는 패턴

- 매 순간 가장 좋은 선택을 하면서 해결되는 경우

ex. 최소신장트리, 최단 경로 문제(다익스트라에서 사용, 밸만포드는 X),...

 

- 특정 조건을 만족하면서 가장 최대/최소값을 찾는 경우

ex. 부분배낭 문제(0/1 배낭은 X), 스케쥴링 문제,...