알고리즘 유형1. 그리디 (greedy) feat. 유레카

Greedy 탐욕법

현재 상황에서 지금 당장 좋은 것만 고르는 방법

개인적으로 알고리즘 방법중 가장 단순 무식한 방법, 단순 암기가 필요하지 않은 방법, 다양한 유형에서 어떻게든 답을 낼 수 있는 방법 이라고 생각한다.

 

• 모든 경우의 수를 다 따지는 완전 탐색(브루트포스)을 대비해서 꼭 필요한 (최선의) 선택을 통해서 답을 구함
• Greedy의 전제조건 : "수학적으로 증명된" 당연한 논리 (막연한 추측은 절대 네버 금물)
• 타고난 수학적 직관력..(은 없어서) 오랜 경험을 통한 판단 해야한다.
• 그래프 알고리즘(DFS, BFS) 에서 Greedy를 사용할 수 있다.

 

이것이 코딩테스트다 CH03.문제1 큰 수의 법칙

: n개의 숫자들 중 m번 더해서 만들 수 있는 최대값을 출력 (단, 같은 수는 k번까지 반복 가능)

package Greedy_ch03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//BufferedReader + static(optional)
//static 변수는 재귀호출에서 공유
//local 변수 대비 반복 테케가 있는 경우(SWEA) 각 테게별로 초기화 해줘야 한다.
public class 큰수의법칙_5 {
	static int n, m, k, result;
	static int[] arr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// N, M, K를 공백을 기준으로 구분하여 입력 받기
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		// N개의 수를 공백을 기준으로 구분하여 입력 받기
		arr = new int[n];
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// sort대신 사용, O(N)
		int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        
        // 배열을 한 번 순회하여 가장 큰 수와 두 번째로 큰 수를 찾기
        for (int i = 0; i < n; i++) {
            if (arr[i] > first) {
                second = first;
                first = arr[i];
            } else if (arr[i] > second) {
                second = arr[i];
            }
        }

		int cnt = (m / (k + 1)) * k;
		cnt += m % (k + 1);
		result += cnt * first; // 가장 큰 수 더하기
		result += (m - cnt) * second; // 두 번째로 큰 수 더하기
		System.out.println(result);
	}
}
/*
5 8 3
2 4 5 4 6

46
 */

 

 

이것이 코딩테스트다 CH03.문제2 숫자카드게임

: n x m개의 2차원으로 제시된 숫자중 각 행기준 최솟값 중 최대값을 출력

package Greedy_ch03;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 리팩토링, 자료구조(map) 사용안함
public class 슷자카드게임3 {
	static int n, m, result;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		for (int i = 0; i < n; i++) {
			// 각 행별로 가장 작은 수 선택
			int min_value = 10001;
			st = new StringTokenizer(br.readLine());	// 한 줄을 읽어서 token 처리
			for (int j = 0; j < m; j++) {
				int input = Integer.parseInt(st.nextToken());
				min_value = Math.min(min_value, input);
			}
			result = Math.max(result,  min_value);
		}
		
		System.out.println(result);
	}
}
/*
3 3
3 1 2
4 1 4
2 2 2

2
*/

 

이것이 코딩테스트다 CH03.문제3 1이 될때까지

: n이 1이 될 때까지 1을 빼거나, k로 나누기

package Greedy_ch03;

import java.util.Scanner;
public class _1이될때까지2 {

	 public static void main(String[] args) {
	        Scanner sc = new Scanner(System.in);

	        // N, K를 공백을 기준으로 구분하여 입력 받기
	        int n = sc.nextInt();
	        int k = sc.nextInt();
	        int result = 0;

	        while (true) {
	            // 우선순위대로 n -> 1로 변경
	        	// 1 이 되면 종료
	        	if(n == 1) break;

	        	// k 로 나눌 수 있으면 나눈다. (우선순위)
	        	if (n % k == 0) {
	        		n = n / k;
	        		result++;
	        	}else {
	        		// 여러개 연산 갯수 처리
	        		int target = (n / k) * k;
	        		result += (n - target);
	        		n--;
	        	}
	        }

	        System.out.println(result);
	    }
}