2021년 8월 24일에 작성된 문서 2번 입니다.
자료 구조 배운 내용을 정리했습니다.
Greedy Algorithm
말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있습니다.
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.
greedy algorithm 예시 01
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다. 이때 김코딩은 어떻게 거슬러 주어야 할까요?
탐욕 알고리즘으로 동전의 개수를 헤아리는 일은, 우리가 거스름돈으로 동전을 선택하는 방법과 같다.
- 거스름돈 960원을 채우기 위해서 먼저, 500원짜리 동전을 한 개 선택.
- 100원짜리 동전을 네 개 선택
- 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택.
위의 과정에 탐욕 알고리즘을 적용하면,
- 선택 절차 :
- 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택.
- 적절성 검사
- 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사.
- 초과하면 가장 마지막에 선택한 동전을 삭제 후, 1번으로 돌아가 한 단계 작은 동전을 선택.
- 해답 검사 :
- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사.
- 액수가 부족하면 1번 과정부터 다시 반복.
이 과정을 통해 얻은 문제에 대한 해답은 다음과 같습니다.
가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.
greedy algorithm 예시 02
김코딩이 아르바이트를 하러 간 사이에, 안타깝게도 김코딩의 집에 도둑이 들었습니다. 도둑의 가방은 35kg까지의 물건만 담을 수 있고, 김코딩의 집에는 4개의 물건이 있습니다.
탐욕 알고리즘
- 가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다.
- 그다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다.
- 이 과정을 반복합니다.
- 가방은 35kg까지 담을 수 있고, 그림이 가장 비싸 그림을 먼저 가방에 담을 수 있다.
하지만 남는 공간이 5kg밖에 남지 않아 더 훔칠 수 있는 물건이 없다.
이때 훔친 물건의 총 가치는 그림 하나의 가치와 같은 $3,000.
만약 그림 대신 컴퓨터와 반지를 가방에 담았다면 어떨까?
- 35kg이 넘지 않으면서 총 가치는 $3,500으로 그림 하나만 훔칠 때보다 더 많은 가치의 물건을 훔칠 수 있다.
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식입니다. 그러나 도둑의 예와 같이 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 합니다.
탐욕 알고리즘을 적용하기 위한 조건
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.
Written with StackEdit.
