완전검색, 그리디

완전검색

• 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
• Brute-force 혹은 Generate-and-Test 기법이라고도 불리운다.
• 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.
• 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
• 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
• 자격검정평가 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

package test01;

public class test1순열 {
	public static void main(String[] args) {
		//a부터 b까지의 연속된 숫자 중에서
		//3개를 뽑아서 나열하는 순열
		
		int a=1;
		int b=4;
		//1,2,3,4, 네 개의 숫자 중에서 3개를 뽑아 나열하는 순열
		
		
		
		for(int i=a; i<=b; i++) {
			for (int j = a; j <= b; j++) {
				//j는 앞에서 나왔던 a가 아닌 수만 나올 수 있다.
				if (j!=i) {//if문 안에서 그 다음 for문이 돌아야된다.
					for (int k = a; k <=b; k++) {
						//k는 i,j가 아닌 수만 나올 수 있다.
						if (k!=i&&k!=j) {
							System.out.printf("%d %d %d\n", i, j, k);
						}
					}
				}
			}
		}
	}
}
//
1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1
2 3 4
2 4 1
2 4 3
3 1 2
3 1 4
3 2 1
3 2 4
3 4 1
3 4 2
4 1 2
4 1 3
4 2 1
4 2 3
4 3 1
4 3 2

package test01;

public class test2 {
	public static void main(String[] args) {
		//연속되지 않은 서로 다른 n개의 숫자 중에서 3개를 뽑는 방법은?
		//배열의 숫자 중에서 3개를 뽑아 나열하는 순열
		//서로 다른 n개 중에서 r개 뽑는 순열
		//->r중포문
		
		int[] arr= {2,5,8,9};
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (j!=i) {
					for (int k = 0; k < arr.length; k++) {
						if (k!=i&&k!=j) {
							System.out.printf("%d %d %d\n", arr[i], arr[j], arr[k]);
						}
					}
				}
			}
		}
	}
}
//
2 5 8
2 5 9
2 8 5
2 8 9
2 9 5
2 9 8
5 2 8
5 2 9
5 8 2
5 8 9
5 9 2
5 9 8
8 2 5
8 2 9
8 5 2
8 5 9
8 9 2
8 9 5
9 2 5
9 2 8
9 5 2
9 5 8
9 8 2
9 8 5

package test02;

public class test1babyjin {
	// 문제에 접근할 때는 분할정복

	public static void main(String[] args) {
		// 3개 짜리
		int[] arr = { 4, 5, 6 };

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (j != i) {
					for (int k = 0; k < arr.length; k++) {
						if (k != i && k != j) {
							// 여기에서 모든 경우의 수가 만들어짐
							// 첫번째 숫자:arr[i] 두번째 숫자:arr[j] 세번째 숫자:arr[k]
							if (runCheck(arr[i], arr[j], arr[k])) {
								System.out.println("run");
								System.out.printf("%d %d %d->%s\n", arr[i], arr[j], arr[k], runCheck(arr[i], arr[j], arr[k]));
								System.out.printf("%d %d %d->%s\n", arr[i], arr[j], arr[k], tripletCheck(arr[i], arr[j], arr[k]));
							}
						}
					}
				}
			}
		}
	}

	// run체크하는 메서드
	// 임의의 숫자 3개가 주어질 때 연속 여부 판단
	static boolean runCheck(int a, int b, int c) {
		// b==a+1 && c==a+2
		// b==a+1 && c==b+1
		return b == a + 1 && c == a + 2;
	}

	// triplet을 체크하는 메서드
	// 임의의 숫자 3개가 주어질 때 일치 여부를 판단
	static boolean tripletCheck(int a, int b, int c) {
		return a == b && a == c;
	}
}
//}
//
run
4 5 6->true
4 5 6->false

 

탐욕 알고리즘

• 탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
• 일반적으로, 머릿속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.

탐욕 알고리즘의 동작 과정

• 1. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합에 추가
• 2. 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검사한다.
• 3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1.의 해 선택부터 다시 시작한다.

package test03;

//거스름돈 줄이기
//거스름돈에서 가장 돈을 조금 주는 방법

public class Test1_거스름돈 {
	public static void main(String[] args) {
		int money = 800;
		
		int c500 = money / 500;
		money -= c500 * 500;
		
		int c100 = money / 100;
		money -= c100 * 100;
		
		int c50 = money / 50;
		money -= c50 * 50;
		
		int c10 = money / 10;
		money -= c10 * 10;
		
		System.out.printf("500원: %d\n", c500);
		System.out.printf("100원: %d\n", c100);
		System.out.printf(" 50원: %d\n", c50);
		System.out.printf(" 10원: %d\n", c10);
		
		
	}
}
//
500원: 1
100원: 3
 50원: 0
 10원: 0

package test03;

public class Test2_거스름돈2 {
	public static void main(String[] args) {
	
		//탐욕 알고리즘
		
		//1. 최적해 문제를 푸는데 사용
		//최적해 : 최소값, 최소값 찾는 것 ex) 동전의 개수를 최소로
		//최적해는 1개
		
		//2. 각 단계마다 최선의 선택을 해나감
		//어떻게 선택할지는 미리 정함
		//각 선택이 부분해에 포함
		//각 선택은 그 단계에서 최적해
		
		//3. 모든 단계가 끝나면 그 부분해 집합이 곧 최적해가 됨
		
		//최소의 동전 개수로 거스름돈을 주는 방법?
		//각 단계에서 선택할 수 있는 방법? 500, 100원, 50원, 10원
		//각 단계에서 어떻게 선택할지 미리 정하기
		//각 방법을 비교
		//500원->1개
		//100원->5개
		//50원->10개
		//10원->50개
		//각 단계에서는 최대한 금액이 큰 동전을 거슬러 주는 것이 최선의 선택
		
		//매 단계에서 동일한 기준으로 판단
		//f(1200) / f(900) / f(300)
		//현재 단계에서 최선의 선택만을 생각
		//선택했다면 그것을 부분해 집합에 포함하고, 그 다음단계로 넘어감
		
		//ex) f(800)
		//500원 선택
		//->{500원 1개}, f(300)->100원 선택
		//->{500원 1개, 100원 1개}, f(200)->100원 선택
		//->{500원 1개, 100원 2개}, f(100)->100원 선택
		//->{500원 1개, 100원 3개}:최적해
		
		//800원->400원 두개가 최소
		
		int money = 800;
		
		int c500 = money / 500;
		money -= c500 * 500;
		
		int c400 = money / 400;
		money -= c400 * 400;
		
		int c100 = money / 100;
		money -= c100 * 100;
		
		int c50 = money / 50;
		money -= c50 * 50;
		
		int c10 = money / 10;
		money -= c10 * 10;
		
		System.out.printf("500원: %d\n", c500);
		System.out.printf("400원: %d\n", c400);
		System.out.printf("100원: %d\n", c100);
		System.out.printf(" 50원: %d\n", c50);
		System.out.printf(" 10원: %d\n", c10);
		
		
	}
}
//
500원: 1
400원: 0
100원: 3
 50원: 0
 10원: 0