TIL #9 브루트 포스 (1)

노력하는 배짱이·2020년 9월 2일
JavaTIL알고리즘
0

브루투 포스

브루트 포스는 모든 경우의 수를 다 해보는 것이다.
예를 들어 4자리의 숫자로만 이루어진 비밀번호를 알아내기 위해서 0000 ~ 9999까지 다 입력하는 방법이다.
이 경우의수는 10,000가지가 나오는데 비밀번호가 4자리가 아닌 더 긴 8자리 12자리 이면 경우의 수는 많아지고 시간은 오래 걸리게 된다.

따라서 브루트 포스로 문제를 풀려면 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다.

브루트 포스로 문제를 풀기 위해 3가지 단계가 있다.
1. 문제의 가능한 경우의 수를 계산한다.
2. 가능한 모든 방법을 다 만들어본다.
3. 각각의 방법을 이용해 답을 구해본다.

1번에 경우 대부분 손으로 직접 계산이 가능하다. 2번은 가능한 모든 방법을 빠짐 없이 만들어야 하며 대표적인 방법에는 for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다. 3번에서는 문제에 나와있는 대로 답을 계산하면 된다.

브루트 포스의 시간복잡도는 대부분 경우의수 * 1개 방법을 시도해보는데 걸리는 시간 복잡도 이다.

경우의 수(=방법의 수) 예시를 보자.
1. N명의 사람이 한 줄로 서는 경우의 수
    -> N!
2. N명의 사람 중에서 대표 두 명을 뽑는 경우의 수
    -> NC2_{N}\mathrm{C}_{2}
3. N명의 사람 중에서 반장 1명과 부반장 1명을 뽑는 경우의 수
    -> N∗(N−1)N*(N-1)

이렇게 경우의 수를 구하는 문제들이 있다.

문제 - 그냥 다 해보기

1. 문제 : 일곱 난쟁이

9명의 난쟁이 중 7명의 난쟁이를 찾는 문제이며 일곱 난쟁이의 키의 합은 100이다.
그러면 9명 중에서 7명을 뽑으면 되는데, 이는 9명에서 2명을 뽑는 것과 같다.
즉, 9C2=36_{9}\mathrm{C}_{2} = 36 이 나오게 된다. 36의 경우의수는 작기 때문에 오랜 시간이 걸리지 않아 이 방법을 사용할 수 있다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = 9;
		int[] a = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			sum += a[i];
		}
		Arrays.sort(a);
		for (int i = 0; i < n; i++) { // 하나의 난쟁이
			for (int j = i + 1; j < n; j++) { // 위의 하나의 난쟁이를 제외한 나머지 난쟁이
				if (sum - a[i] - a[j] == 100) {
					for (int k = 0; k < n; k++) { // 출력하는 부분
						if (i == k || j == k) {
							continue;
						}
						System.out.println(a[k]);
					}
					System.exit(0); // 문제에서 정답이 여러가지 인 경우 하나마 출력해야 함으로 사용
				}
			}
		}
	}

2. 문제 : 사탕 게임

NxN 크기의 테이블에 사탕이 있으며 인접한 두 칸을 골라 사탕을 교환한 뒤, 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제이다.

먼저 인접한 두 칸을 골라 사탕을 교환하는 경우의 수는 임의의 한칸에서 상하좌우로 교환이 가능하고 칸의 갯수는 N2N^2이기 때문에 4N24N^2이 나온다. 또 다른 방법으로는 임의의 한칸이 오른쪽 또는 아래쪽으로만 교환이 가능하다고 하면 2N22N^2 이 나온다.

따라서 문제를 풀 때 오른쪽을 기준으로 먼저 구해주고 아래를 구해주면 된다.
이 과정에서 중간에 교환을 해서 답을 구했으면 다시 원래대로 돌려 놓아야 한다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char[][] a = new char[n][n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.next().toCharArray();
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j + 1 < n) { // 오른쪽
					char t = a[i][j];
					a[i][j] = a[i][j + 1];
					a[i][j + 1] = t;
					int temp = check(a);
					if (ans < temp) {
						ans = temp;
					}
					t = a[i][j];
					a[i][j] = a[i][j + 1];
					a[i][j + 1] = t;
				}
				if (i + 1 < n) { // 아래
					char t = a[i][j];
					a[i][j] = a[i + 1][j];
					a[i + 1][j] = t;
					int temp = check(a);
					if (ans < temp) {
						ans = temp;
					}
					t = a[i][j];
					a[i][j] = a[i + 1][j];
					a[i + 1][j] = t;
				}
			}
		}
		System.out.println(ans);

	}

	public static int check(char[][] a) {
		int n = a.length;
		int ans = 1;
		for (int i = 0; i < n; i++) {
			int cnt = 1;
			for (int j = 1; j < n; j++) { // 행
				if (a[i][j] == a[i][j - 1]) {
					cnt += 1;
				} else {
					cnt = 1;
				}
				if (ans < cnt) {
					ans = cnt;
				}
			}
			cnt = 1;
			for (int j = 1; j < n; j++) { // 열
				if (a[j][i] == a[j - 1][i]) {
					cnt += 1;
				} else {
					cnt = 1;
				}
				if (ans < cnt) {
					ans = cnt;
				}
			}
		}
		return ans;
	}

