02. 탐욕 알고리즘(Greedy)

1. 정의

   현재 위치에서 최적의 해를 찾는 알고리즘.

   즉, 현재 위치의 최선이  전체의 최선이라는 전제를 기반으로 한다.

 

2. 활용 제약조건

    현재 위치에서의 선택이 전체에 미치는 영향이 제한적이어야 하며,
    그 영향이 국소적인 범위 안에서 해결 가능해야 한다.

3. 사용 예시

• 체육복 문제 (±1 범위 내 대여)
• 회의실 배정 (가장 빨리 끝나는 회의 선택)
• 동전 거스름돈 (가장 큰 단위부터 사용)
• 다익스트라 알고리즘 (가장 가까운 정점부터 탐색)
• Kruskal, Prim (최소 비용 간선 선택)

   실 사용 예시 = > 네비게이션, 라우팅 알고리즘(OSPF)등...

 

4. 이해하기 쉽게 설명

    - 어렸을 적 오락실에서 게임을 떠올려 보자. 

      마지막에 랭킹 등록할 때, "AAA" 초기화가 된 것에서 1, 2, 3번째 글자를 입력할 때,
      앞으로 갔다가 뒤로 갔다가, 빠르게 입력하려고 노력했을 것이다.  

      1, 2, 3번째 입력하는 3가지의 경우를 각각 최적으로 입력하다보니 결론적으로 가장 빠르게 입력할 수 있다는 것.

      어렸을 때부터 그리디 알고리즘을 우리는 벌써 다루어 본 것이다.

 

 

 

5. 예제 코드 

//프로그래머스 : 조이스틱
//[전제 조건]
// 1. 문자열 자릿수에 맞처 'A'로 전부 초기화됨.
// 2. 문자열의 글자를 입력해야 하는데 A-Z까지 최적의 움직임으로 찾는 것.

class Solution {
    public int solution(String name) {
        int answer = 0;
        char[] charr = name.toCharArray(); 
        int count = 0;
        
        //상,하 이동 최적 계산 -> 단순 누적
        for(char res : charr){
            answer += Math.min(res - 'A', 'Z' - res + 1);
        }
        
        //좌우 최적 경로 찾기
        answer += getWide(name);    
        return answer;
    }
    // 그리디 : 좌우 최적 경로 찾기 
    // 최악의 해 : name.length - 1; => 정방향으로만 가는 경우
    // 돌아서 가는게 최악보다 최적일 경우 그 경로를 갱신하여 리턴함
    // JAEANE의 경우 -> 국소 최적을 검사하는 인덱스 -> E, N, E
    public int getWide(String name) {
        int len = name.length();
        int minMove = len - 1;

        for (int i = 0; i < len; i++) {
            int next = i + 1;
            //'A'는 바꿔줄 필요가 없으므로 건너뜀.
            while (next < len && name.charAt(next) == 'A') {  
                next++;
            }
            int move = i + i + (len - next); // 시작점(0) -> 오른쪽 -> 현재위치(i) -> 왼쪽 -> next  (정방향 진행 후 돌아가기)
            int reverseMove = (len - next) * 2 + i; // 시작점(0) -> 왼쪽 -> 오른쪽 -> 현재위치(i) (역방향 진행 후 돌아가기)
            minMove = Math.min(minMove, Math.min(move, reverseMove));  //최악보다 최적일 경우 리턴함.
	}
        return minMove;
    }
}

 

전략 : 좌/우 “이동” 최적화에 대한 그리디 전략

• 국소최적 : 바꿔야 할 문자 기준 ⇒ 정방향 진행 후 왼쪽으로 돌아가기 vs 역방향 진행 후 왼쪽으로 돌아가기
• 전체최적 : 정방향으로만 진행하기 vs 진행 후 돌아가기(국소최적)

//백준 : ATM
import java.util.Arrays;
import java.util.Scanner;

public class greedy_atm {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] wastetimes = new int[n];
        int sum = 0;
        int answer = 0;

        for(int i =0; i<n; i++){
            wastetimes[i] = sc.nextInt();
        }
        Arrays.sort(wastetimes);
        for(int i=0; i<n; i++){
            sum += wastetimes[i];
            answer += sum;
        }
        
        System.out.println(answer);
    } 
}

전략 : 시간[크기] 최적화에 대한 그리디 전략

   * 국소 최적 : Arrays.sort(wastetimes); → 작은 시간부터 정렬 후 구하는 것이 최적

   * 전체 최적 : sum += wastetimes[i], answer += sum (대기기간 누적)

 

//백준 : 한줄로 서기
import java.util.*;

public class greedy_linearray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] memlist = new int[n]; //각 번호사람 : 기억하는 왼쪽사람 수
        int[] answer = new int[n];

        //기억하는 사람수 입력
        for (int i = 0; i < n; i++) {
            memlist[i] = sc.nextInt();
        }
        //answer -> 사람번호 재배치
        for (int i = 0; i < n; i++) {
            int cnt = 0;            //
            int pnum = i + 1;       //사람번호
            //빈자리인지 연속 탐색
            for (int j = 0; j < n; j++) {
                if (answer[j] == 0) {           // 빈 자리인지 검사
                    if (cnt == memlist[i]) {    // 중복될 경우 1개씩 cnt 증가
                        answer[j] = pnum;
                        break;
                    }
                    cnt++;
                }
            }
        }

        for (int res : answer) {
            System.out.print(res + " ");
        }
    }
}

전략 : 인덱스 기반 순서 배치 그리디 전략

* 국소 최적 : 내 앞에 큰 사람 수만큼 현재 위치에서 먼저 배치함. (다음사람은 한칸 밀어버림)

* 전체 최적 : 국소 최적을 만족하면 결론적으로 앞에 정의된 큰사람만큼 정렬됨.