SW 문제해결 응용 - 구현 - 탐욕알고리즘

하루입니다.

 

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3FuEG6AMkBBAQ3 

SW Expert Academy

 

---

 

학습 목표

1. 탐욕 알고리즘 기법의 개념과 특징에 대해 설명할 수 있다.
2. 탐욕적 선택이 항상 최적해를 찾는다고 보장할 수 없음을 파악할 수 있다.
3. 최적화 문제가 탐욕적 선택 속성과 최적 부분구조를 가질 때 탐욕 기법이 적용 가능하다는 것을 설명할 수 있다.

 

1. 탐욕 알고리즘

2. 동전 거스름돈 문제

3. 배낭 문제

4. 활동 선택 문제

5. 베이비진

 

---

1. 탐욕(Greedy) 알고리즘

• 최적화 문제를 해결하는 알고리즘이다.
• 근시안적 방법이다.
• 최적의 값을 구하는 문제로, 하나의 문제에 여러 해가 있을 수 있다.
• 생각 후 검증 없이 바로 구현하면 탐욕 접근이다.
• 여러 경우 중 하나를 선택할 때, 그 순간 최적이라고 생각되는 것을 선택하는 방식으로 최종적인 해답에 도달한다.
• 한번 선택된 것을 번복하지 않는다.
• 단순하며 제한적인 문제들에 적용된다.
• 각 결정별로는 최적이나, 선택을 모아 해답을 만들었으므로 항상 최적이라는 보장은 없다.

 

동작 과정

1. 부분 문제의 최적해를 구해서 부분 해 집합에 추가한다.
2. 현재 상태에서 최선이라고 여겨지는 선택을 추가한다.
3. 실행 가능성을 검사한다.
4. 새로운 부분해 집합의 실행가능 여부를 확인하고, 문제의 제약 조건 위반 여부를 검사한다.
5. 해를 검사하고, 새로운 부분해 집합이 문제의 해가 되는지 확인한다.
6. 전체 문제의 해가 완성되지 않은 경우는 해 선택부터 다시 시작한다.

 

 

---

2. 동전 거스름돈 문제

손님에게 거스름돈을 동전으로 줄 때, 동전의 갯수를 어떻게 해야 최소로 할 수 있을까?

 

 

 

---

3. 배낭 문제

앗! 도둑이다!

도둑이 훔친 물건을 배낭에 담으려고 한다. 어떻게 담아야 가장 가격이 높게 담을 수 있을까?

 

으에?

 

 

Knapsack 완전 검색 방법과 탐욕적 방법

 

 

Fractional knapsack 방법

 

 

 

 

 

---

4. 활동 선택 문제

 

 

탐욕 기법 적용

크기가 줄어든 하위 문제를 사용하여 문제를 해결하는 것을 Top-Down 방식의 문제 해결이라고 한다.

 

 

 

 

 

탐욕 기법 검증

 

 

 

---

5. 베이비진 다시보기!

베이비진 문제에 탐욕 기법 적용하기

 

 

---

 

 

휴 역시 수학적 개념이 나오면 어려워 ( •︠-•︡ )