[이것이 코딩테스트다] 2. 그리디(Greedy) 알고리즘

이것이 취업을 위한 코딩테스트다

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

그리디(Greedy) : 현재 상황에서 당장 좋은 것만 고르는 알고리즘.

ex) 거스름돈 알고리즘 - 동전을 가장 적게 주는 문제

 

 

그리디 관련 예제 소스(java로 작성)

아래의 소스들은 제가 공부하면서 작성한 코드이기에 참고용으로만 봐주시면 감사하겠습니다.

 

- 큰 수의 법칙

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String a= br.readLine();
		String b= br.readLine();
		
		StringTokenizer st = new StringTokenizer(a);
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		StringTokenizer st2 = new StringTokenizer(b);
		int[] arr = new int[N];
		
		for(int i =0; i<N ; i++) {
			int num = Integer.parseInt(st2.nextToken());
			
			arr[i]=num;
		}
		// 반복되는 묶음 : (M / (K+1))
		// 가장 큰 수가 나오는 횟수 : 반복되는 묶음 * K + 나머지
		// 마지막에 묶음이 아닌 나머지들 : (M % K+1)
		// 두번 째로 큰 수가 나오는 횟수 : M - 가장 큰 수가 나오는 횟수
		
		Arrays.sort(arr); // 입력 받은 수들 정렬하기
        int big1 = arr[N - 1]; // 가장 큰 수
        int big2 = arr[N - 2]; // 두 번째로 큰 수
        
		int count = (M / (K+1)) * K;
		count += (M % (K+1));
		
		int result = 0;
		result = big1 * count;
		result += big2 * (M-count);
		
		System.out.println(result);
		
	}

}

 

 

- 숫자 카드 게임

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		String str1 = sc.nextLine();
		StringTokenizer st1 = new StringTokenizer(str1);
		
		int n = Integer.parseInt(st1.nextToken());
		int m = Integer.parseInt(st1.nextToken());
		
		int[] arr = new int[m];
		
		int big = 0;
		
		for (int i = 0; i<n; i++) {
			String str2 = sc.nextLine();
			
			StringTokenizer st2 = new StringTokenizer(str2);
			for(int j=0;j<m;j++){
				arr[j] = Integer.parseInt(st2.nextToken());
			}
			
			Arrays.sort(arr);
			
			if(arr[0]>=big) {
				big=arr[0];
			}
		}
		
		System.out.println(big);
		
	}

}

 

- 1이 될 때까지

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		int count = 0;
		
		while(true) {
			count++;
			if(N % K == 0) {
				N /= K;
			}else {
				N--;
			}
			
			if(N == 1) {
				break;
			}
		}
		
		System.out.println(count);
	}

}