프로그래머스 코딩 테스트 고득점 Kit의 탐욕법 카테고리를 풀기 시작하면서 그리디 알고리즘에 대해서 정리해본다.
-그리디(탐욕법) 알고리즘이란?
그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다고 한다.
그리디 알고리즘이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘이다.
즉, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에서 현재 당장 최적이라고 생각되는 것을 선택해 나가는 식으로 진행하여 최종적인 해답에 도달한다.
백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다.
그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택해나가는 방식이지만 이 가장 좋은 결과는 최종적인 결과 도출에 대한 최적해를 보장해주는 것은 아니다!
-그리디 알고리즘이 추구하는 가장 좋은 것(최선의 선택) 이란?
시작 지점에서 부터 시작, 가장 큰 수를 구하는 문제에서 그리디 알고리즘을 사용한다면
우리는 가장 좋은 결과(최적해)가 "시작 - 6 - 128" Path가 가장 큰 수를 도출할 수 있다는 것을 알 수 있다.
하지만 그리디 알고리즘은 시작 지점에서 부터 가장 큰 수를 얻는 Path인 '17'을 선택하게 된다.
결론적으로 그리디 알고리즘은 "시작 - 17 - 23" Path가 가장 좋은 것이라고 판단한다.
최초의 선택에서 최적 선택을 하여 부분 최적해는 구했지만 전체 선택에서는 오히려 최적이 아닌 경로를 선택하여 전체 문제에서의 최적값은 구하지 못하게 된 것이다.
이처럼 그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택하는 방식이다.
그럼에도 불구하고 그리디 알고리즘은 속도가 매우 빠르기 때문에 자주 사용될 수 있다. 그리고 그리디 알고리즘을 사용하는 문제는 간단한 문제로 나올 가능성이 매우 크다. 하지만 항상 최적해가 되지 않으므로 특수한 조건이 만족되어야 사용할 수 있다.
-그리디 알고리즘을 사용하기 위해 필요한 2가지 조건
1. 탐욕스러운 선택 조건
탐욕적인 선택이 항상 안전하다는 것이 보장되어야 한다.
여기서 "안전하다"는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것.
그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아니다!
하지만 그리디 알고리즘을 사용해 푸는 문제가 나왔을 때 이 조건이 만족되는가? 를 생각해 충족되면 그리디 알고리즘을 사용하는 것이다.
즉, 그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제에서 사용해야 한다.
2. 최적 부분 구조 조건
부분문제의 최적결과가 전체에도 그대로 적용될수 있어야 한다.
문제에 대한 최종 해결 방법이 부분문제에 대해서도 또한 최적의 해결 방법이라는 조건이다.
전체 문제 안에 여러 단계가 존재하고, 이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다는 것이다.
그리디 알고리즘에서 고려해야 하는 상황은 값들이 서로 영향을 주면 안된다는 것을 염두에 두어야 한다. 이전의 선택이 이후에 영향을 주지 않음을 의미한다. 위에서 사용한 예시를 한번 더 사용해 설명하자면
- 그리디 알고리즘이 도출한 최종 Path는 "시작 - 17 - 23" 이다.
이때 "6" 아래의 "128"이라는 값이 있어서 Path를 변경할 수 없다는 것이다.
-그리디 알고리즘을 사용해야 하는 문제들
앞에서 말했듯이 그리디를 사용하려면 이 방법이 최선이다 라는 근거가 있어야 하고 그리디를 사용한 방법이 정답이라는 보장이 되어야 사용할 수 있다.
그래서 모두 그런것은 아니지만 그리디 문제는 일반적으로 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다.
그리고 그리디를 사용할 수 있는 조건이 주어진다. 물론 이러한 조건은 문제 내에 숨겨져있어 찾아내야 하는 경우가 많다.
그리디 알고리즘
1. 일반적으로 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다.
2. 그리디를 사용할 수 있는 조건이 주어진다. (주로 문제를 읽고 조건을 찾아야한다.)
3. 정렬을 한 뒤 그것을 이용해 푸는 문제가 많다. (그리디 알고리즘 문제 예시로 유명한 최소의 개수로 사용해야하는 동전문제의 경우에도 동전을 내림차순으로 정렬한 뒤 하나 하나 사용해 나가야 할 것이다.)
-참고한 블로그
https://hongjw1938.tistory.com/172
알고리즘 - 그리디 알고리즘(Greedy Algorithm)
1. 그리디 알고리즘(Greedy Algorithm)이란? 간단히 설명해, 그리디 알고리즘은 "매 선택에서 현재 당장 최적인 답"을 선택해 전체 적합한 결과를 도출하자는 알고리즘 기법이다. 즉, 백트래킹을 통해
hongjw1938.tistory.com
https://sectumsempra.tistory.com/88
[C++ 알고리즘] 그리디(탐욕법,Greedy Algorithm)
개념 그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 실제 그리디 알고리즘을 검색하면 아래와 같이 나온다. 탐욕 알고리즘은
sectumsempra.tistory.com
-> 여기는 문제들도 상세히 나와있다.
탐욕법(그리디) 알고리즘
탐욕법(이하 '그리디') 알고리즘이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말합니다. 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많
velog.io
'코딩테스트 및 개인공부 > 알고리즘' 카테고리의 다른 글
| [강의정리] [연결리스트] 실전 알고리즘 0x04 정리 (0) | 2022.04.26 |
|---|---|
| [강의정리] [배열] 실전 알고리즘 0x03 정리 (0) | 2022.04.22 |
| [알고리즘] 완전탐색 (Exhaustive Search) (0) | 2021.07.06 |
