[플레이데이터][알고리즘] 탐욕법(그리디 알고리즘)
그리디 알고리즘 (탐욕법)
🔊 2021.05.18 (화) 엔코아 플레이데이터 알고리즘 특강 9주차 내용을 정리한 노트 게시물입니다.
탐욕법은 정해진 풀이방법이 없기 때문에 다양한 예제를 보면서 진행한다.
탐욕법이란?
- 전체가 아닌 현재 상태에서 최선의 선택을 하는 알고리즘
- 전체탐색보다 빠르지만 반드시 정답을 도출하지 않는다.
큰 문제를 작은 문제로 나누어 선택을 한다는 과정에서 동적계획법과 유사하지만,
작은 문제들의 최적의 해가 전체의 최적의 해가 될 수 있다는 점에서 동적계획법으로 풀어야 할 지 혹은 탐욕법이 적용 가능한지 구별을 할 수 있어야한다.
즉, 탐욕법이 적용가능한 문제인지 아닌지를 판별할 수 있어야한다!
탐욕법 예제
ⓐ 최단경로
☞ 동적계획법을 적용해야 하는 경우 (그림)
위 그림처럼 출발점부터 최단경로로 도착점에 도착하려고 한다.
그렇다면 1번 선택으로 3 혹은 5를 지불함으로써 이동할 수 있다.
하지만, 1번 선택의 결과가 2번 선택에 영향을 미치기 때문에 우리는 1번에서 3을 선택하는 것이 정답이 될 수 있다고 말할 수 없다.
이 경우는 동적계획법을 활용하여 문제를 접근해야한다.
☞ 하지만, 아래 그림처럼 길이 있다면 어떨까?
1번에서 선택을 한 이후 1번에서의 선택이 2번에서의 선택에 영향을 주지 않고, 2번에서의 선택이 3번 선택에 영향을 주지 않는다면 우리는 매 순간순간 최적의 길을 선택하여 도착점에 도착하여 최단경로로 이동할 수 있는 것이다.
바로 지금의 경우 우리는 탐욕법을 활용할 수 있는 것이다.
즉 탐욕법으로써의 조건은
☞ 탐욕법의 조건
- 각 부분에서의 선택이 다른 부분에게 영향을 주지 않는다.
- 각 부분에서의 최적해결이 최종 해결방법이다.
다른 탐욕법의 예제를 보도록 하자.
ⓑ 교환 가능한 동전의 최소 갯수
- 아래 그림과 같이 500원 100원 50원 10원 네 종류의 동전을 무한하게 보유하고 있다.
- 우리는 1,970원을 최소의 동전의 갯수로 만들고자 한다.
- 10원짜리 동전을 197개를 사용해서 1,970원을 만들 수도 있겠지만, 금액 단위가 가장 큰 500원부터 채워나간다면 우리는 가장 적은 동전을 활용하여 1,970원을 만들 수 있는 것이다.
다른 문제이다.
만약 동전이 아래와 같이 500, 300, 200, 50, 10원 단위로 있다면 앞에서와 같은 방법으로 적용이 가능할까?
하지만,
500원짜리 3개로 1,500원을 만들고,
300원을 사용하지 않고,
200원 2개를 사용해서 400원을 만들어주는 방법을 택하면 동전의 갯수는 몇개가 될까?
계속 진행해본다.
50원 한개를 사용해서 부족한 70원을 채워주고… 아직 20원이 부족하다
부족한 20원을 10원짜리 2개를 이용해서 채워주면 이 때 몇개의 동전이 필요할까?
앞에서는 9개의 동전이 필요했지만, 이 방법으로는 8개 동전이 필요한 것이다.
즉, 순간순간 최적을 적용하던 탐욕법보다 더욱 적은 동전의 갯수로 정답을 도출하였다. 그 이유로는 동전들이 서로간 배수가 아니기 때문에
즉, 300원짜리 동전은 200원짜리 동전의 배수가 아니기 때문에 앞에서의 선택이 뒤에서의 선택에 영향을 미친다는 것이다.
(동전들이 서로간 배수인 경우에 탐욕법 적용 가능)
즉, 우리는 규칙을 찾아 문제를 풀어야 할 상황을 마주친다면 동적계획법인지 혹은 동적계획법에서 서로간 영향이 없는 탐욕법이 적용 가능한지를 찾아낼 수 있어야 한다.
다른 예제를 보도록 한다.
ⓒ 가능한 많은 수의 회의시간
하나의 회의실을 여러 팀에서 사용하길 원할 경우 가장 많은 회의시간을 가질 수 있도록 회의실을 배치해주는 것이다.
앞에서부터 최적의 선택을 찾아나가보도록 하겠다.
처음에 9시부터 10시 사이에 사용가능한 회의가 있는지 확인한다.
하나의 회의가 존재하긴 하지만 10시에 끝나는 회의가 아니므로 탐색을 종료한다.
이번엔 시간을 조금 더 넓혀서 9시에서 11시 사이에 끝날 수 있는 회의가 존재하는지 확인한다.
비록 늦게 시작하기는 하나 11시에 끝날 수 있는 회의가 존재하므로 회의실을 배치해주도록 한다. 그리고 작업을 종료한다.
11시에 끝났으니 다시 11시를 기점으로 탐색을 시작한다.
11시에서 12시 사이에 끝날 수 있는 회의가 존재하지 않으므로 구간을 조금 더 넓히도록 하겠다.
11시에서 13시 사이에 끝날 수 있는 회의가 존재하는지 확인한다. 끝나는 회의가 없으므로 탐색을 종료한다.
구간을 조금 더 넓혀 11시에서 14시 사이에 끝날 수 있는 회의가 존재하는지 확인한다.
14시를 기점으로 끝날 수 있는 회의가 하나 존재하므로 회의실을 배치해주고 작업을 종료한다.
계속 이어서 14시부터 시작하여 15시에 끝날 수 있는 회의가 존재하는지 탐색한다.
하나의 회의가 존재하나 끝나지는 않으므로 탐색을 종료한다.
시간을 더 넓혀서 14시에 시작해서 16시에 끝나는 회의가 존재하는지 확인한다.
새롭게 시작하는 또 다른 회의가 존재하나 16시에 끝나지 않으므로 탐색을 종료한다.
시간을 조금 더 넓혀 14시에서 17시 사이에 가능한 회의가 있는지 확인한다.
비록, 14시보다 늦은 15시에 시작하긴 하지만 보다 일찍 끝나므로 회의실을 배치해주고 작업을 종료한다.
계속해서 17시 이후부터 18시까지의 회의를 탐색한다.
하지만, 그 시간에 시작해서 끝날 수 있는 회의는 존재하지 않으므로 탐색을 종료한다.
시간을 조금 더 넓혀서 17시에서 19시 사이에 가능한 회의가 있는지 확인한다.
하나의 회의가 존재하므로 회의실을 배치해주고 작업을 종료한다.
이렇게 우리는 탐욕법을 적용하여 가능한 많은 팀이 회의실을 사용할 수 있도록 배치할 수 있었다.
(결과)
또 다른 탐욕법의 예제를 보자
ⓓ 카드 게임
A, B 두 사람이 카드를 가지고 있다.
서로 한 장씩 꺼내어 숫자를 비교했을 때 카드에 있는 숫자가 더 큰 사람이 점수를 획득하는 게임이다.
다음과 같은 상황에서 A라는 사람이 얻을 수 있는 최대 점수 값이 알고 싶은 경우 우리는 탐욕법을 적용할 수 있다.
먼저, 위 이미지에 보이는 것과 같이 A와 B가 카드를 가지고 있다.
뒤죽박죽 섞여있지만, 탐욕법을 적용하기 위해 카드를 정렬하도록 하겠다.
카드가 위와 같이 내림차순으로 정렬되었다.
그리고, 한 장씩 비교해보도록 하겠다.
제일 앞에 있는 카드를 비교해보도록 하겠다.
A가 더 크므로 A가 1점을 가져갈 수 있다.
이어서 다음 카드를 비교해보도록 하겠다.
A가 더 작은 카드를 가지고 있기 때문에 점수를 얻을 수 없다.
따라서, B의 다음 카드와 비교하도록 하겠다.
B의 다음 카드인 9와 비교하였을 때 A가 더 클 수 있으므로 A는 1점을 더 획득할 수 있다.
그리고, 다음 카드를 비교하도록 하겠다.
다음 카드인 8과 7을 비교했을 때 A가 더 크기 때문에 A는 1점을 더 획득할 수 있다.
그리고, 다음 카드를 비교하도록 하겠다.
A가 더 작다.
그러므로, B의 카드를 버리고 다음 카드를 비교해보도록 하겠다.
A가 더 크므로 A는 한번 더 점수를 획득할 수 있다.
그리고, 이어서 게임을 진행하려고 하지만 B가 남아있는 카드가 없으므로 작업을 종료한다.
(최종 결과)
따라서, A가 가지고 있는 카드로는 B와 게임을 했을 경우
최대 4점의 점수를 얻을 수 있음을 우리는 알 수 있다.
이렇게 우리는 동전의 최소 갯수, 회의시간, 카드 게임까지 3개의 탐욕법 예제를 같이 살펴보았다.
탐욕법이 적용가능한지 찾아내는 것, 순간순간 최적의 선택이 전체의 정답이 되는 그 이유를 아는 것도 중요하지만 가능한 많은 탐욕법 예제를 경험해보는 것 만큼 좋은 방법도 없다.
Leave a comment