[알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기

[ 목차 ]

1. 정의

 

2. 그리디 알고리즘 작동 방식(그림 예시)

 

3. 그리디 알고리즘 채택의 조건

 

4. 코드구현 예제풀이 : 행렬

 

5. 정리

▶그리디 알고리즘(탐욕법, Greedy Algorithm)

• 최적값 탐색 알고리즘
• 말 그대로 탐욕적 알고리즘,  최적값을 탐색하는 상황에서 당장 눈앞에 주어진 선택지 중 가장 최적의 값을 선택하는 알고리즘
• DP가 단순한 문제 상황에서 지나치게 많은 수행시간을 가지는 단점을 해결
• 부분문제의 최적값이 전체문제의 최적값이 아닐 수 있음

 

◈ 그리디 알고리즘 작동 방식(그림 예시)

위 그림의 트리에서 최댓값 탐색을 한다고 할 때, 실제 최적값은 2 - 10 선택을 통한 12이지만, 그리디 알고리즘은 각 단계별 근시안적인 선택을 하기 때문에, 5 - 6 선택으로 11의 값을 도출한다. 이러한 그리디 알고리즘의 특성 때문에 후술할 두가지 조건을 만족해야만 문제 해결 도구로 그리디 알고리즘을 채택할 수 있다.

 

 

 

 

◈ 그리디 알고리즘 채택의 조건

1. 탐욕스러운 선택이 최적값이라는 것에 대한 보장(탐욕 선택 속성)

- 위 그림과 같은 상황에서는 그리디 탐색을 통해 최적값을 도출할 수 없기 때문에, 그리디 알고리즘을 사용할 때는 반드시 탐욕적인 선택이 전체 문제의 최적값이라는 것에 대한 보장이 있어야 한다.

 

2. 최적 부분 구조

- 문제가 부분문제로 나누어져,  부분문제의 최적값이 전체문제의 최적값이라는 것에 대한 보장이 있을 때 사용할 수 있다.

 

 

 

 

▶코드 구현 예제 풀이 : 행렬

이해를 돕기 위해, 백준의 1080번 행렬을 예시로 가지고 왔다.

 

 

 

 

 

 

▶전체 코드

import java.util.Scanner;

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

        // 행렬의 크기 N, M 입력
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[][] A = new int[N][M];
        int[][] B = new int[N][M];

        // 행렬 A 입력
        for (int i = 0; i < N; i++) {
            String row = scanner.next();
            for (int j = 0; j < M; j++) {
                A[i][j] = row.charAt(j) - '0'; //숫자의 char형 아스키코드에서 '0'을 빼면 같은 숫자의 int형 정수로 변환 됨 
            }
        }

        // 행렬 B 입력
        for (int i = 0; i < N; i++) {
            String row = scanner.next();
            for (int j = 0; j < M; j++) {
                B[i][j] = row.charAt(j) - '0';
            }
        }

        int operations = 0;

        // 3x3 부분 행렬을 뒤집는 연산 수행
        for (int i = 0; i <= N - 3; i++) {
            for (int j = 0; j <= M - 3; j++) {
                // A[i][j]와 B[i][j]가 다르면 3x3 부분 행렬을 뒤집음
                if (A[i][j] != B[i][j]) {
                    flip(A, i, j);
                    operations++;//연산횟수 증가
                }
            }
        }

        // 최종적으로 A와 B가 같은지 확인
        if (isEqual(A, B)) {
            System.out.println(operations);
        } else {
            System.out.println(-1);//바꿀 수 없을 시 -1 출력 
        }
        scanner.close();
    }

    // 3x3 부분 행렬을 뒤집는 함수
    private static void flip(int[][] A, int startX, int startY) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                A[startX + i][startY + j] ^= 1; // XOR 연산으로 0과 1을 뒤집음
            }
        }
    }

    // 두 행렬이 같은지 확인하는 함수
    private static boolean isEqual(int[][] A, int[][] B) {
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[0].length; j++) {
                if (A[i][j] != B[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
    
}

 

 

 

 

▶출력 결과

 

 

 

 

 

 

▶정리

• 그리디 알고리즘은 최적값 탐색 알고리즘이다.
• 근시안적 탐색이라는 특성때문에, 탐욕 선택 속성과 최적 부분 구조를 만족해야만 그리디 알고리즘을 사용할 수 있다.
• 코드로의 구현이 매우 쉬운 편.