[코딩테스트/알고리즘 맛집] 그리디 알고리즘 (Greedy Algorithm) 으로 빠르고 효율적으로!

그리디 알고리즘(Greedy Algorithm)

개요

greedy
형용사 - 1. 탐욕스러운 2.욕심 많은 

 

그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다.

•  코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형
• 지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함
• 탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족

✅ 동적 프로그래밍(Dynamic Programming)과 차이점 

• DP는 부분 문제의 해결 결과를 저장하며 최적해를 찾음
• Greedy는 매 선택이 최적해로 가는 과정이라 가정하고 탐

✅ 그리디 알고리즘을 사용 할 수 있는 조건

• 탐욕적 선택 속성(Greedy Choice Property)
   - 현재의 선택이 이후 선택에 영향을 주지 않고 최적해를 보장해야 한다.
• 최적 부분 구조(Optimal Substructure)
   - 부분 문제의 최적해가 전체 문제의 최적해를 구성할 수 있어야 한다.

✅ 코딩테스트 문제 유형

• 거스름돈 문제
• 활동 선택 문제(Activity Selection Problem)
• 프림(Prim) 알고리즘 (최소 신장 트리)
• 크루스칼(Kruskal) 알고리즘 (최소 신장 트리)
• 다익스트라(Dijkstra) 알고리즘 (최단 경로)

 

예제 1 - 거스름돈

당신은 마트에서 계산을 하는 점원이 되었습니다.  손님에게 거슬러줘야할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하세요. 이때 거스름돈으로 사용할 동전은 500원, 100원, 50원, 10원으로 무한히 존재하고, N은 10의 배수로 가정합니다.

 

입출력 예

입력 예시	출력 예시
1,460	8
1,890	11

 

요점

• 최소 개수를 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 준다.

 

소스코드

package Algorithm_01_Greedy;

import java.util.Scanner;

public class Q01_1_change {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int total = sc.nextInt();
		int minCoinCnt = 0;
		int coins [] = {500, 100, 50, 10};
		for (int coin : coins) {
			minCoinCnt += (total/coin);
			total %= coin;
		}
		System.out.println("result = " + minCoinCnt);
		sc.close();
	}

}

 

예제 2 - 큰 수 만들기

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 
만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

출력 조건

• 첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

요점

• 앞자리부터 탐색하며 제거할 수 있는 숫자는 최대한 제거하여 큰 숫자가 앞에 오도록 greedy하게 선택한다. (스택을 활용하여 앞 숫자보다 큰 숫자가 오면 이전 숫자를 제거)

 

소스 코드

package Algorithm_01_Greedy;

import java.util.Stack;

public class Q01_2_TheLargestNumber {

	public static void main(String[] args) {
		// 프로그래머스 
        System.out.println(solution("1924", 2)); // 출력: "94"
        System.out.println(solution("1231234", 3)); // 출력: "3234"
        System.out.println(solution("4177252841", 4)); // 출력: "775841"
	}

	public static String solution(String number, int k) {
		Stack<Character> stack = new Stack<>();

		for (char digit : number.toCharArray()) {
			while (!stack.isEmpty() && stack.peek() < digit && k > 0) {
				stack.pop();
				k--;
			}
			stack.push(digit);
		}
		
		while (k > 0) {
			stack.pop();
			k--;
		}
		
		StringBuilder answer = new StringBuilder();
		for (char digit : stack) {
			answer.append(digit);
		}
		return answer.toString();
	}

}

 

예제 3 - 단속카메라

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

 

입출력 예

routes	return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]	2

 

입출력예 설명

• -5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
• -15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

요점

• 진출 지점을 기준으로 오름차순 정렬한 후, 가장 먼저 단속카메라를 설치해야 하는 위치를 갱신하며 최소 개수의 카메라를 배치한다.

 

소스 코드

package Algorithm_01_Greedy;

import java.util.Arrays;
import java.util.Comparator;

public class Q01_3_Camera {

    public static void main(String[] args) {
        int[][] routes = {{-20, -15}, {-14, -5}, {-18, -13}, {-5, -3}};
        System.out.println(new Q01_3_Camera().solution(routes)); // 결과: 2
    }

    public int solution(int[][] routes) {
        // 카메라를 설치한 횟수
        int cameraCount = 0;

        // 이동 경로 종료 지점 기준으로 오름차순 정렬
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] route1, int[] route2) {
                return Integer.compare(route1[1], route2[1]); // 더 안전한 비교 방식
            }
        });

        // 설치된 카메라가 감시할 수 있는 마지막 위치
        int lastCameraPosition = Integer.MIN_VALUE;

        // 모든 차량의 경로를 순회하면서 카메라가 필요한 구간 찾기
        for (int[] route : routes) {
            if (lastCameraPosition < route[0]) { // 새로운 카메라 필요
                lastCameraPosition = route[1]; // 카메라를 현재 차량의 끝 지점에 설치
                cameraCount++; // 카메라 개수 증가
            }
        }

        return cameraCount; // 최종 카메라 개수 반환
    }
}

 

