브루트 포스(Brute Force)

브루트포스

• 브로트 포스는 모든 경우의 수를 다 해보는 것
• 브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있음.
  • 문제의 가능한 경우의 수를 계산
    • 직접 계산을 통해 구함. 대부분 손으로 계산해볼 수 있다.
  • 가능한 모든 방법을 다 만들어 봄
    • 하나도 빠짐 없이 만들어야 한다.
    • 대표적으로 그냥 다 해보는 방법. for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용 등이 있음.
  • 각각의 방법을 이용해 답을 구해봄
    • 문제에 나와있는 대로 풀어본다.
• 시간 복잡도: O(방법의 수 * 방법 1개의 시간 복잡도)

2차원 벡터 동적 할당

#include <vector>

//int arr[6][5] 배열 선언, 0으로 값 초기화
vector<vector <int>> arr(6, vector<int>(5, 0));

건너 뛰며 해보기(브루트포스)

• 모든 경우의 수를 시도해보는 것이 아니라, 필요한 것만 해보는 것.

N중 for문

• N개 중에 일부를 선택해야 하는 경우에 많이 사용
• 재귀 호출이나 비트 마스크를 사용하면 더 간결하고 보기 쉬운 코드로 작성할 수 있기 때문에 사용할 일이 거의 없다.

N과 M

• 재귀
• 순열
  • 브루트 포스로 문제를 풀어야 하는데, 순서가 중요한 의미를 가질 때 품.
• 비트마스크
  • 이 중, 재귀가 가장 중요. 순열과 비트마스크는 모두 재귀로 표현될 수 있기 때문

재귀를 사용하는 브루트포스

• 순서
• 선택

순열(Permutation)

• 임의의 수열을 다른 순서로 섞는 연산
• 모든 순서를 다 시도해보아야 할 때.

다음 순열(Next Permutation)

• 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법
• C++의 STL의 algorithm에는 이미 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다.

1. A[i-1]<A[i]를 만족하는 가장 큰 i를 찾는다O(N)
2. j>=i이면서, A[j]>A[i-1]를 만족하는 가장 큰 j를 찾는다O(N)
3. A[i-1]과 A[j]를 swap 한다.O(1)
4. A[i]부터 순열을 뒤집는다.O(N)

bool next_permutation(int *a, int n){
  int i = n-1;
  while(i>0 && a[i-1] >=a[i]) i -= 1; //1
  if(i <= 0) return false; //마지막 순열
  //2
  int j = n-1;
  while(a[j] <= a[i-1]) j-=1;
  //3
  swap(a[i-1], a[j-1]);
  j = n-1;
  //4
  while(i<j){
    swap(a[i], a[j]);
    i += 1; j -= 1;
  }
  return true;
}

Combination

• next_permutation(vec.begin(), vec.end()) 를 통해 구현할 수 있다.
• nCk를 구하고 싶은 경우, 새로운 vector com에 k개의 1과 n-k개의 0을 넣어준다.
• com을 sort(com.begin(), com.end(), greater<int>()) 을 통해 내림차순으로 정렬해준다.
• do, while 문으로 next_permutation(com.begin(), com.end()) 이 있을 때 까지 돌려준다!

백트래킹(Backtracking)

• 재귀 함수를 이용해 브루트포스를 하다 보면, 더 이상 함수 호출이 의미 없는 경우가 있다.
• 이 때, 이런 경우를 제외하고 브루트포스를 진행하는 것을 백트래킹이라고 한다.

비트마스크

• 비트(bit) 연산을 사용해서 부분 집합을 표현할 수 있다.
• xor은 둘 중에 하나만 1일 때만 1. 둘 다 1이거나 둘 다 0이면 0.

A	B	~A	A&B	A|B	A^B
0	0	1	0	0	0
0	1	1	0	1	1
1	0	0	0	1	1
1	1	0	1	1	0

• 정수로 집합을 나타낼 수 있다.

  • {1, 3, 4, 5, 9} = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9

  • 공간 절약의 장점.

  • 정수라는 장점.

  • 10	9	8	7	6	5	4	3	2	1
    0	1	0	0	0	1	1	1	0	1

• 보통 0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용한다.

• 1부터 N까지 정수로 이루어진 집합을 사용하는 것은 공간이 2배 더 필요하다.

• 또, 각종 연산을 조금 변형해서 사용해야 한다.

• 따라서, 0부터 N-1까지로 볂여해서 사용하는 것이 더 좋다.

비트 연산

• 두 수 A와 B를 비트 연산 하는 경우에는 가장 뒤의 자리부터 하나씩 연산을 수행하면 된다.
• not 연산의 경우에는 자료형에 따라 결과가 달라진다.
  • A=83=1010011
  • ~A=10101100(8bit)
  • ~A: 11111111 11111111 11111111 10101100(32bit)
  • 또, unsigned, signed에 따라서 보여지는 값이 다르다.
• shift 연산에는 shift left(<<)와 shift right(>>) 연산이 있다.
  • A>>B: A를 오른쪽으로 B비트만큼 민다.
  • 10 >> 2 = 2
• A<<B는 A*2^B와 같다.
• A>>B는 A/2^B와 같다.
• (A+B)/2는 (A+B)>>1로 쓸 수 있다.

비트마스크

• {1, 3, 4, 5, 9}

  • 0이 포함되어 있는지 검사
    • 570 & 2^0 = 570 & (1<<0) = 0
  • 1이 포함되어 있는지 검사
    • 570 & 2^1 = 570 & (1<<1) = 2
  • 2 추가하기
    • 570 | 2^2 = 570 | (1<<2) = 574 (100111110)
  • 3 추가하기(3이 이미 있어도 연산을 수행할 수 있음)
  • 1 제거하기
    • 570 & ~2^1 = 570 & ~(1<<1) = 568 (1000111000)