[JAVA] Greedy 알고리즘 (with 이코테)

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

=> 지금 상황에서 가장 좋아보이는 것만 선택해도 문제를 풀 수 있는지를 파악해야 함

 

예제 1) 거스름돈 문제

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

=> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 가능함. 

 

그러나 400원과 같은 단위가 생긴다면? 800원을 거스름돈 주는 경우, 그리디의 경우 500,100*3 = 4개가 되지만, 최적의 해는 400*2 이므로 그리디를 적용할 수 없음. => 다이나믹 알고리즘 활용해야 함

=> 문제풀이를 위한 최소한의 아이디어가 정당한 지 검토할 수 있어야 함

 

예제 2) 1이 될 때 까지

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

1. N에서 1을 뺍니다.

2. N에서 K로 나눕니다.

 

Solution 1 => 역방향으로 짜봤다.

// 문제 대로 했을 경우
Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int K = sc.nextInt();

int temp = 1;
int cnt = 0;
while (true) {
	if (temp > N) {
		temp = temp / K;
		cnt--;
		break;
	}
	temp = temp * K;
	cnt++;
}
cnt += N - temp;
System.out.println(cnt);

 

Solution 2 => 문제가 요구하는대로 짜봤음 / 최적의 답 안나옴

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int K = sc.nextInt();
int cnt = 0;

while (true) {
	if (N <= 1) {
		System.out.println(cnt);
		break;
    }
	if (N % K == 0) {
		N = N / K;
		cnt++;
	} else {
		N = N - 1;
		cnt++;
	}
}

 

Solution 3 => 교재 해답

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int K = sc.nextInt();

int result = 0;
while (true) {
	int target = (N / K) * K; // N이 K로 나누어 떨어지는 N과 가장 가까운 수
	result += (N - target); // K로 나누어 떨어지지 않은 수
	N = target;
	if (N < K)
		break;

	result += 1;
	N /= K;
}

result += (N - 1);
System.out.println(result);

 

예제 3) 곱하기 혹은 더하기

각 자리가 숫자로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 문자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

 

- 첫째 줄에 여러개의 숫자로 구성된 하나의 문자열  S가 주어진다.

- 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력한다.

 

Solution 1 => 내가 한번 짜봄.. 답 아닐듯 1을 고려하지못함

int[] input = new int[S.length()];
for (int i = 0; i < S.length(); i++) {
	input[i] = S.charAt(i) - '0';
}

int result = 0;
for (int i = 0; i < S.length(); i++) {
	if (result == 0) {
		result += input[i];
	} else {
		result *= input[i];
	}
}

System.out.println(result);

 

Solution 2 => 교재 해답

long result = S.charAt(0) - '0'; // 첫번째 문자를 변경해서 대입
for (int i = 1; i < S.length(); i++) {
	int num = S.charAt(i) - '0';
	if (num <= 1 || result <= 1) { // 0이거나 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개의 그룹을 만들 수 있습니다. 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

 

Solution => 교재 해답

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class P1_모험가길드 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			list.add(sc.nextInt());
		}

		Collections.sort(list);

		int result = 0; // 총 그룹의 수
		int cnt = 0; // 현재 그룹에 포함된 모험가의 수
		for(int i = 0;i<N;i++) { 
			cnt++; // 현재 그룹에 해당 모험가를 포함시키기
			if(cnt>=list.get(i)) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이면 그룹 결성
				result++; // 그룹 수 증가
				cnt = 0; // 그룹에 포험된 모험가 수 초기화
			}
		}
		System.out.println(result);
	}
}