[알고리즘] 그리디 알고리즘

백준 알고리즘 문제들을 풀면서, 단순히 코드를 작성하고 문제만 푸는 것이 아니라 알고리즘 공부도 병행하면서 해야겠다는 필요성을 느꼈다. 그 첫번째 시작이 이번 그리디 알고리즘이다.

 

 

 

---

 

그리디 알고리즘이란? 

 

 

 

그리디 알고리즘이란 그 이름 Greedy 에서 알 수 있듯이 매 선택의 순간마다 현재 상황에서 당장 최적인 답을 선택하는 방법을 의미한다. 쉽게 말하면 먼 미래를 생각하는게 아니라, 당장 눈 앞에 보이는 최적의 선택을 하는 방식이다. 

 

 

 

 

이런 그리디 알고리즘은 일반적인 상황에서 최적의 해를 보장할 수 없을때가 많다.

하지만 이런 그리디 알고리즘을 적용했을 때 최적의 답을 보장해주는 알고리즘 문제들이 몇 있기에, 

그 문제들 유형을 정리해놓는 것이 필요하다고 생각했다. 

 

 

 

 

 

그리디 알고리즘 문제는 다음 포스팅부터 살펴보는 것으로 하고,,,

우선은 그리디 알고리즘에 대한 좀 더 구체적인 설명을 그림과 함께 해보려고 한다. 

(아래 그림의 출처는 [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 에 있습니다.)

 

 

 

 

위의 문제 상황에서 최적의 해를 먼저 구해보자. 

 

 

 

노드 값의 합이 최대가 되는 것은, 그림에서 보이는 것처럼 색칠된 루트를 따라가는 경우이다. 

5 + 7 + 9 => 21

 

 

 

 

 

 

 

 

 

하지만 본 문제에 그리디 알고리즘을 적용하는 경우를 생각해보자.

 

 

 

 

매 순간순간에 당장 최적의 값을 골라야하기때문에 

위의 그림에서 보이는 것처럼 색칠된 루트를 따라가게 될 것이다. 

그렇게 된다면 5 + 10 + 4 => 19 로, 위의 21보다는 작은 결과가 도출되게 된다. 

 

 

 

 

 

이 예시를 통해 본다면, 위에 언급했던것처럼 

그리디 알고리즘은 일반적인 상황에서 최적의 해를 보장할 수 없을때가 많다.

 

 

 

---

 

 

 

 

 

따라서 그리디 알고리즘을 공부하면서 내가 내린 결론은,,,

 

 

 

1. 코딩 테스트에서 그리디 알고리즘으로 최적의 해를 도출할 수 있는 문제 유형들을 뽑아서 연습하고, 익혀놓자
2. 그리디 알고리즘을 적용해서 문제를 해결할 때는 항상 최적의 해가 맞는지 아닌지를 확인하는 '정당성 검토' 과정을 거치자

 

 

 

 

 

그리디 알고리즘 문제풀이 =>

2022.12.23 - [백준 알고리즘] - [알고리즘] 그리디 알고리즘 - 백준 11047 파이썬 문제풀이: 동전 0

[알고리즘] 그리디 알고리즘 - 백준 11047 파이썬 문제풀이: 동전 0