[백준] 2798번 : 블랙잭 - JAVA [자바]

www.acmicpc.net/problem/2798

2798번: 블랙잭

 

---

• 문제

 

 

 

 

문제가 그리 어렵지 않다!

 

---

• 알고리즘 [접근 방법]

 

 

브루트 포스 (Brute Force) 카테고리의 첫 문제다.

 

브루트 포스.. 난폭한(무식한) 힘이라는 의미 그대로 어떤 값을 찾아내기(또는 목적을 달성하기) 위해 무차별적으로 대입해보는 방법이다.

말 그대로 무식한 방법이다. (일명 노가다..)

 

이 알고리즘의 가장 큰 특징은 가능한 모든 경우의 수를 대입해보며 조건에 만족하는 값만을 찾아낼 수 있다는 점이다.

결국 자원만 충분하다면 원하는 값을 100% 확률로 찾아낼 수 있다는 것이 매우 크다.

 

특히나 암호학에서 위 방법은 매우 원초적일 수 있으나 정확도가 100% 이다보니 자원이 무한하면 가장 무서운 방법이기도 하다.

그렇기에 브루트 포스 알고리즘을 위해 가장 중요한 것은 "빠짐 없이" 완전탐색 알고리즘을 잘 짜야한다는 점이다.

 

(물론 명백하게 불가능한 값의 경우는 제외하는 등, 어느정도 자원을 최적화 할 필요도 있다.)

 

 

 

이번 블랙잭 문제도 마찬가지다.

 

전체 카드(N)에서 3개를 고를 수 있는 경우의 수 모두 탐색하여 각 경우 별 선택한 카드의 합을 모두 구한 뒤, 주어진 M 을 넘지 않는 최댓값을 찾으면 된다.

 

 

즉, 3중 for문을 사용하여 모든 경우의 수를 탐색하면 끝이다.

 

 

 

 

 

 

 

---

• 4가지 방법을 이용하여 풀이한다.

 

먼저 가장 기본적인 완전 탐색 알고리즘을 보여줄 것이다.

즉, 만족하는 값을 찾을 때 까지 계속 찾다가, 모든 경우를 탐색하고 나면 M 을 넘지 않은 가장 큰 값을 출력하면 된다.

 

그리고 다음으로는 자원을 조금이나마 최소화하여 탐색을 좀 더 효율적으로 하는 방법을 보여주려 한다.

 

입력은 각각의 알고리즘에 대해 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int M = in.nextInt();

		int[] arr = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		int result = search(arr, N, M);
		System.out.println(result);
	}

	
	// 탐색
	static int search(int[] arr, int N, int M) {
		int result = 0;

		// 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
		for (int i = 0; i < N - 2; i++) {

			// 두 번째 카드는 첫 번째 카드 다음부터 N - 1 까지만 순회
			for (int j = i + 1; j < N - 1; j++) {

				// 세 번째 카드는 두 번째 카드 다음부터 N 까지 순회
				for (int k = j + 1; k < N; k++) {
					
					// 3개 카드의 합 변수 temp
					int temp = arr[i] + arr[j] + arr[k];
					
					// M과 세 카드의 합이 같다면 temp return 및 종료 
					if (M == temp) {	
						return temp;
					}
					
					// 세 카드의 합이 이전 합보다 크면서 M 보다 작을 경우 result 갱신 
					if(result < temp && temp < M) {
						result = temp;
					}
				}
			}
		}
		
		// 모든 순회를 마치면 result 리턴 
		return result;
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

i, j, k 번째 카드의 합을 구한다.

만약 세 카드의 합이 M 이랑 같으면 더이상 탐색을 할 필요가 없기 때문에 바로 세 카드의 합을 리턴시킨다.

만일 세 카드의 합이 M 보다 작으면서, 이전에 저장했던 세 카드의 합보다 크면 result 를 새로 갱신한다.

 

이런식으로 세 카드의 합이 M이랑 같기 전까진 모든 경우의 수를 탐색해보는 것이다.

 

---

- 방법 2 

 

 

위 알고리즘에서 Scanner 대신 BufferedReader 로 입력받아 사용하는 방법이다.

또한 문자열 분리를 필요로 하니 StringTokenizer 을 추가로 사용할 것이다.

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = search(arr, N, M);
		System.out.println(result);
	}

	
	// 탐색
	static int search(int[] arr, int N, int M) {
		int result = 0;

		// 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
		for (int i = 0; i < N - 2; i++) {

			// 두 번째 카드는 첫 번째 카드 다음부터 N - 1 까지만 순회
			for (int j = i + 1; j < N - 1; j++) {

				// 세 번째 카드는 두 번째 카드 다음부터 N 까지 순회
				for (int k = j + 1; k < N; k++) {
					
					// 3개 카드의 합 변수 temp
					int temp = arr[i] + arr[j] + arr[k];
					
					// M과 세 카드의 합이 같다면 temp return 및 종료 
					if (M == temp) {	
						return temp;
					}
					
					// 세 카드의 합이 이전 합보다 크면서 M 보다 작을 경우 result 갱신 
					if(result < temp && temp < M) {
						result = temp;
					}
				}
			}
		}
		
		// 모든 순회를 마치면 result 리턴 
		return result;
	}
}

 

 

 

 

 

 