3. 문제 : 날짜 계산

E, S, M 으로 표현되는 연도에서 E, S, M이 주어졌을 때 이게 몇 년인지 구하는 문제이다.
범위는 다음과 같다.
(1≤E≤15)(1 \leq E \leq 15), (1≤S≤28)(1 \leq S \leq 28), (1≤M≤19)(1 \leq M \leq 19)

이 문제이서 나올 수 있는 경우의 수는 15x28x19 = 7980 가지 이다. 수가 작기 때문에 브루트 포스로 문제를 해결할 수 있다.

for문을 무한루프로 돌려 e, s, m을 +1씩 해줌으로서 입력된 E, S, M과 같아지는 부분을 찾아 출력하면 된다. 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int E = sc.nextInt();
		int S = sc.nextInt();
		int M = sc.nextInt();
		int e = 1, s = 1, m = 1;
		for(int i=1;;i++) {
			if(e == E && s == S && m == M) {
				System.out.println(i);
				break;
			}
			e += 1;
			s += 1;
			m += 1;
			if(e == 16) {
				e = 1;
			}
			if(s == 29) {
				s = 1;
			}
			if(m == 20) {
				m = 1;
			}
		}

	}

4. 문제 : 리모컨

TV 채널을 바꾸는 문제인데, 이동하려는 채널 N으로 변경하기 위해서 고장난 버튼을 제외한 나머지 버튼과 +, - 버튼을 이용하여 최소한으로 버튼을 누르는 횟수를 구하는 문제이다.

예를 들어, 5457에 이동하려면 번호 5, 4, 5, 7를 눌러 4번만에 이동할 수 있다. 만약 버튼 7번이 고장났으면 5,4,5,6,+ 또는 5,4,5,8,-를 눌러 5번만에 이동할 수 있다.
문제 예시로 주어진 6,7,8이 고장난 경우에는 5,4,5,5,+,+ 또는 5,4,5,9,-,-를 눌러 6번만에 이동할 수 있는데 이 과정에서 절대 정답이 될 수 없는 경우가 2가지가 존재한다.

  1. 5,4,3,5,+,+,+,5,4,-,-,5,4,5,5,+,+ 이러한 형태
    이유는 +, - 뒤에 숫자가 나오면 이전에 입력한 버튼은 의미가 없어진다. 문제는 버튼을 누르는 횟수의 최소를 구하는 것이기 때문에 이 경우를 생각하면 안된다.

  2. 5,4,5,5,-,-,+,+,+,+ 형태
    이유는 - 뒤에 + 가 나오면 이전에 이동한 채널이 중복이 되며 이는 문제에서 요구한 최소를 구하는 것과는 거리가 멀어지기 때문이다.

따라서 숫자 버튼을 누르고 그 다음에 + 또는 - 중 하나만 연속해서 눌러야 한다.

추가적으로 고려해야하는 부분은 숫자 버튼을 눌러서 이동하는 채널이다. 문제에서 이동하려고 하는 채널 N의 범위가 최대 500,000으로 주어졌다. 또한 채널의 최대는 무한이기 때문에 숫자 버튼을 눌러서 이동하는 채널을 C라고 하면 C는 임의의 수 1,000,000 정도로 두고 문제를 해결 할 수 있다.

가장 처음에 보고 있는 채널이 100이라서 정답의 최대값은 500,000 - 100 을 넘지 않는다. 이제 숫자 버튼을 이용해 채널 c로 이동한 다음 거기서 + 혹은 - 버튼을 몇 번 눌러야하는지 계산을 하면 된다. 이때 + 혹은 -를 누르는 횟수 계산은 뺄셈으로 구할 수 있다.
아래 순서로 문제를 해결하면 된다.

  1. 이동할 채널 c를 정함
  2. c에 포함되어 있는 숫자 중에 고장난 버튼이 있는지 확인
  3. 고장난 버튼이 포함되어 있지 않다면 |c-n|을 계산하여 + 혹은 - 버튼을 몇 번 눌러야 하는지를 계산

2번 과정에서 확인하는 방법에는 2가지가 있다. 하나는 수를 문자열로 바꾸고 한글자씩 검사하는 방법이고 다른 방법은 수를 10으로 계속해서 나누면서 하나씩 검사하는 방법이다.

