그리디 알고리즘

1. 탐욕 알고리즘(Greedy Algorithm)이란?

• 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 쫓아 최종적인 해답에 도달한다.

  	✔ '탐욕스러운, 욕심 많은' 이란 뜻

2. 탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아간다.

3. 탐욕 알고리즘이 적용하려는 문제의 조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

4. 예시문제-1번

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어서 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

import java.awt.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

class Map{
	
	HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
}


public class Main{
	
	//public static int N, M, A[];
	public static int three_check(int i, int j, int k) {
		if((i%10 == 3 || i/10 == 3) || (j%10 == 3 || j/10 == 3) || (k%10 == 3 || k/10 == 3))
			return 1;
		else
			return 0;
	}

	
	
	public static void main(String[] args) throws Exception {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		int cnt=0;
		for(int i=0; i<=N; i++) {
			for(int j =0; j<60; j++) {
				for(int k=0; k<60; k++) {
					if(three_check(i, j, k) == 1)
						cnt++;
				}
			}
		}
		System.out.println(cnt);
		 
	} // main()
	
	
	

}

예시 문제 풀이1 설명)

 h(시간)를 보고 설명을 하면

 3%10 = 3, 13%10 = 3, 23%10 = 3 으로 시간에 3이 들어가는지 확인이 가능하다.

 m(분)과 s(초)을 보고 어떤 부분만 설명을 하면

 31/10 = 3, 32/10=3, 43%10 = 3 으로 시간에 3이 들어가는지 확인이 가능하다.