이것이 코딩 테스트다 (JAVA 코드) - Greedy

개요

그리디 (greedy) 알고리즘이란 현재 상황에서 지금 당장 좋은 방법으로만 풀이를 해나가는 것을 그리디 알고리즘이라고 합니다. 그리디 알고리즘의 핵심은 정당성 분석을 통한 풀이 입니다. 단순히 가장 좋아보이는  것만을 반복해도 최적의 해가 나올 수 있는지 검토해야 합니다.

 

출처

이것이 코딩테스트다

 

예시

루트 노드부터 시작하여 거쳐가는 노드의 값들의 합을 최대값으로 구하고 싶을 때 최적의 해를 구하려면 어떻게 해야할까요?

루트 노드에서 루트들의 최대의 합을 구하려면 어떻게 할까?

• 최적의 해는 5 - 7 - 9 노드일겁니다.
• 하지만 그리디 알고리즘은 현재 상황에서 가장 큰 값만 선택하게 되는 경우입니다. 그러므로 보통은 5 - 10 - 4노드를 선택합니다
• 그렇다면 이 경우 최적의 해가 아니게 됩니다.

일반적인 상황에서 그리디 알고리즘은 최적의 해가 보장받을 수 없을 때가 많습니다. 하지만 그럼에도 코딩테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됩니다. 

 

문제1 : 거스름 돈

당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 동전 500원, 100원, 50원, 10원짜리 동전이 부족하지않게 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

 

 

포인트

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 줍니다.
• N원을 거슬러 줘야할 때, 가장 먼저 500원부터 거슬러 줄 수 있는 만큼 거슬러 주고 다음 화폐단위로 넘어갑니다.

 

정당성 분석

• 가장 큰 화폐 단위부터 돈을 거슬러 줘야한다고 했는데 이유가 뭘까요?
  • 동전중에서 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른해가 나올 수 없기 때문입니다.
• 만약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면 다른 경우보다 400원 단위 화폐로 2개를 거슬러 주는게 최적의 해가 됩니다.
• 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 갖고 이를 정당한지 검토할 수 있어야 합니다.

public class Main {

	public static void main(String[] args) {
		int n = 1260;
		int cnt = 0;
		int[] coinTypes = {500, 100, 50, 10};

		for(int i=0; i<4; i++) {
			cnt += n / coinTypes[i];
			n %= coinTypes[i];
		}
		
		System.out.println(cnt);
	}
}

 

 

 

 

문제2 : 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.

예를 들어 N이 17, K가 4라고 가정한다면, 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 그리고 2번 과정을 두번 수행하면 N은 1이 됩니다. 이렇듯 이 경우에는 전체 과정을 실행한 횟수가 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하시오.

 

포인트

• 주어진 N에 대하여 최대한 많이 나누기를 수행하면 됩니다.
• N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄입니다.
• 예를 들어 N = 25, K = 3일 때는 다음과 같습니다.단계 연산 과정 N의 값 

  0	초기 값	N = 25
  1	N에서 1 빼기	N = 24
  2	N을 K로 나누기	N = 8
  3	N에서 1 빼기	N = 7
  4	N에서 1 빼기	N = 6
  5	N을 K로 나누기	N = 2
  6	N에서 1 빼기	N = 1

 

 

 

정당성 분석

• 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할까요?
• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있습니다.
• 다시 말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것 보다 항상 빠르게 N을 줄일 수 있습니다.
• 또한 N은 항상 1에 도달하게 됩니다.

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int result = 0;

		while(true) {
			int target = (n / k) * k;
			result += (n - target);
			n = target;

			if(n < k) break;
			result += 1;
			n /= k;
		}
		
		result += (n - 1);
		System.out.println(result);
	}
}

 

 

문제3 : 곱하기 혹은 더하기

각 자리가 숫자(0 ~ 9) 로만 이루어진 문자열 S가 주어질 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 * 혹은 + 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하시오. 단, + 보다 *를 먼저 계산하는 일반식과는 달리 모든 연산은 왼쪽부터 순서대로 이루어집니다.

예를 들어 02984라는 문자열로 이루어진 수를 통해 만들 수 있는 가장 큰 수는 (((((0 + 2) * 9) * 8) * 4) = 576 입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

 

 

포인트

• 대부부의 경우 ‘+’보다 ‘ * ’가 더 값을 크게 만듭니다. 예를 들어 5 + 6 = 11, 5 * 6 = 30입니다.
• 다만 두 수 중에서 하나라도 ‘0’이거나 ‘1’이라면 곱하기 보다는 더하기를 수행하는 것이 효율적입니다.
• 따라서 두 수에 대한 연산을 수행할 때, 두 수중에서 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 정답입니다.

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		
		long result = str.charAt(0) - '0';
		for(int i=1; i<str.length(); i++) {
			int num = str.chatAt(0) - '0';
			if(num <= 1 ||  result <= 1) {
				result += num;
			} else {
				result *= num;
			}
		}
		System.out.println(result);
	}
}

 

 

 

문제4 : 모험가 길드

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’를 측정했는데, ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

모험가 길드장인 아무개는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.

아무개는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 최대 그룹의 수를 구하시오.

예를 들어, N = 5 이고, 각 모험가의 공포도가 다음과 같습니다.

2 3 1 2 2

이 경우 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면 총 2개의 그룹을 만들 수 있습니다.

또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

 

 

 

문제 해결 아이디어

• 오름차순 정렬 이후에 공포도가 낮은 모험가부터 하나씩 확인합니다.
• 앞에서부터 공포도를 확인하여 ‘현재 그룹에 포함된 모험가의 수’가 ‘현재 확인하고 있는 공포도’ 보다 크다면 이를 그룹으로 설정합니다.
• 이러한 방법을 이용하면 공포도가 오름차순으로 정렬되어 있다는 점에서 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 됩니다.

public class Main {

	public static int n;
	public static ArrayList<Integer> list = new ArrayList<>():

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		for(int i=0; i<n; i++) {
			list.add(list);
		}
		Collections.sort(list);

		int result = 0;
		int cnt = 0;
		for(int i=0;i<n;i++){
			cnt += 1;
			if(cnt >= list.get(i)) {
				result += 1;
				cnt = 0;
			}
		}
		System.out.println(result);
	}
}

 

 

출처 : 이것이 코딩테스트다 도서