---

- 방법 3 

 

 

 

위 브루트 포스 알고리즘의 경우 세 카드의 합이 M 이랑 같지 않는 이상 모든 경우의 수를 탐색한다.

즉 최악의 경우 수행시간이 O(N³) 이 된다. 

 

그렇기에 조금만 더 효율적으로 탐색하기 위해서 어떻게 해야할지 고민해볼 가치가 있다.

 

조건을 보면 세 카드의 합이 M 을 넘으면 안된다는 조건이 있다.

그렇다면 카드 한 장이 이미 M 보다 크면 탐색할 필요가 있는가? 당연 없다.

 

만약 첫 번째 카드가 M 보다 작거나 같은 경우라도, 두 번째 카드를 선택 했을 때 두 카드의 합이 M 보다 커도 이미 탐색할 가치는 없을 것이다. (카드의 값은 양의 정수로 입력된다고 이미 조건에 나와있으므로)

 

이를 조건문으로 달아서 탐색하면 불필요한 탐색까지 할 필요가 없어질 것이다.

 

(물론 블랙잭 문제의 경우 데이터 자체가 매우 적어서 조건문을 다는 것이 시간을 더 지연시킬 수도 있다)

 

즉, 아래와 같이 짜보면 될 것 같다.

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int M = in.nextInt();

		int[] arr = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		int result = search(arr, N, M);
		System.out.println(result);
	}

	
	// 탐색
	static int search(int[] arr, int N, int M) {
		int result = 0;

		// 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
		for (int i = 0; i < N - 2; i++) {
			
			// 첫 번째 카드가 M 보다 크면 skip
			if(arr[i] > M) continue;
			
			// 두 번째 카드는 첫 번째 카드 다음부터 N - 1 까지만 순회
			for (int j = i + 1; j < N - 1; j++) {

				// 두 번째 카드와 첫 번째 카드의 합이 M보다 크면 skip
				if(arr[i] + arr[j] > M) continue;
				
				// 세 번째 카드는 두 번째 카드 다음부터 N 까지 순회
				for (int k = j + 1; k < N; k++) {
					
					// 3개 카드의 합 변수 temp
					int temp = arr[i] + arr[j] + arr[k];
					
					// M과 세 카드의 합이 같다면 temp return 및 종료 
					if (M == temp) {	
						return temp;
					}
					
					// 세 카드의 합이 이전 합보다 크면서 M 보다 작을 경우 result 갱신 
					if(result < temp && temp < M) {
						result = temp;
					}
				}
			}
		}
		
		// 모든 순회를 마치면 result 리턴 
		return result;
	}
}

 

 

 

 

 