public static boolean[] broken = new boolean[10];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
			int x = sc.nextInt();
			broken[x] = true;
		}
		int ans = n - 100;
		if (ans < 0) {
			ans = -ans;
		}
		for (int i = 0; i <= 1000000; i++) {
			int c = i;
			int len = possible(c);
			if (len > 0) {
				int press = c - n;
				if (press < 0) {
					press = -press;
				}
				if (ans > len + press) {
					ans = len + press;
				}
			}
		}
		System.out.println(ans);

	}

	public static int possible(int c) {
		if (c == 0) {
			if (broken[0]) {
				return 0;
			} else {
				return 1;
			}
		}
		int len = 0;
		while (c > 0) {
			if (broken[c % 10]) {
				return 0;
			}
			len += 1;
			c /= 10;
		}
		return len;
	}

5. 문제 : 테트로미노

N x M 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 스여 있는 수의 합을 최대를 구하는 문제이다.
문제에서 주어진 도형이 5가지인데, 회전이 가능하다하여 총 19가지라고 할 수 있다.

그러면 해당 도형을 어디에 놓아야 하는 것인가?
문제에 주황색 도형을 기준으로 예시를 들으면 5 x 5 크기의 종이라 가정 했을 때, 주항색 도형의 맨 위 정사각형이 놓일 장소는 종이의 왼쪽 맨 위에서부터 3 x 4 부분에만 가능하고 나머지는 불가능 하다. 즉 (n-2) x (m-1) 부분이다.

따라서 시간복잡도 역시 O(NM)이 나오게 된다.
문제에서 N 과 M 의 최대 크기가 500이기 때문에 모든 경우의 수는 19∗500219*500^2이 된다.

이 문제는 브루트 포스로 가능하기 때문에 모든 경우를 다 구해주면 된다.

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] a = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (j + 3 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i][j + 3];
					if (ans < temp)
						ans = temp;
				}
				if (i + 3 < n) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 3][j];
					if (ans < temp)
						ans = temp;
				}
				if (i + 1 < n && j + 2 < m) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 1][j + 2];
					if (ans < temp)
						ans = temp;
				}
				if (i + 2 < n && j + 1 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 2][j];
					if (ans < temp)
						ans = temp;
				}
				if (i + 1 < n && j + 2 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j + 2];
					if (ans < temp)
						ans = temp;
				}
				if (i + 2 < n && j - 1 >= 0) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j - 1];
					if (ans < temp)
						ans = temp;
				}
				if (i - 1 >= 0 && j + 2 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i - 1][j + 2];
					if (ans < temp)
						ans = temp;
				}
				if (i + 2 < n && j + 1 < m) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 2][j + 1];
					if (ans < temp)
						ans = temp;
				}
				if (i + 1 < n && j + 2 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i + 1][j];
					if (ans < temp)
						ans = temp;
				}
				if (i + 2 < n && j + 1 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 2][j + 1];
					if (ans < temp)
						ans = temp;
				}
				if (i + 1 < n && j + 1 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
					if (ans < temp)
						ans = temp;
				}
				if (i - 1 >= 0 && j + 2 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i - 1][j + 1] + a[i - 1][j + 2];
					if (ans < temp)
						ans = temp;
				}
				if (i + 2 < n && j + 1 < m) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 2][j + 1];
					if (ans < temp)
						ans = temp;
				}
				if (i + 1 < n && j + 2 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j + 2];
					if (ans < temp)
						ans = temp;
				}
				if (i + 2 < n && j - 1 >= 0) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 1][j - 1] + a[i + 2][j - 1];
					if (ans < temp)
						ans = temp;
				}
				if (j + 2 < m) {
					int temp = a[i][j] + a[i][j + 1] + a[i][j + 2];
					if (i - 1 >= 0) {
						int temp2 = temp + a[i - 1][j + 1];
						if (ans < temp2)
							ans = temp2;
					}
					if (i + 1 < n) {
						int temp2 = temp + a[i + 1][j + 1];
						if (ans < temp2)
							ans = temp2;
					}
				}
				if (i + 2 < n) {
					int temp = a[i][j] + a[i + 1][j] + a[i + 2][j];
					if (j + 1 < m) {
						int temp2 = temp + a[i + 1][j + 1];
						if (ans < temp2)
							ans = temp2;
					}
					if (j - 1 >= 0) {
						int temp2 = temp + a[i + 1][j - 1];
						if (ans < temp2)
							ans = temp2;
					}
				}
			}
		}
		System.out.println(ans);

	}

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.

profile
노력하는 배짱이
이전 포스트

TIL #8 다이나믹 프로그래밍 (2)

다음 포스트

TIL #10 브루트 포스 (2)

0개의 댓글