[C++] 알튜비튜 4주차 - 브루트포스

브루트포스 

• 무차별 대입, 완전 탐색
• 해답을 찾기 위해 가능한 모든 경우의 수를 찾는 기법
• 시간복잡도는 입력크기에 비례
• 간단하지만 매우 느림 BUT 떠올리기 가장 쉬운 기법 -> 문제를 풀 때 가장 먼저 고려해야 한다.
• 입력범위와 시간복잡도를 잘 고려

 

분해합

• n의 분해합 = n과 n을 이루는 각 자리수의 합
• n의 생성자 = 분해합이 n인 어떤 자연수 m

 

비트마스킹

• 비트 필드 각각을 하나의 원소처럼 사용하는 기법 
• C++ 에서 int는 32비트의 공간을 사용 -> int 한 개로 32개의 원소 저장 가능
• 산술 연산보다 빠른 연산 수행가능
• 1개의 int만으로 32개의 원소를 저장하는 효과
• 효율적 메모리사용
• DP, 백트래킹 등 방문 여부를 저장해야 하는 알고리즘에 사용 

 

비트연산자

• AND(&) : int ans = a & b;
  • 1100 과 1001 -> 1000 : 둘 다 1일때만 1, 나머지는 0
• OR(|) : int ans = a | b;
  • 1100 과 1001 -> 1101 : 둘 다 0일때만 0, 나머지는 1
• XOR(^) : int ans = a ^ b;
  • 1100 과 1001 -> 0101 : 두 비트가 다를때만 1, 같을때는 0
• NOT(~) : int ans = ~a;
  • 1100 -> 0011 : 각 비트를 반대로 바꿔준다.
• LEFT SHIFT(<<) : int ans = a << 3; 
  • 000000100101 -> 000100101000 : 왼쪽으로 3비트 이동
• RIGHT SHIFT(>>) : int ans = a >> 3;
  • 010011010000 -> 00010011010

비트마스킹의 활용

• x{1,2,5,10,15} 와 13 의 합집합

int x=33830; //(100010000100110)_2
int y= 1 << 13;
int ans = x | y; // x | (1 << 13)

 

1. 수학, 구현 : 입력 데이터 값 자체의 특성이나 규칙 활용
2. 브루트포스, 백트래킹 : 모든 가능한 경우의 수를 탐색할 때 비트마스킹으로 가능한 부분집합을 효율적 표시
3. 그래프 탐색(BFS 등) : N번째 노드의 방문여부 저장하기 위해, 여러개의 조건을 따져야 하는 경우 각 조건의 만족여부를 저장하기 위해 사용
4. 다이나믹 프로그래밍(DP) : 각 조합별 가능한 경우의 수를 DP배열에 저장, 각 부분집합에 새로운 원소가 추가됐을 때의 경우의 수를 DP로 계산