알고리즘 유형 정리

브루트포스 란

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.
너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊으므로 그때 따로 작성하도록 하겠다.

문제풀이

문제
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오
입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.
예제입력 :
5 21
5 6 7 8 9
예제출력 :
21

아래 2가지 방식으로 문제풀이를 진행하였다.

DFS 방식

public class 백준2798_블랙잭 {

	static int N;
	static boolean[] visited;
	static int 차이 = Integer.MAX_VALUE;
	static int result;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		N = sc.nextInt();
		int M = sc.nextInt();
		visited=new boolean[N];
		int[] arr= new int[N];
		for(int i=0 ; i< N ; i++) {
			arr[i] = sc.nextInt();
		}
		DFS(0,M,arr,0);
		System.out.println(result);
	}
	
	public static void DFS(int idx, int M, int[] arr, int cnt) {
		
		if(cnt ==3) {
			int sum =0;
			for(int i=0 ; i< N ; i++) {
				if(visited[i]){
					sum += arr[i];
				}
			}
			if(sum <= M){
				int diff = M-sum;
				if(차이 >diff) {
					차이 = diff;
					result = sum;
				}
			}
			return;
		}else {
			for(int i=idx; i< N ; i++) {
				if(!visited[i]) {
					visited[i] = true;
					DFS(i+1,M,arr, cnt +1);
					visited[i] = false;
				}
			}
		}
	}
}

삼중 for구문 방식

import java.util.Scanner;

public class 백준2798_블랙잭 {

	static int N;
	static boolean[] visited;
	static int 차이 = Integer.MAX_VALUE;
	static int result;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		N = sc.nextInt();
		int M = sc.nextInt();
		visited=new boolean[N];
		int[] arr= new int[N];
		for(int i=0 ; i< N ; i++) {
			arr[i] = sc.nextInt();
		}
		int result = solution(arr, M);
		System.out.println(result);
	}
	
	public static int solution(int[] arr, int sum) {
		for(int i=0; i<N -2; i++) {
			for(int j =i+1 ; j<N - 1;  j++) {
				for(int k = j+1 ; k < N ; k++){
					int 합산 = arr[i]+arr[j]+arr[k];
					if(합산 == sum) {
						return sum;
					}else if(합산 > sum){
						continue;
					}else {
						int 차 = sum - (합산);
						if(차이 > 차) {
							차이 = 차;
							result = 합산;
						}
					}
				
				}
			}
		}
		return result;
	}
}

해설

일반적으로 모든 경우의 수를 탐색하여 가장 가까운 수를 만드는 완전탐색 유형이다. 완전탐색을 하는 방식은 여러가지 있지만 여기서는 for 구문을 사용한 삼중 for문 방식과 DFS (재귀함수 호출) 방식을 사용하여 진행해보았다. DFS 코드를 익히기 위해 진행하였는데 , 다른 풀이를 보니 다들 삼중for 문을 통해 진행하였는데 속도결과가 더 빠르게 나와 삼중for문 방식도 구현하여 테스트했는데 속도결과는 비슷한것으로 나왔다. 보통 알고리즘 문제에서 이중 for구문 이상을 사용하게되면 시간복잡도가 굉장히 커지는 오류를 범하게 되지만 이 유형에서는 문제없이 수행된것 같다.