[이것이 코딩테스트다] Chapter 03 그리디 - 동빈이의 큰 수의 법칙, 숫자 카드게임, 1이 될 때까지

 

Chapter 03 그리디

 

 그리디 (Greedy) 알고리즘

'탐욕법'이라고도 소개되는 이 알고리즘은 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

• 단순하지만 강력한 문제 해결 방법
• 매 순간 가장 좋아보이는 것을 선택. 현재의 선택이 나중에 미칠 여향에 대해서는 고려하지 않는다.
• 보통 코딩 테스트에서 출제되는 그리디 알고리즘 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

 

[예제 1] 거스름돈

- 풀이시간 : 15분

- 문제 설명

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨
• N원을 거슬러 줘야 할 때 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다
  • 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됨
• N = 1,260일 때의 예시를 확인

 

- 문제풀이

N = int(input())
list = [500, 100, 50, 10, 5, 1]
count = 0
for i in range(4) : 
    count += (N // list[i])
    N %= list[i]
print(count)

 

[유사 문제 1] 백준 5585번 거스름 돈 

5585번: 거스름돈 (acmicpc.net)

5585번: 거스름돈

 

 

- 문제풀이

▷입출력 형태로 작성

N = 1000 - int(input())
list = [500, 100, 50, 10, 5, 1]
count = 0
for i in range(6) : 
    count += (N // list[i])
    N %= list[i]
print(count)

화폐의 종류만큼 반복을 수행 => 시간 복잡도 O(K) 

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.

 

- 정당성 확인

가지고 있는 동전 중에서 가장 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

 

만약 서로 배수형태가 아니라 무작위로 주어진 경우 그리디알고리즘으로 해결 X => 다이나믹 프로그래밍으로 해결

 ex) 화폐단위가 500, 400, 100 이고 800원을 거슬러 줘야함.

• 그리디 알고리즘으로 풀었을 때 : 500원 + 100원 + 100원 + 100원
• 최적의 해 : 400원 + 400원

 

[실전문제 2] 큰 수의 법칙 

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번을 더하여 가장 큰 수를 만드는 법칙.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음.

예1) 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정. 이 경우 특정한 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주.

예2) 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 간주. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능. 결과적으로 4+4+4+4+4+4+4인 28

<문제>

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

입력 조건

첫째 줄에 N(2≤N≤1000), M(1≤M≤10000), K(1≤K≤10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분.
둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.
입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건

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

- 풀이시간:   20분

- 문제풀이 (내 풀이)

package com.algo;

import java.util.Arrays;
import java.util.Scanner;

public class BigNumberRule {
	
	public static void main(String[] args) {
		
		//입력값 받기
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int K = sc.nextInt();
		
		int[] arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		//배열 정렬
		Arrays.sort(arr);
		
		//가장 큰 수가 더해지는 개수
		int firstMax = (M / (K + 1)) * K;
		firstMax += M % (K + 1);
		
		//총합 구하기
		int sum = arr[N-1] * firstMax + arr[N-2] * (M - firstMax);
		
		System.out.println(sum);
	}
}

 

예) N이 5이고 입력값이 2, 4, 5, 4, 6. M이 8이고, K가 3

가장 큰 수: 6, 두 번째로 큰 수: 5

정답은 (6+6+6+5) + (6+6+6+5)로 46

"반복되는 수열"에 대해 파악 필요. 위의 예시에선 수열 {6, 6, 6, 5}가 반복됨.

수열의 길이 : (K+1)

수열이 반복되는 횟수 : (M / (K+1)) ⇒ 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수

이때 M이 K+1로 나누어 떨어지지 않는 경우도 고려해야 함. ⇒ M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해짐.

가장 큰 수가 더해지는 횟수 : (M / (K + 1)) * K + M % (K + 1)

 

 

[실전문제 3] 숫자 카드 게임 

- 내 풀이

package com.algo;

import java.util.Scanner;

public class NumberCardGame2 {
	
	public static void main(String[] args) {
		
		//입력 받기
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[][] arr = new int[N][M];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		//각 행의 최솟값이 들어있는 배열 생성
		int[] minArr = new int[N];
		
		for(int i = 0; i < N; i++) {
			minArr[i] = arr[i][0];
			for(int j = 0; j < M; j++) {
				if(minArr[i] > arr[i][j]) {
					minArr[i] = arr[i][j];
				}
			}
		}
		
		//minArr에서 가장 큰 수 찾기
		int max = minArr[0];
		for(int i = 0; i < N; i++) {
			if(max < minArr[i]) {
				max = minArr[i];
			}
		}
		
		System.out.println(max);

	}
}

 

+ min()함수 사용하여 풀어보기

+ 이중배열에 넣지않고 풀어보기

package com.algo;

import java.util.Scanner;

public class NumberCardGame_min {
	
	public static void main(String[] args) {
		
		//N, M 입력 받기
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int result = 0;
		
		//행렬의 원소들 입력받으면서 동시에 최소, 최대 구하기
		for(int i = 0; i < N; i++) {
			int min = 10001;
			for(int j = 0; j < M ; j++) {
				int x = sc.nextInt();
				min = Math.min(x, min);
			}
			result = Math.max(min, result);
		}
		System.out.println(result);
	}
}

 

 

[실전문제 4] 1이 될 때까지

- 내 풀이

package com.algo;

import java.util.Scanner;

public class Until_one {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//내 풀이...
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int cnt = 0;
		while(N>1) {
			if(N % K == 0) {
				N /= K;
				cnt++;
			} else {
				N -= 1;
				cnt++;
			}
		}
		System.out.println(cnt);

	}
}

 

- 교재 풀이

package com.algo;

import java.util.Scanner;

public class Until_one {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//교재 풀이
		//나의 풀이는 계속 1을 빼는 작업을 돌리는게 좀 비효율적임!
		//99,3일때 99/3=33이 되어 66을 빼는 작업에 66번을 돌리는게 좀 비효율적이라
		//아예 66이라는 수를 구해서 빼주도록 해보자! 
		int n = sc.nextInt();
		int k = sc.nextInt();
		int result = 0;
		
		while(true) { // 19 5
			int target = (n / k) * k; // 15
			result += n - target; // 4
			n = target; // 15
			
			if(n < k) break; // 15 < 5 ? False
			
			//1더해주기
			result += 1;
			n /= k; // n = 15 / 5 = 3
		}
		
		result += (n - 1);
		System.out.println(result);

	}
}

 

-정당성 확인

K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있으며, N이 결국 1에 도달한다는 것을 알 수 있다.

 

정리

얼마나 논리적으로 생각해서 알고리즘을 구현하느냐에 따라 코드 차이가 많이 난다.

마지막 문제 '1이 될 때까지' 는 N을 K로 나눌 수 있을 때와 없을 때를 if문을 사용하여 쉽게 구현했는데 이 소스코드는 N의 범위가 10만 이하이므로 빠르게 동작했지만, 만약 N이 100억 이상의 큰 수가 되는 경우를 가정했을 때는 교재풀이처럼 효율적으로 한 번에 빼는 방식으로 작성해주어야 통과했을 것이다.