예제 4 - 구명보트

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

요점

• 몸무게가 가벼운 사람과 무거운 사람을 쌍으로 묶어 태우되, 무게 제한을 초과하지 않도록 투 포인터를 활용하여 최소한의 보트를 사용한다.

 

소스 코드 

package Algorithm_01_Greedy;

import java.util.Arrays;

public class Q01_4_Lifeboat {
    public static void main(String[] args) {
        Q01_4_Lifeboat lifeboat = new Q01_4_Lifeboat();
        
        int[] people1 = {70, 50, 80, 50};
        int limit1 = 100;
        System.out.println(lifeboat.solution(people1, limit1)); // Expected output: 3
        
        int[] people2 = {70, 80, 50};
        int limit2 = 100;
        System.out.println(lifeboat.solution(people2, limit2)); // Expected output: 3
    }

    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        
        int idx = 0; // 가장 가벼운 사람의 인덱스
        int answer = 0; // 필요한 구명보트 수

        for (int i = people.length - 1; i >= idx; i--) {
            if (people[i] + people[idx] <= limit) {
                idx++; // 가장 가벼운 사람도 태움
            }
            answer++; // 보트 사용
        }
        
        return answer;
    }
}

 

예제 5 -  체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

 

요점

• 여벌 체육복을 가진 학생을 번호순(오름차순)으로 정렬한 후, 여벌 체육복을 가진 학생이 앞번호(번호 -1) → 뒷번호(번호 +1) 순서로 빌려줄 수 있는지 확인한다. 앞번호 학생이 체육복이 없으면 먼저 빌려주고, 없으면 뒷번호 학생에게 빌려준다. 이렇게하면 최대한 많은 학생이 체육복을 가지도록 처리할 수 있다.

 

소스 코드 

package Algorithm_01_Greedy;

import java.util.Arrays;

public class Q01_5_Sportswear {

    public static void main(String[] args) {
        Q01_5_Sportswear sw = new Q01_5_Sportswear();
        
        int n1 = 5;
        int[] lost1 = {2, 4};
        int[] reserve1 = {1, 3, 5};
        System.out.println(sw.solution(n1, lost1, reserve1)); // Expected output: 5
        
        int n2 = 5;
        int[] lost2 = {2, 4};
        int[] reserve2 = {3};
        System.out.println(sw.solution(n2, lost2, reserve2)); // Expected output: 4
        
        int n3 = 3;
        int[] lost3 = {3};
        int[] reserve3 = {1};
        System.out.println(sw.solution(n3, lost3, reserve3)); // Expected output: 2
    }

    public int solution(int n, int[] lost, int[] reserve) {
    // 1. 체육복을 잃어버린 학생의 수에서 기본적으로 체육복을 가지고 있는 학생 수를 뺀 값으로 시작.
    int answer = n - lost.length;

    // 2. 잃어버린 학생과 여벌 체육복을 가진 학생의 배열을 정렬하여 빠르게 비교할 수 있게 함.
    Arrays.sort(lost);
    Arrays.sort(reserve);

    // 3. 같은 학생이 잃어버린 체육복과 여벌 체육복을 가지고 있을 경우, 그 학생은 체육복을 사용할 수 있음.
    for (int i = 0; i < lost.length; i++) {
        for (int j = 0; j < reserve.length; j++) {
            // 4. 잃어버린 학생과 여벌 체육복을 가진 학생이 같으면 그 학생은 체육복을 사용할 수 있음.
            if (lost[i] == reserve[j]) {
                answer++; // 체육복을 가지게 되므로 answer 증가
                lost[i] = -1; // 이미 처리된 학생은 -1로 표시하여 다시 처리되지 않게 함
                reserve[j] = -1; // 여벌 체육복을 가진 학생도 -1로 처리
                break; // 더 이상 비교할 필요 없음
            }
        }
    }

    // 5. 이제 잃어버린 학생에게 체육복을 빌려줄 수 있는 여벌 체육복을 찾음
    for (int i = 0; i < lost.length; i++) {
        for (int j = 0; j < reserve.length; j++) {
            // 6. 잃어버린 학생이 체육복을 빌릴 수 있는 학생을 찾음 (앞번호나 뒷번호 학생)
            if (lost[i] - 1 == reserve[j] || lost[i] + 1 == reserve[j]) {
                answer++; // 빌려주었으므로 answer 증가
                reserve[j] = -1; // 여벌 체육복을 가진 학생은 더 이상 빌려줄 수 없으므로 -1로 처리
                break; // 더 이상 비교할 필요 없음
            }
        }
    }

    // 7. 최종적으로 체육 수업에 참여할 수 있는 학생 수 반환
    return answer;
}

 

예제 6 - 조이스틱

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

요점

• 각 알파벳을 만드는 최소 조작 횟수와 커서 이동의 최솟값을 고려하여 전체 최소 이동 횟수를 구한다. (커서 이동시에는 왼쪽/오른쪽 방향으로 이동할 때의 최단 경로를 계산하여, 연속된 A가 있는 구간을 건너뛰는 방법을 고려한다.)

 

소스 코드 

package Algorithm_01_Greedy;

public class Q01_6_Joystick {

