그리디(Greedy) 알고리즘

그리디 알고리즘(Greedy Algorithm)이란 "지금 당장 눈앞에 보이는 최선의 선택을 한다"는 전략이다.

계산이 빠르고 구현이 쉽다는 장점이 있지만, 항상 최적의 답을 보장하지 않는다.

그래서 다음 두 가지 조건이 만족될 때 주로 사용한다.

1. 탐욕적 선택 속성
지금 한 선택이 나중에 영향을 주지 않아야 한다.
즉, 지금 최선을 다하면 전체적으로도 최선이 되어야 한다는 확신이 있어야 한다.

2. 최적 부분 구조
작은 문제의 최적해가 모여서 전체 문제의 최적해가 되는 구조여야 한다.

그리디는 가장 ~한 것을 고르기 때문에 정렬과, 우선순위 큐를 자주 사용한다.

문제 (강의실 배정)

백준 11000번 강의실 배정

풀이

시간의 흐름에 따라 모든 수업을 배치해야 하므로, 시작 시간순으로 정렬하여 앞에서 부터 검사

강의실을 배치할 때 우선순위 큐를 활용하여 현재 사용중인 강의실 중 가장 빨리 끝나는 방과 비교

import java.util.*;

class Time implements Comparable<Time>{
	int start;
	int end;
	
	public Time(int start, int end) {
		this.start = start;
		this.end = end;
	}
	
	@Override
	public int compareTo(Time t) {
		if(this.start == t.start) return this.end - t.end;
		return this.start - t.start;
	}
}

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		List<Time> list = new ArrayList<>();
		for(int i=0; i<n; i++) {
			int start  = sc.nextInt();
			int end = sc.nextInt();
			list.add(new Time(start, end));
		}
		Collections.sort(list);
		
        //현재 사용중인 강의실의 끝나는 시간 담을거임
        //빨리 끝나는거 먼저 꺼내서 다음 강의 시작 시간이랑 비교해야 하니깐
        //최소힙으로 사용
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		int answer = 0;
		for(Time t : list) {
			if(pq.isEmpty()) {
				pq.offer(t.end);
				answer++;
			}
			else if(pq.peek() > t.start) {
				pq.offer(t.end);
				answer++;
			}
			else if(pq.peek() <= t.start){
				pq.poll();
				pq.offer(t.end);
			}
		}
		System.out.println(answer);
	}
}

문제 (크게 만들기)

백준 2812번 크게 만들기

풀이

앞자리가 클수록 전체 수가 크기 때문에, 숫자를 하나씩 확인하며 현재 숫자 뒤에 더 큰 숫자가 오면 과감히 지운다.

스택을 사용하여 현재 숫자가 앞에 있던 숫자들보다 큰지 작은지 확인하며 지운다.

k번을 다 못지우고 끝났을 경우도 있으니 처리한다.

숫자를 문자열로 받아서 인덱스로 접근하여 효율성을 높인다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        String number = sc.next();

        Deque<Integer> stack = new ArrayDeque<>();
        
        int cnt = 0;
        for(int i=0; i<number.length(); i++){
            int cur = number.charAt(i) - '0';
            
            while(!stack.isEmpty()){
                if(stack.peek() >= cur || cnt == k) break;
                stack.pop();
                cnt++;
            }
            
            stack.push(cur);
        }
        
        while(!stack.isEmpty()){
            if(cnt == k) break;
            stack.pop();
            cnt++;
        }
        
        StringBuilder sb = new StringBuilder();
        
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        
        String answer = sb.reverse().toString();

        System.out.println(answer);
    }
}