[알고리즘] 그리디 Greedy Algorithm

1. Divide and Conquer

- 같은 일을 반복할 수 있음

- bottom -> top

2. Dynamic progamming

1) Optimal substructure

  :  Problem에 대한 최종 Solution은 Sub problem에 대한 Optimal Substructure (최적 문제 해결 방법)으로 구성

 

문제의 최적해가 부분문제의 최적해로 구성된 것을 일컫는다.

쉽게 말해서 전체 문제의 답은 서브 문제의 답으로 구성된다는 것

 

2) Overlapping problems

테이블에 저장해두고 자주 봄

중복 사용하니까 - overlap.

[알고리즘] Dynamic Programming (동적계획법)

- 같은 일을 반복x 한번만 함 (- list에 저장하면서 진행)

- 재 계산하는 일이 없으므로 divide and conquer보다 빠름 (?)

- top -> down

출처 : 한동대학교 알고리듬 분석 강의

>문제

1. Matrix Chain Multiplication: O(n^3) (정확히는 세타)

2. Longest common subsequence: O(mn)

3. Optimal binary search trees : O(n^3) - 다루진 않았음.

 

---

 

3. Greedy Algorithm

: 탐욕 알고리즘이란 매순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법

- local optimal한 해만 채워 나가는 문제 해결법 (global 한 해를 생각하는게 아님)

1. Greedy Choice Property : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

내가 global한 그림 따위는 집어치우고

오직 locally optimal 선택만을 하는데

그게 모아보니 globally optimla 한 (!!) 특성을 가진다는 것이다. 

 

  2. Optimal Substructure :  문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

> 탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

> 예시

 

동전 거스름돈

 

740원 - 500원, 50원, 10원

10원짜리 740개보다는 500원1개 (240원 거스름돈) - 50원 4개(40원 거스름돈) - 10원 4개

1. 선택 절차 : 500원 선택

• 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.

2. 적절성 검사 :

• 1번 과정을 통해 선택된 동전들의 합이 거슬러  줄 금액을 초과하는지 검사
• 초과하면 가장 마지막에 선택한 동전 삭제, 1번으로 돌아가 한 단계 작은 동전을 선택

3. 해답 검사

• 선택된 동전들의 합 거슬러 줄 금액과 일치하는지 검사
• 액수 부족하면 1번 과정부터 다시 반복

 

참고 블로그 : 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

https://jangu5000.tistory.com/entry/알고리즘-Greedy-Algorithm-그리디-알고리즘

[알고리즘] Greedy Algorithm (그리디 알고리즘)