외않해?

ㄴ 했어요 ..

그리디 알고리즘

: 미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식

• 장점 : 간단하고 빠르다.

• 단점 : 최적의 답이 보장되지 않는다.

• 언제 그리디 알고리즘을 사용할까 ?

  • 문제를 해결하는 다른 알고리즘들이 너무 느려서 사용할 수 없는 수준일 때
  • 최적의 답이 필요 없을 때

• 최적의 답을 구해 주는 경우도 있다 ! - 문제에서 두 가지 조건을 찾으면 됨

  1. 최적 부분 구조 : 어떤 문제에 최적 부분 구조가 있다는 건, 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것

  2. 탐욕적 선택 속성 : 각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택

  → 둘 다 갖춘 문제라면, 이 문제는 그리디 알고리즘이 최적의 솔루션을 보장

• 예시 : 500원, 100원, 50원, 10원짜리 동전이 있다고 가정 → 최대한 적은 동전을 사용해서 돈 거슬러 주는 알고리즘 구현

  1. 최적 부분 구조 확인

     예시) 1700원을 거슬러 준다고 가정

     • 첫 동전으로 500원 -> 1200원 거슬러 주기

     • 100원 -> 1600원

     • 50원 -> 1650원

     • 10원 -> 1690원

     • 이 부분 문제들에 대한 최적의 답을 구하고, 이 4가지 경우를 비교하면 기존 문제의 최적의 답을 구할 수 있음 → 이 문제는 최적 부분 구조가 있음

  2. 탐욕적 선택 속성 확인 : 매 순간마다 최대한 큰 동전을 고를 수 있음

     예시) 660원을 거슬러 준다고 가정

     • 처음에 선택할 수 있는 가장 큰 동전은 500원 -> 160원 -> 줄 수 있는 가장 큰 동전은 100원 -> 60원 -> 줄 수 있는 가장 큰 동전은 50원 -> 10원 -> 줄 수 있는 가장 큰 동전은 10원 -> 끝

     • 100원짜리 5개 줄 바에 500원 짜리 1개 준다

     • 50원짜리 2개 줄 바에 100원 짜리 1개 준다

     • 10원짜리 5개 줄 바에 50원 짜리 1개 준다

     • 가능한 가장 큰 동전으로 거슬러주는 게 무조건 좋다 → 이 문제는 탐욕적 선택 속성이 있음

  → 따라서 이 문제를 그리디 알고리즘으로 풀면 최적의 답이 보장