    public static void main(String[] args) {
        Q01_6_Joystick js = new Q01_6_Joystick();
        
        System.out.println(js.solution("JEROEN")); // 56
        System.out.println(js.solution("JAN"));    // 23
        System.out.println(js.solution("AAAA"));   // 0
        System.out.println(js.solution("ABABAAAAABA")); // 10
    }
    
    public int solution(String name) {
        int answer = 0; // 총 조작 횟수를 저장할 변수
        int length = name.length(); // 이름의 길이
        int index = 0; // 커서를 이동할 위치를 추적하는 변수
        int move = length - 1; // 커서 이동의 최솟값을 추적하는 변수
        
        // 1. 각 알파벳을 만들기 위한 최소 조작 횟수를 더해줌
        for (int i = 0; i < length; i++) {
            // 알파벳을 만드는 데 드는 최소 조작 횟수: 위로 가는 방법과 아래로 가는 방법 중 더 작은 값 선택
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
        
            // 2. 왼쪽으로 이동할 수 있는 연속된 A를 찾아, 그 범위 안에서 이동을 최소화
            index = i + 1;
            // A가 연속되는 구간을 건너뛰기 위해 index를 찾음
            while (index < length && name.charAt(index) == 'A') {
                index++;
            }
        
            // 3. 이동 경로에서 최솟값을 갱신
            // i * 2 + length - index는 왼쪽으로 이동하고 나서 오른쪽으로 이동하는 경우
            move = Math.min(move, i * 2 + length - index);
            // (length - index) * 2 + i는 오른쪽으로 이동하고 나서 왼쪽으로 이동하는 경우
            move = Math.min(move, (length - index) * 2 + i);
        }
        
        // 4. 알파벳을 만드는 최소 횟수와 커서 이동의 최솟값을 합산하여 결과 반환
        return answer + move;
    }
}

 

그리디 알고리즘을 예제를 풀어본 후

알고리즘 문제는 너무 어렵다. 하지만 한 가지 희망적인 사실(?)은 나에게만 어려운 것이 아니라 남들에게, 우리 모두에게 어렵다는 것이다. 아무렴, 최고의 수학자와 과학자들이 발견한 난제를 푸는 건데, 쉽지 않을 것이다. 문제 유형별로 어떤 자료구조를 써서 알고리즘으로 해결 할 지를 빨리 캐치 할 줄 알아야 한다.

 

그리디 알고리즘은 현재 상태에서 최적의 선택을 하는 방식이다. 이 방식이 잘 통하는 문제와 그렇지 않은 문제를 직감적으로 구분할 수 있어야 한다. 프림 알고리즘과 크루스칼 알고리즘을 사용하는 최소 신장 트리(MST) 문제, 그리고 다익스트라 알고리즘을 사용하는 최단 경로 문제의 경우 그리디 방식이 최적해를 보장한다. 

 

그러나 벨만-포드 알고리즘이나 플로이드-워셜 알고리즘를 사용하는 최단경로 문제는 그리디 방식이 최적해를 보장하지 않는다. 이런 문제들은 다이나믹 프로그래밍(DP)이나 백트래킹 등의 다른 알고리즘을 사용해야 하므로, 그리디 알고리즘 외에도 다양한 알고리즘을 공부하는 것이 중요하다.

또한 그리디 알고리즘을 구현하면서 시간 복잡도를 반드시 고려해야 한다. 보통 그리디 알고리즘은 O(n) 또는 O(n log n)으로 풀 수 있는 경우가 많으므로, 시간 복잡도가 중요한 문제에선 효율적인 자료구조를 선택하는 것도 중요하다. 그리디와 함께 쓰이는 자료구조로는 우선순위 큐나 힙이다.

 

GitHub: https://github.com/awesomepossumgirl/coding-test/tree/main/coding-test/src/Algorithm_01_Greedy

문제 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/parts/12244