알고리즘 학습 요약 1

알고리즘을 공부하기 시작할텐데 시작 전에 한번 내용을 정리하고 가는 시간을 갖자!

비트 마스킹

내가 가장 중요하게 생각하는 것은 항상 "왜" 이다.

왜? 비트 마스킹을 사용해야 하는 걸까?

비트마스킹은 이진수의 특성을 활용해서 좀 더 가볍고 빠르게 연산을 할 수 있도록 해준다!

예를 들면

배열의 어떤 요소를 찾을 때 선형적인 시간 : O(N)
sorted array에서 이분 탐색으로 찾을 때 : O(logN)
해싱테이블에서는 O(1)
불리언 배열에서 찾을 때 find메서드를 쓰는 등 방법이 있음

하지만 이런 것들보다 불리언배열의 역할을 하는 "하나의 숫자"를 만들어서 "비트 연산자"를 통해 탐색, 수정 등의 작업을 하는 것을 비트마스킹이라고 함!

불리언배열 {0,1,0,1} 은 하나의 수 5라고 표현하면 5 가 0101이라는 불리언 배열의 역할이 가능하다!

특히 유용한 것은 경우의 수 조합같은 부분에서 활용 가능성이 높음!

#include <bits/stdc++.h>
using namespace std;
const int n = 4;
int main() {
string a[n] = {"사과", "딸기", "포도", "배"};
for(int i = 0; i < (1 << n); i++){
string ret = "";
for(int j = 0; j < n; j++){
if(i & (1 << j)){
ret += (a[j] + " ");
}
}
cout << ret << '\n';
}
return 0;
}

/*
사과
딸기
사과 딸기
포도
사과 포도
딸기 포도
사과 딸기 포도
배
사과 배
딸기 배
사과 딸기 배
포도 배
사과 포도 배
딸기 포도 배
사과 딸기 포도 배
*/

BUT 비트마스킹도 한계가 있음 바로 31까지 가능하다는 점!

int형 숫자의 범위까지만 가능하다! (long은 왜? : 2^30 만 해도 이미 시간복잡도가 10억)

본격적 학습 전에 비트마스킹의 전반적인 내용을 학습했다 꽤 유용할 것 같다!!