Greedy 알고리즘
탐욕알고리즘,
탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.
당장 최적인 답을 선택을해서 적합한 결과를 뽑아내야하는데 순간선택에 대해서는 최적이지만 종합적으로 봤을경우
최적이라는 보장이 절대 없다는것.
leetcode의 캔디 문제를 보면 다음과같다
- 각 child는 적어도 1개의 캔디를 가지고 있어야한다.
- 높은 점수를 가진 child는 옆의 child보다 많은 캔디를 가져야한다.
input = [1,0,2] Output = 5
해당 부분에서 최적의 조건은 2,1,2이다 총 5개의 캔디가 필요한것으로 코드를 한번 작성해 보면 다음과같다.
func candy(rating []int) int {
candies = make([]int, len(rating))
// 1로 캔디를 초기화해준다.
for i := 0; i < len(rating); i++ {
candies[i] = 1
}
// 왼쪽부터 탐색하여 캔디를 증가시켜준다.
for i := 1; i < len(rating); i ++ {
if rating[i] > rating[i - 1] {
candies[i] = candies[i - 1] + 1
}
}
// 오른쪽부터 탐색하여 체크
for i := len(rating) - 2; i >= 0; i-- {
if rating[i] > rating[i + 1] && candies[i] <= candies[i + 1]{
candies[i] = candies[i+1] + 1
}
}
c := 0
for i := 0; i < len(candies); i++ {
c += candies[i]
}
return c
}
다음 과정으로 양방향 탐색을 통해 greedy 알고리즘을 작성해봤다.