그리디 알고리즘은 무엇이고 어디에 써야할까?

그리디 알고리즘이란?

현재 상황에서 가장 최적의 선택을 하는 알고리즘 (미래를 고려하지 않음)

 

그리드 알고리즘으로 문제를 푸는 방법

• 문제를 읽고 항상 현재 상황에서 최적의 선택을 하면 전체적으로도 최적의 선택이 될 수 있을까를 고려한다.
• 탐욕 조건(Greedy Chocie Property)과 최적 부분 구조(Optimal Substructure)가 있는 지 확인한다.
  • 탐욕 조건: 현재 상황에서 당장 최선이라고 생각한 선택이 결과적으로 전체에서도 최선의 선택이 된다는 성질
  • 최적 부분 구조: 전체 문제의 최적해(optimal solution)가 부분 문제의 최적해(optimal sub-solutions)로 구성될 수 있는 성질
• 정렬 또는 우선순위 설정
  • 가장 좋은 선택을 판단할 기준을 설정한다.
  • 기준에 맞게 데이터를 정렬 혹은 Priority Queue(Heap)을 쓴다.

 

그리드 알고리즘 문제 예시

• 동전 거스름돈
• 회의실 배정
• 최소 신장 트리 (크루스칼)
• 작업 스케줄링
• 문자열 만들기

 

기본 코드 구조

function greedyAlgorithm(data) {
  // 1. 정렬: 문제에 따라 기준을 잡아서 정렬
  data.sort((a, b) => {
    // 정렬 기준: 필요에 따라 수정
    return a - b; 
  });

  // 2. 초기화
  let result = 0; 

  // 3. 로컬 최적 선택 반복
  for (let i = 0; i < data.length; i++) {
    if (/* 현재 상황에서 가장 좋은 선택 */) {
      // 선택할 때 처리
      result += /* 선택한 값 */;
    }
  }

  // 4. 결과 반환
  return result;
}