📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

TIL (this week I learned)
월 😴
화 개념정리, 몸풀기

시간 관리 참 어렵다..

16-1 그리디 개념 ⭐⭐

그리디 알고리즘이 최적해를 보장하려면?

• 아래의 특정한 상황에서는 그리디 알고리즘이 최적해를 보장한다.
  • 최적 부분 구조(optimal substructure): 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
  • 그리디 선택 속성(greedy selection property): 선택 과정이 다른 과정에 영향을 주지 않음
• 한계; 항상 최적해를 도출하지는 못 함.
• 그럼에도 빠른 시간 내에 근사해를 제공하는 효율적인 방법 중 하나

16-2 최소 신장 트리

신장 트리(spanning tree)

모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프

최소 신장 트리(minimum spanning tree, MST)

• 간선의 가중치 합이 최소
• 실생활 예: 항공기의 운항 경로를 최적화 할 때

최소 신장 트리를 구하는 그리디 알고리즘

1. 프림 알고리즘(prim's algorithm)

• 임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식
• 시간복잡도: $O(E*logV)$, 인접리스트 활용 시 $O(N^2)$
  
  (출처: wiki)

2. 크루스칼 알고리즘(Kruskal's algorithm)

• 시간복잡도: $O(E*logV)$
• 최소 가중치를 가지는 간선부터 하나씩 추가하는 방식
  
  (출처: wiki)

16-3 배낭 문제(knapsack problem)

짐을 쪼갤 수 있는 부분 배낭 문제(fractional knapsack problem)

1. 무게당 가치 계산
2. 무게당 가치가 높은 짐을 먼저 배낭에 넣음(최적 부분 구조)
3. 무게가 덜 찼을 떄, 그 다음으로 가치가 높은 짐을 넣음

• 앞에 선택한 짐이 다른 짐 선택에 영향을 주지 않으므로 그리디적 선택 요소
• 시간복잡도(짐의 갯수 N, 가치 W): $O(N*logN)$

짐을 쪼갤 수 없는 0/1 배낭 문제(0/1 knapsack problem)

• 그리디 알고리즘으로 최적의 해를 구할 수 없음
• DP 접근
• 배낭 짐들의 가치의 합이 최대가 되도록 함
• 시간 복잡도: $O(N*W)$

16-4 문제

1. 예산

https://school.programmers.co.kr/learn/courses/30/lessons/12982

2. 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

3. 귤 고르기

https://school.programmers.co.kr/learn/courses/30/lessons/12979

추천문제

1. 체육복
   https://school.programmers.co.kr/learn/courses/30/lessons/42862

2. 단속 카메라
   https://school.programmers.co.kr/learn/courses/30/lessons/42884

3. 큰 수 만들기
   https://school.programmers.co.kr/learn/courses/30/lessons/42883