[Algorithms/python] Greedy Algorithm

 

 

자료구조의 선택

• 각각의 값이 서로 다른 값에 영향을 주지 않을 것
• 그리디 알고리즘으로 풀어낸 값이 모든 경우의 수에서 최적의 해일 것
• 주어진 상위의 값이 하위 값의 배수일 것
• 그리디 알고리즘은 현재 상황을 기준으로 적합한 해를 찾는 방법이지 최적의 해를 찾는 방법은 아니다.
  • 최적의 해를 찾기 위해서는 동적계획법(Dynamic Programming)을 사용한다.

 

 

Greedy VS DP

 

 

Greedy 문제 해결 방안 

 

• 나열된 값의 정렬이 매우 중요하다. 
  • 즉, 경우의 수(주어질 지, 내가 만들어야될지는 모르겠지만)를 잘 정렬하여 현재 상황이 원하는 순서대로 나타날 수 있도록 해야한다.

1. 문제의 최적의 부분 문제를 결정한다
2. Prove that it is always safe to make the greedy choice
3. Greedy 전략을 위한 재귀 알고리즘 

 

 

가장 유명한 예시로 푸는 패턴을 적용해보자면...  문제의 최적의 부분 문제를 결정한다 -> 즉 어떤 순으로 정렬해서 문제를 풀어야 최적일지 결정한다  1. 회의실을 짧게 쓰는 순서대로 정렬한다: X 2. 먼저 시작하는 순으로 정렬한다: X 3. 회의 종료 시간 기준 오름차순 정렬한다 : O Prove that it is always safe to make the greedy choice Greedy 전략을 위한 재귀 알고리즘

 

 

 

개념 정리

• 최적화 문제에서 쓰는 전략
  • 매 step마다 최선으로 보이는 선택 
  • 하지만 항상 최적의 해를 선택하지는 않는다 
  • 대부분 top-down (선: 선택 / 후 : 부분 문제)방식을 사용한다
    • ↔ DP의 bottom up (선 : 부분 문제 / 후 : 선택 )
• 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다.
  1. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며
     • 어떤 알고리즘이 이 속성에 해당하는 경우, 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 사는 길 중 하나다 -> 탐욕적 선택에 손해가 없다 
  2. 매 순간의 최적해(== 부분 문제의 최적해)가 전체 문제에 대한 최적해여야 한다는 의미이다.
• 많은 문제에 대해서 강력하다 
  1. Activity Selection Problem : 최대 몇 개의 활동 가능 ? 
  2. Minimum spanning tree (최소 신장 트리 )
     1. Prim Algorithm
     2. Kruskal Algorithm
  3. Fractional Knapsack Problem
  4. Huffman Codes
  5. Dijkstra's algorithms (for shortest paths from a single source)
  6. Set-cover heuristic

 

 

 

https://github.com/AAISSJ/AlgorithmStudy/blob/main/README.md

GitHub - AAISSJ/AlgorithmStudy: [2022.11 ~] Problem Sloving with algorithms ✍️

 

 

Reference

https://www.dongyeon1201.kr/c7ebdce4-043c-4d21-ad9b-af003db87adb#0ae8fcbc-d634-4416-bb90-ea1aebd03872

알고리즘 문제 풀이 팁