[알고리즘] 그리디 알고리즘

그리디 알고리즘

💡 언제 쓸까?

직관적으로 될 것 같을 때...
최대한 계산수를 줄이려고 생각하다 보면..

💡 포인트

• 해를 구하는 각 단계에서 지금 당장 가장 좋은 방법을 선택
• 최대한 탐색 범위를 줄여 계산수를 줄인다
  • ex. 배열의 경우 여러 번 탐색 대신 한 번만 탐색할 수 있지 않을까
    • for문으로 배열 여러번 탐색했는데 시간초과 나온다? 풀이를 뒤엎어야 할 확률이 큼! 좀더 획기적인 방법으로 계산수를 줄일 방법이 있을 것
    • 대부분 1번의 탐색으로 답이 확정될 수 있음(어떤 작업을 수행한 후 더이상 다시는 이 작업을 수행할 필요가 없음)

생소하고 어려운 그리디 알고리즘을 풀어보기보다는
알려진 그리디 알고리즘을 잘 이해하고 사용하는 연습을 하자

💡 최적해가 보장되는 예

• 다익스트라 알고리즘
  • 양의 가중치에서의 최단 경로
• 프림 알고리즘, 크루스칼 알고리즘
  • 최소 신장 트리(최소 스패닝 트리)

💡 연습문제

2212 센서
1946 신입사원
15903 카드 합체 놀이
1339 단어 수학
2437 저울