[Greedy] 그리디 알고리즘
그리디 알고리즘이란?
- Greedy 욕심많은
- 탐욕 알고리즘이라고도 한다.
- 그리디 알고리즘은 현재의 시점으로 가장 최고의 선택(최적해)을 따라 최종적인 해답에 도달하는 방법이다.
-
무슨 뜻이냐면, 그리디 알고리즘은 매 순간 가장 좋아 보이는 것만 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
- 그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
- 로컬에서는 최적의 선택을 따라가도, 최종적으로는 최적이 아닐 수 있다.
- 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
그리디 알고리즘의 정당성(조건)
그리디 알고리즘으로 최적해를 도출하기 위해서는 아래 두가지 조건을 만족해야 한다.
-
탐욕적 선택 속성 현 시점에서 하는 선택이 언제나 최적해를 보장해야한다.
-
최적 부분 구조 지역적인 부분에서의 최적해가 모여 전역적인 최적해를 구할 수 있는 구조이다.(문제, 경우)
이러한 조건이 성립하지 않는 경우엔 그리디 알고리즘이 해결법이 되기 어렵다.
그리디 알고리즘이 항상 최적의 결과를 도출하는 것은 아니지만,
어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
이 장점이 그리디 알고리즘을 근사 알고리즘으로 쓸 수 있도록 해준다.
근사 알고리즘이란
- Approximation Algorithm
- 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
- 가장 최적화된 해를 구할 수는 없지만, 상대적으로 빠른 시간에 계산이 가능하며 어느정도 보장된 근사해를 계산할 수 있다.
접근방법
-
선택절차: 현재 상태에서 최적의 해답을 선택한다.
-
적절성 검사: 선택된 해가 문제 조건을 만족하는지 검사한다.
-
해답 검사: 원래 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 과정을 반복한다.
예제
백준 : 1026 보물
👀옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + … + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.
해결과정
만약, A = 1 1 1 6 0, B = 2 7 8 3 1 이라고 하자.
🤘S값이 작아지려면 더하는 수들이 작아야하고, 더하는 수가 작으려면 곱셈의 결과가 작아야하고, 곱셈이 작으려면 큰 수에는 작은 수를 곱해주어야한다.
✌️곱셈 결과가 작으려면 큰 수에는 작은 수를 매치해주어야 한다. 즉, B에서 가장 큰 수인 8에는 가장 작은 수인 0이 곱해져야 한다. 그다음 큰 수 7에는 1이 곱해져야 하고, 가장 작은 수인 1에는 가장 큰 수인 6이 곱해져야 한다.
👌따라서 B를 오름차순으로 정렬해주고, A를 내림차순으로 정렬해준 뒤 차례로 각각 곱해주면 큰 수에 작은 수가 곱해지게 되면서 최적해를 구할 수 있게 된다.