그리디 알고리즘

최대환·2021년 11월 23일
0

알고리즘

목록 보기
4/8

개념

  • 그리디 알고리즘이란 지금 당장 좋은 것만 고르는 방법
  • 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올리는 능력을 요구
  • 그리디 해법은 그 정당성 분석이 중요(단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야함)

동전던지기

800원인데 동전이 500,400, 100원이면?

예제 - 최댓값 구하기

사실 지금은 값이 많지 않기 때문에 바로 5, 7, 9 의 값이 21로 가장 크다는걸 알 수 있다.

다만 이를 매 상황에서 가장 큰 값만 고르는 그리디 알고리즘을 짠다면 답이 틀리게 된다. 즉 그리디 알고리즘이 항상 최적을 보장하지 않음을 나타낸다.

그럼으로 그리디 알고리즘을 사용할 때에는 해당 아이디어를 내고 항상 이게 정말 전체를 대변할 수 있는 알고리즘인가 하고 정당성 분석을 해야한다.

그리드 알고리즘 사용시 중요사항

어떠한 문제를 보고 이 문제를 풀 수 있는 아이디어를 내고 이게 정당한지 확인하는게 중요하다. 그렇지 않으면 아래의 그래프 처럼 특정상황에서만 맞고 전체로 보면 틀린 상황이 벌어질 수가 있다.


아래와 같이 이 방법이 전체를 구할 수있는 방법인지 판별하는게 중요하다.

그리디 알고리즘을 사용해도 최적의 해에 가까운 값을 얻을 수 있을 때 혹은 최적의 값을 구할 수 있을 때 사용한다.
사실 일반적인 상황에서는 최적의 해를 구하기 힘들지만 알고리즘 문제 같은경우에는 설계자체를 딱떨어지게 설계를 해놨기 때문에 제대로된 방법론만 사용하면 최적의 해를 구할 수 있게끔 만들어 놓았다고 한다.

그리디 알고리즘 사용시기

  • 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
  • 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며(DP와 반대다), 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

탐욕 알고리즘(Greedy Algorithm) vs 동적 계획법(Dynamic Programming)

탐욕 알고리즘

  • 한번 선택하고 나면 번복하지 않는다. (그 순간의 최적을 선택)
  • 항상 최적해를 보장하지는 않는다. (정당성 증명 과정을 반드시 거쳐야 함)
  • 대게 동적 계획법보다 더 빠른 성능을 보인다.

동적 계획법

  • 전체 단계를 마치고, 최적해를 찾기 위해 재고하는 단계를 거친다.
  • 항상 최적해를 보장한다.

레퍼런스

참고영상
참고영상
참고블로그

profile
나의 개발지식 output 공간

0개의 댓글