[Algorithm] Greedy Algorithm

한빛미디어의 이것이 취업을 위한 코딩테스트다 with 파이썬을 요약 정리했습니다. 

그리디 알고리즘이란

- 탐욕 알고리즘, 탐욕법

- 여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

 

그리디 알고리즘의 특징

- 매 순간 가장 좋아보이는 것을 선택

- 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

- 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

 

예제문제- 거스름돈

거스름돈으로 사용할 500, 100, 50, 10원짜리 동전히 무한히 존재한다고 가정.
거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.
(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.)

 

소스코드

- 예제 소스 3-1.py를 자바로 작성하였음

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

	public static void main(String[] args) {
		int n = 1260;
		int count = 0;

		int[] coin_types = {500, 100, 50, 10};

		for(int coin : coin_types) {
			count += n / coin;
			n %= coin;
		}

		System.out.println(count);
	}

 

풀이

- 가장 큰 화폐 단위부터 돈을 거슬러 주는 것

- ex.) N이 1,260 -> 500원 2개, 100원 2개, 50원 1개, 10원 1개

- N이 1,260일 때 손님이 받은 동전의 최소 개수는 6개.

- 화폐의 종류만큼 반복을 수행해야 함.

- 따라서 화폐의 종류가 K개라고 할 때 시간 복잡도는 O(K)

 

그리디 알고리즘의 정당성

- 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아님.

- 대분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분.

- 하지만 거스름돈 문제와 같이 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적.

- 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

 

- 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유

    - 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

 ex.) 800원을 거슬러줘야 할 경우이며, 화폐 단위가 500, 400, 100원인 경우
그리디 알고리즘의 결과는 4개의 동전. 
하지만, 최적의 해는 2개의 동전(400 + 400)

"다시 말해 이 문제에서는 큰 단위가 작은 단위의 배수 형태이므로, '가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다'는 아이디어는 정당하다."

- 대부분의 그리디 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

 

연습문제- BOJ 1105 팔

- solved.ac tag:greedy silver1

L과 R이 주어진다. 이때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에
8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

1105번: 팔

풀이

- 주어진 범위 안에서, 8이 가장 적게 들어있는 수 안에 들어있는 8의 개수를 구하는 문제

- ex.) a,b가 각각 1과 10이면 1,2,...7,8,9 중에서 가장 적게 들어있는 수는 8을 제외한 나머지 이므로 0개 이다.

    - 이처럼 자리수가 다르다면 8이 들어가지 않는 수가 존재함 즉, 0개

- 자릿수가 같아도 큰 자릿수를 비교하였을 때 다르다면, 8이 들어가지 않는 수가 존재함 즉, 0개 ex.) 89와 90 => 0

- a와 b의 자릿수가 같고, 큰 자릿수의 수가 동일하며 a의 큰 자릿수가 8인 수를 카운트하면 됨. ex.) 88과 89 => 1

- 즉 자릿수가 같고, a와 b 둘 다 8로 시작하는 수를 범위 안에서 카운트.

 

소스코드

import java.io.*;

public class BOJ_1105 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] strArr = br.readLine().split(" ");

        char[] L = strArr[0].toCharArray();
        char[] R = strArr[1].toCharArray();

        int result = 0;
        if(L.length == R.length) {
            for (int i = 0; i < L.length; i++) {
                if(L[i] == R[i] && L[i] == '8') {
                    result++;
                } else if(L[i] != R[i]) {
                    break;
                }
            }
        }

        bw.write(String.valueOf(result));
        bw.close();
    }
}

// 추가
// 조건절을 다음과 같이 수정하면 불필요한 로직을 줄일 수 있다.
if(L[i] != R[i]) {
	break;
} else if(L[i] == '8') {
	result++;
}