---

- 방법 4

 

 

 

방법 3 의 알고리즘에서 입력 방법만 바꾼 방법이다.

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = search(arr, N, M);
		System.out.println(result);
	}

	
	// 탐색
	static int search(int[] arr, int N, int M) {
		int result = 0;

		// 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
		for (int i = 0; i < N - 2; i++) {
			
			// 첫 번째 카드가 M 보다 크면 skip
			if(arr[i] > M) continue;
			
			// 두 번째 카드는 첫 번째 카드 다음부터 N - 1 까지만 순회
			for (int j = i + 1; j < N - 1; j++) {

				// 두 번째 카드와 첫 번째 카드의 합이 M보다 크면 skip
				if(arr[i] + arr[j] > M) continue;
				
				// 세 번째 카드는 두 번째 카드 다음부터 N 까지 순회
				for (int k = j + 1; k < N; k++) {
					
					// 3개 카드의 합 변수 temp
					int temp = arr[i] + arr[j] + arr[k];
					
					// M과 세 카드의 합이 같다면 temp return 및 종료 
					if (M == temp) {	
						return temp;
					}
					
					// 세 카드의 합이 이전 합보다 크면서 M 보다 작을 경우 result 갱신 
					if(result < temp && temp < M) {
						result = temp;
					}
				}
			}
		}
		
		// 모든 순회를 마치면 result 리턴 
		return result;
	}
}

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

위에서 부터 순서대로

 

채점 번호 : 19901303  -  방법 4 : BufferedReader

채점 번호 : 19901297  -  방법 3 : Scanner

채점 번호 : 19901293  -  방법 2 : BufferedReader

채점 번호 : 19901284  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

알고리즘의 경우 데이터가 워낙 적어 사실상 성능차는 안보이는 것 같다.

---

• 정리

 

브루트 포스 알고리즘은 조건에 만족하는 값을 100% 찾아낼 수 있다는 점에서 매우 강력하지만 너무나도 큰 단점이있다.

바로 자원이다.

 

이전에 필자가 소수를 구하는 알고리즘 포스팅에서 암호에 관해 잠깐 언급했듯이 자리수에 따라 경우의 수는 기하급수적으로 늘어난다.

예로들어 숫자와 소문자 조합의 개수만 탐색하더라도 n 개의 자리수 암호에 대해서 O(36ⁿ) 이 걸린다.

 

12 자리라 한다면 36¹² = 4,738,381,338,321,616,896 이다.. (약 470경)

 

초당 1억번 연산을 수행한다 한들 47383813383 초..

 

하루가 86400 초이니 548423일이 걸린다.

 

결과적으로 모두 탐색하는데 최악의 경우 대략 1502년이 걸린다는 의미다.

 

 

즉, 지금부터 브루트 포스 방식으로 때려넣으면서 하더라도

여러분의 후세대에 물려주거나, 의료가 발달하여 생명연장이 되길 빌어야 한다.

 

 

물론 병렬처리 방법을 동원하고 뭐.. 데이터의 크기야 어찌저찌해서 서버를 구했다고 치더라도 현재 있는 대부분의 암호화는 단순 소문자 + 숫자 조합이 아니기 때문에 (길이도 어마어마하다) 브루트 포스 방식으로는 풀 가능성이 0% 에 거의 가깝다. (우연히 때려맞추는 방법 밖엔..)

 

 

물론 성공사례도 있다. 여러분들은 아실련지 모르겠지만 김재열의 '청와대 해킹사건'이 대표적인 예다.

이 때 해킹 방법이 위와같이 브루트포스를 사용하여 대입해본 것이다. (그런데 비밀번호가 12345 였다더라...)

 

그러니 이번 기회에 비밀번호는 최대한 길게 하거나, 특수문자를 넣어 변경해보는 것은 어떨까?