그리디 알고리즘_JAVA

이것이 코딩테스트다 교재 공부중

 

---

 

그리디 알고리즘

= 현재 상황에서 지금 당장 좋은 것만 선택 

= 지금의 선택이 나중에 미칠 영행은 고려하지 않는다. 

 

언제 사용할까?

사전에 암기하지 않아도 풀 수 있을 가능성이 높은 문제이다. 

- 문제를 풀기 위한 아이디어를 떠올릴 수 있는 능력 평가(창의력)

- 주로 가장 큰 순서대로, 가장 작은 순서대로 같은 기준을 제시해준다. 

- 따라서 그리디는 정렬과 자주 짝을 이뤄서 출제된다.

 

---

 

예제1) 500원, 100원, 50원,10원 동전을 최소 갯수로 거슬러 주는 문제(p.87)

조건, N은 항상 10의 배수 (동전 단위도 항상 배수이다.)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class coins {
	public static void main(String[] args) throws IOException {
		int count = 0;
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	//n 입력 받기
    	int N = Integer.parseInt(br.readLine());
    	
    	//동전 리스트
       	int[] coins = {500,100,50,10};
        
        for(int coin : coins) {
        	count += N / coin;
        	N %= coin;
        }
        
        System.out.print(count);
	}
}

 

-> 가지고 있는 동전 중 가장 큰 단위로 나눠줬을 때 값을 찾을 수 있는지 확인, 가능하면 그리디

 

---

예제2) 큰 수의 법칙(p.92)

N 개의 자연수가 주어지고, 주어진 수를 M번 더해서 가장 큰 수를 구한다.

이때 주어진 수를 연속으로 K번까지만 더할 수 있다. 

N, M, K 가 주어지고 , N개의 자연수가 주어질 경우 최댓값을 구하는 예제

 

how)

연속하는 수의 제한만 있으므로 가장 큰 수와 두번째로 큰 수만 이용해서 값을 구하면 된다.

총 M 번 더할 수 있고, K번만 연속될 수 있기 때문에

M/K 번 만큼 두번째로 큰 수를 더하고 나머지는 가장 큰 수를 더해주면 된다. 

public class biggestNum {
	public static void main(String[] args) throws IOException {
		int count = 0;
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	//첫째줄 N, M, K 입력받기
    	String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int K = Integer.parseInt(input[2]);
    	//자연수 N개 입력받기
    	int[] arr = new int[N];
    	String[] input2 = br.readLine().split(" ");
    	for(int i = 0; i < N; i++) {
    		arr[i] = Integer.parseInt(input2[i]);
    	}
        
    	Arrays.sort(arr);
    	
    	int first = arr[N-1];
    	int second = arr[N-2];
    	     
        int s_count = M / K;
        int f_count = M - s_count;
        
        int answer = first * f_count + second * s_count;
        System.out.print(answer);
	}
}

 

---

예제3) 숫자 카드 게임(p.96)

여러 행 중에서 하나를 선택하고 그 행 중에서 가장 작은 수를 선택해야할 때, 

가장 큰 수를 뽑는 방법

 

how) 

1. 각 행에서 가장 작은 수를 모아서 

2. 그 중에서 가장 큰 수를 선택한다. 

 

- 내 방법 : 행 마다 입력 받고, 가장 작은 수를 정렬해서 구해서 저장함.

저장한 수를 또 정렬해서 가장 큰 수를 구해서 출력

public class NumberCardGame {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	//첫째줄 N, M 입력받기
    	String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        //가장 작은 수만 저장하는 arr
    	int[] arr = new int[N];
        //행의 수 N 만큼 반복하면서 숫자 입력받기
    	for(int i = 0; i < N; i++) {
    		int[] line = new int[M];
        	String[] input2 = br.readLine().split(" ");
        	for(int j = 0; j < M; j++) {
        		line[j] = Integer.parseInt(input2[j]); //각 행의 모든 수를 line배열에 저장
        	}
        	Arrays.sort(line);
        	arr[i] = line[0]; //각 행에서 가장 작은 수를 arr배열에 저장
    	}
    	Arrays.sort(arr);
    	int answer = arr[N-1];
    	System.out.print(answer);
	}
}

- 교재 방법:

저장할 때 min사용해서 저장

public class NumberCardGame {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	//첫째줄 N, M 입력받기
    	String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        //가장 작은 수만 저장하는 arr
    	int answer = 0;
        //행의 수 N 만큼 반복하면서 숫자 입력받기
    	for(int i = 0; i < N; i++) {
    		int minNum = 10000;
        	String[] input2 = br.readLine().split(" ");
        	for(int j = 0; j < M; j++) {
        		minNum =Math.min(minNum, Integer.parseInt(input2[j])); 
        	}
        	answer = Math.max(answer, minNum);
    	}
    	
    	System.out.print(answer);
	}
}

---

예제 4) 1이 될 때까지(p.99)

어떤 수 N이 1이 될 때까지 이 두 과정을 반복한다.

- N에서 1을 뺀다. 

- N을 K로 나눈다. (나누어 떨어질 때만)

이 과정을 최소로 해서 1을 구하는 횟수를 출력

 

 

내 풀이) 

- N이 1이 될 때까지 반복문 실행

- N이 K의 배수가 아니면 -1

- N이 K의 배수이면 나누기

public class untilOne {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//첫째줄 N, K입력받기
    	String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        int count = 0;
        while(N>1) {
        	count++;
        	if(N % K != 0) {
        		N -= 1;
        	}
        	else {
        		N /= K;
        	}
        }
        System.out.print(count);
	}
}

 

 

---

2023.09.11

아직 예제가 쉬워서 괜찮다.

뭔가 딱 정렬, 출력 이정도라서 생각만 잘 하면 괜찮을듯

 

프로그래머스가 아니라 입력값 하나씩 직접 입력받고 입력해주는게 넘 귀찮다

그리고 파이썬 코드가 너무 쉬워보여서 고민된다..