[알고리즘] Greedy(탐욕법)

Greedy Algorithm (탐욕)

• 정의 : 매 선택에서 지금 이 순간 당장 최적인 해를 구함.
  • 동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용.
  • 근시안적으로 해를 구할 당시에 가장 최적인 해를 구함.
  • 동적 계획법처럼 반드시 최적의 해를 구한다는 보장이 없다.
  • 한번의 선택이 다음 선택에서는 전혀 무관한 값이여야 하는 매순간의 최적해가 문제의 최적해.
• 과정
  1. 선택 : 현 상태에서 최적해에 포함시킬 대안을 선택
  2. 타당성 조사 : 선택된 해가 주어진 문제의 조건을 만족하는지 검사
  3. 해답 조사 : 원래의 문제가 해결되었는지를 조사
• WHEN?
  • 탐욕 알고리즘을 사용해 최적의 답을 구할 수 있다는 것이 쉽게 보이면
  • 탐욕 알고리즘을 사용할 수 있는지가 의심스럽고 다른 알고리즘으로 답을 구할 수 있는 경우 사용X
  • 탐욕 알고리즘 이외에 제한 시간 내에 문제를 풀 수 있는 알고리즘이 생각나지 않을 경우에는 탐욕 알고리즘으로 최적의 답을 구할 수 없는 반례를 찾아보고 발견되지 않으면 구현
  • 경험 중요!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

해밀턴 경로

• 구현 포인트
  1. 갈래가 나뉘어지는 도시 확인(y가 3이상이면 0리턴)
  2. 순환되는 경로가 있는지 확인(y를 2개 포함하고 이전 도시와 다음도시가 y 1개가 있는경우)
  3. 반드시 통과해야 하는 경로의 수를 얻는다. (메모해야됨)
  4. 자유롭게 이동할 수 있는 도시 수 (y를 포함하지 않는 열의 수를 세면 얻을 수 있다.)
  5. 효율 업! (y를 1개만 포함하고 있는 도시 사시의 도시가 y를 2개 포함하고 있다면 반드시 거쳐야 하는 경로- y를 1개만 포함하고 있는 도시의 수를 세면 반드시 거쳐야 하는 경로!!!)