[코딩테스트] 브루트 포스

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

브루트 포스

  • 브루트 포스는 모든 경우의 수를 다 해보는 것이다.
  • 문제 방법 제시되고 다 해보는 것. 경우의 수를 아는 게 중요하다.
  • 방법의 개수가 크지 않을 때만 가능.
    1. 문제의 가능한 경우의 수를 계산한다
      • 직접 계산을 통해서, 대부분 손으로 계산 가능
    2. 가능한 모든 방법을 다 만들어본다
      • 하나도 빠짐 없이 만들기. ex) for문 사용/순열 사용/재귀 호출 사용, 비트마스크 등
    3. 각각의 방법을 이용해 답을 구해본다
  • 시간복잡도 : O(방법의 개수 x 시도하는 복잡도)
  • N! 일땐 보통 N≤10 조건이 같이 나올것, 2ⁿ일땐 N≤20

일곱 난쟁이(2309번)

https://www.acmicpc.net/problem/2309
문제
아홉 명의 난쟁이 중 일곱 명의 난쟁이를 찾는 문제, 일곱 난쟁이 키의 합은 100

출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

풀이

  • 고르는 경우의 수
  1. 9명 중에 7명 찾기
  2. 9명 중에 2명 찾기 = 9C2 = 9x8/2x1 = 36 즉 O(N²)
  • 키의 합을 고르는 시간 복잡도 O(N)
  • 즉 문제 시간복잡도는 O(N³)이나 이 문제는 O(N²) 방식으로 해결할 수 있음. 난쟁이의 키는 변하지 않기 때문에 1. 모든 키의 합을 구함(sum) 2. sum - A[i] - A[j] 는 O(1)과 같기 때문에 O(N²) 가능함.
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int arr[] = new int[9];
		int sum = 0;
		boolean chk = false;

		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
			sum += arr[i];
		}
		int aws = sum - 100;

		for (int i = 0; i < arr.length; i++) {
			if(chk) break;
			for (int j = 0; j < arr.length; j++) {
				if(i==j) continue;
				if (arr[i] + arr[j] == aws) {
					arr[i] = 0;
					arr[j] = 0;
					chk=true;
					break;
				}
			}
		}
		Arrays.sort(arr);

		for (int i = 0; i < 9; i++) {
			if (arr[i] != 0) {
				System.out.println(arr[i]);
			}
		}
	}
}

-> 처음에 풀 때 if(chk) break;를 안 넣었더니 시간복잡도에서 걸린건지 76프로에서 넘어가질 않았다. 답은 나오는데 자꾸 틀려서 답답했는데ㅠㅠ 답을 찾으면 다 돌지 않고 끊게 해주는게 중요하단걸 배웠다..

사탕 게임(3085번)

https://www.acmicpc.net/problem/3085
문제
NxN 크기의 테이블에 사탕이 있다(N≤50), 인접한 두 칸을 고르고 사탕을 교환, 그 다음 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제.

출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

풀이

  • 인접한 두 칸 : 한칸을 고르고 인접한 4개를 고름. 전체칸 N² x 4 = O(N²)
  • 가장 긴 연속 부분 : 모두 검사해주기 O(N²)
  • 총 시간복잡도 O(N⁴) 1억이 1초정도 걸린다 가정할시 6백만(50⁴)은 가능
  • 방법 갯수는 줄일 수 없지만, 길이 재는 건 O(N)으로 줄일 수 있음. 임의 두 칸 변경했을 때, 정답 변화 있는 건 최대 3개의 행과 열(3N)이므로 중복연산을 줄일 수 있다(O(N)). 따라서 총 시간 복잡도 O(N³)
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		char arr[][] = new char[n][n];
		for (int i = 0; i < n; i++) {
			String str = sc.next();
			for (int j = 0; j < n; j++) {
				arr[i][j] = str.charAt(j);
			}
		}

		int ans = 0;
		// 바꾸기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j + 1 < n) {
					char t = arr[i][j];
					arr[i][j] = arr[i][j + 1];
					arr[i][j + 1] = t;
					int temp = check(arr);
					if (ans < temp)
						ans = temp;
					t = arr[i][j];
					arr[i][j] = arr[i][j + 1];
					arr[i][j + 1] = t;
				}

				if (i + 1 < n) {
					char t = arr[i][j];
					arr[i][j] = arr[i + 1][j];
					arr[i + 1][j] = t;
					int temp = check(arr);
					if (ans < temp)
						ans = temp;
					t = arr[i][j];
					arr[i][j] = arr[i + 1][j];
					arr[i + 1][j] = t;
				}
			}
		}

		System.out.println(ans);
	}

	private static int check(char[][] arr) {
		// 갯수 세기
		int temp = 0;
		for(int i=0; i<arr.length; i++) {
			int cnt = 1;
			for(int j=1; j<arr.length; j++) {
				if(arr[i][j]==arr[i][j-1]) {
					cnt++;
				} else {
					cnt = 1;
				}
				if(temp < cnt) {
					temp = cnt;
				}
			}

			cnt = 1;
			for(int j=1; j<arr.length; j++) {
				if(arr[j][i]==arr[j-1][i]) {
					cnt++;
				} else {
					cnt = 1;
				}
				if(temp < cnt) {
					temp = cnt;
				}
			}
		}
		return temp;
	}
}

-> 시간복잡도 O(N³)으로 줄이는 방식은 check 메소드에 넘기는 걸 start_row, end_row, start_col, end_col 을 지정해 넘겨 바뀌는 곳의 행과 열을 지정해줘야 한다. 위에 쓴 방식은 전체를 검사해서 좀 더 비효율적…

블랙잭(2798번)

https://www.acmicpc.net/problem/2798
문제
카드 합 21 넘지 않는 한도 내, 합을 최대한 크게 만들기. N장의 카드 딜러 숫자 M, N장의 카드 중 3장의 카드 고르기(≤M, M과 최대한 가깝게)

입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000), 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수, 합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어짐.

출력
첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

해설

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] card = new int[n];
		for (int i = 0; i < n; i++) {
			card[i] = sc.nextInt();
		}

		int ans = 0;
		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				for (int l = j + 1; l < n; l++) {
					int sum = card[i] + card[j] + card[l];
					if (ans < sum && sum <= m) {
						ans = sum;
					}
				}
			}
		}
		System.out.println(ans);
	}
}

-> 경우의 수는 N(N-1)(N-2) = N³, 시간복잡도는 O(N³)이다. 더 좋은 풀이법은 카드 한 장이 M보다 클 경우 / 두번째 합이 M보다 클 경우 조건문을 달아 작성하는 것. int l = i+2로 적고 돌리는 바람에 한참 뻘짓했다 슬프다..

댓글남기기

최근 포스트