알고리즘 강의 3주차 - 그리디 알고리즘

1. 그리디 (Greedy) 알고리즘
   • 최적화 문제를 해결하기 위한 알고리즘
   • (입력) 데이터 간의 관계를 고려하지 않음
2. 최소 신장 트리 (Minimum Spanning Tree)
   • 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리
3. 최단 경로 (Shortest Path) 문제
   • 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제
   • 다익스트라 (Dijkstra) 최단 경로 알고리즘이 대표적

 

• 그리디 알고리즘은 최적화 문제를 해결하기 위한 알고리즘, 가능한 값중 최대, 최소값을 찾는문제 
• 근시안적인 선택으로 부분적인 최적 해를 찾고, 모아서 최적 해를 찾는다.
• 번복하지 않는다. 단순한 특성을 보임. 제한적인 알고리즘

 

• 동전 거스름돈 - 남은 액수를 초과하지 않는 조건으로 '욕심내어' 가장 큰액면의 동전을 취하는것
• 최소 신장 트리 -  주어진 가중치 그래프에서 사이크이 없이 모든 점을 연결한 트리 중 가중치 합이 최소인 트리
  • 프림의 최소신장트리 알고리즘
• 최단경로 알고리즘 - 주어진 가중치 그래프에서 어느 한 출발점에서 도착점까지의 최단경로를 찾는 문제
  • 다익스트라Dijkstra 알고리즘 
    
    • 프림과의 차이점 - 프림은 임의의 점에서 시작, 다익스트라는 주어진 출발점에서 시작
  • 맵퀘스트와 구글 웹사이트의 지도 서비스
  • 자동차 내비게이션
  • 네트워크와 통신 분야
  • 모바일 네트워크
  • 산업 공학 등

 

1. 부분 배낭 문제
   • n개의 물건이 있을 때
     • 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
     • 물건을 부분적으로 담는 것을 허용
2. 집합 커버(Set Cover) 알고리즘
   • U의 부분 집합들을 원소로 하는 집합 F가 주어질 때
     • F에서 선택하는 집합들의 수를 최소화하는 문제
3. 작업 스케줄링 (Task Scheduling) 문제
   • 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제

 

• 부분 배낭 문제에 대한 그리디 알고리즘
  • n개의 물건이 있을때 각 물건은 무게와 가치를 가짐, 배낭이 한정된 무게의 물건을 담을수 있을때
  • -> 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
  • 물건을 부분적으로 담는것을 허용하는것이 부분 배낭 문제.
  • 가장 값비싼 물건을 넣고, 그다음으로 비싼 물건을 넣는다. 통쨰로 넣을수 없게되면 부분적으로 담는다.
• 집합 커버 알고리즘에 대한 그리디 알고리즘
  • 집합 커버 (Set Cover) 문제
  • n개의 원소를 가진 집합 U가 있고 U의 부분 집합들을 원소로 하는 집합 F가 주어질때, F의 원소들인 집합중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가?
• 작업스케줄링에 대한 그리디 알고리즘
  • 작업의 수행시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제
    • 작업의수
    • 각 작업의 시작시각과 종료시각
    • 작업 시작시각과 종료시각은 정해져있으므로 작업의 길이도 주어진것
    •