브루트 포스
- 모든 경우의 수를 다 해보는 알고리즘
- 브루트 포스에서 가장 중요한것은 경우의 수가 모두 몇가지인지 미리 아는것이다.
- 브루트 포스는 방벙의 개수가 크지 않은 경우에만 사용할수있다.
단계
- 문제의 가능한 경우의 수를 계산해본다.
- 가능한 모든 방법을 다 만들어본다.
- for문
- 순열
- 재귀 호출 ★★
- 비트 마스크
- 각각의 방법을 이용해서 답을 구해본다.
시간 복잡도
= O(방법의 개수 x 시도하는 복잡도)
단계1
경우의 수 계산
• N명의 사람이 한 줄로 서는 경우의 수 → N!(N<=10)
• N명의 사람 중에서 대표 두 명을 뽑는 경우의 수 → O(N^2)
• N명의 사람 중에서 대표 세 명을 뽑는 경우의 수 → O(N^3)
• N명의 사람 중에서 반장 1명과 부반장 1명을 뽑는 경우의 수 → O(N^2)
• N명의 사람이 있을 때, 각 사람이 영화를 볼지, 보지 않을지 결정한다. 가능한 조합의 수 → O(2^N)
->N번 사람당 2가지의 선택이 있기 때문에 22...... =2를 N번 곱하면 됨 (N<=20)
문제 1 ) 2309번 일곱 난쟁이
문제
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
예제 입력 1
20
7
23
19
10
15
25
8
13
예제 출력 1
7
8
10
13
19
20
23
내가한 구현
조합으로 순서 상관없이 7개만 먼저 뽑고
조합 합이 100인 것만 배열에 넣다가 마지막에 넣어진 조합이 출력
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int[] answer;
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
if (r == 0) {
print(arr, visited, n);
return;
}
for (int i = start; i < n; i++) {
visited[i] = true;
combination(arr, visited, i + 1, n, r - 1);
visited[i] = false;
}
}
// 배열 출력
static void print(int[] arr, boolean[] visited, int n) {
StringBuilder sb = new StringBuilder();
int[] temp = new int[7];
int sum = 0;
int index=0;
for (int i = 0; i < n; i++) {
if (visited[i]) {
sum+=arr[i];
temp[index] = arr[i];
index++;
}
}
if(sum==100)
{
answer = Arrays.copyOf(temp, temp.length);
return;
}
return;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int count = 0;
int N = 9;
int[] arr = new int[N];
answer = new int[7];
boolean[] visited= new boolean[N];
for(int i=0; i<N;i++)
arr[i] = Integer.parseInt(reader.readLine());
combination(arr, visited,0,N,7);
Arrays.sort(answer);
for(int num : answer)
sb.append(num+"\n");
System.out.println(sb);
}
}인강 내용
나는 9중에 7을 뽑았는데 인강에서는
9명중에 2명을 뽑는 경우의 수 별로 없기때문에
2명 뽑는것이 best
=> 방법의 개수 : N^2
• 난쟁이의 수를 N이라고 했을 때
• 두 명을 고르는 경우의 수: N^2 라고 할 수 있다.
• 나머지 난쟁이의 키의 합을 고르는 시간 복잡도: O(N)
• 따라서, 이 문제는 O(N^3) 으로 해결할 수 있다.
그치만 O(N^2)으로도 풀수있다.
난쟁이의 키는 변하지 않음
1. 먼저 모든 난쟁이의 키 합을 저장
2. i,j (9명 중 빠지는 두명)
sum-A[i]-A[j] == 100 => O(1)
문제 2 ) 3085번 사탕게임
문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입력 1
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
예제 출력 1
4
과정
• N×N 크기의 테이블에 사탕이 있다. (N ≤ 50)
• 인접한 두 칸을 고르고, 사탕을 교환한다
-> 먼저 한칸을 고르고 그 칸의 입접한 4칸중 다른 한칸을 보면됨
-> 한칸을 뽑는 것은 N^2 x 4(인접한 4칸) = O(N^2)
• 그 다음, 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제
-> 어디가 긴지 모두 검사해야함 -> O(N^2)
=> O(N^4) -> 50^4 = 2500^2 = 6250000 => 가능
구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static char[][] arr;
public static void swap(int i, int j, int ii, int jj) {
char temp = arr[i][j];
arr[i][j] = arr[ii][jj];
arr[ii][jj] = temp;
}
static int check(char[][] a, int start_row, int end_row, int start_col, int end_col) {
int n = a.length;
int ans = 1;
for (int i=start_row; i<=end_row; 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;
}
}
for (int i=start_col; i<=end_col; i++) {
int 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;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(reader.readLine());
// NxN
long max = -999;
int temp_num=0;
arr = new char[N][N];
for (int i = 0; i < N; i++)
arr[i] = reader.readLine().trim().toCharArray();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j + 1 < N) {
swap(i, j, i, j + 1);
temp_num = check(arr, i, i, j, j+1);;
if (max<temp_num)
max=temp_num;
swap(i, j, i, j + 1);
}
if (i + 1 < N) {
swap(i, j, i + 1, j);
temp_num = check(arr, i, i+1, j, j);;
if (max<temp_num)
max=temp_num;
swap(i, j, i + 1, j);
}
}
}
System.out.println(max);
}
}
