[SCCC 스터디] 8일차 그리디

SCCC 스터디 8일차 1月 22日

그리디도 어렵다..

그리디는 Greedy로 탐욕 알고리즘이라 불린다. 현재 선택이 나중 선택에 영향을 미치지 않게 고르는 것이다.

디피랑 그리디에 대한 자세한 개념은 라이님 블로그, 나동빈님의 블로그에 잘 설명 되어있으니 거기서 개념을 보는게 좋다. (난 여기에 쓰는건 그냥 간단히 일기장처럼 쓰는 것이여서 개념보단 문제 리스트를 올리는 것이다.)

그리디 알고리즘의 종류가 있다. (여기서 내가 아는건 거.....의 없다....)

1. Fractional Knapsack Problem (=> 거스름돈 문제)

2. 시간표 배정

3. 수학적 성질이 최적해를 보장하는 경우

4. Huffman Code

5. 다익스트라

6. MST(Kruskal, Prim)

7. 최대 유량

1. 동전 0 - ●○○○○ 

2. 회의실 배정 - ●●○○○

3. ATM - ●○○○○

4. 로프 - ●●○○○

5. 강의실 배정 - ●●◐○○

6. 시험 감독 - ●●○○○

7. 신입 사원 - ●●○○○

8. 캠핑 - ●●○○○

9. 멀티탭 스케줄링 - ●●◐○○

10. DNA - ●◐○○○

11. 수리공 항승 - ●●●○○ ( or ●●●◐○)

12. 모두의 마블 - ●◐○○○

13. 공주님의 정원 - ●●●○○

14. 센서 - (아직 안 품)

15. 30 - ●●○○○

16. 택배 - (아직 안 품)

17. 과제 - ●●●◐○

18. 소트 - ●●●◐○