private k :: [기초] 브루트 포스

- 비트 연산을 사용해서 부분 집합을 표현할 수 있다.

비트 연산에 대해서 먼저 알아보자.

NOT 연산에서는 자료형에 따라 결과가 달라질 것이다.

비트마스크.

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

- 집합은 중복되는 수가 없다. -> 없으면 0 / 있으면 1로 처리할 수 있다.

-> 있는 수를 1로 없는 수를 0으로 하여 이진수로 바꿀 수 있다.

비트마스크의 장점

1. 공간을 적게 사용한다. (항상 정수 1개를 이용하여 집합을 표현할 수 있다.)

2. 정수라는 것. 배열에 넣기 편하다.

3. 검사 / 추가 / 삭제 이 모든 연산의 시간 복잡도가 O(1) 이다.

비트마스크를 쓰기 위한 조건

1. 아무 수나 있다고 하여 사용 가능한 것이 아니라, 적절한 범위가 필요함. 너무 큰 수라면 2^ 이 너무 커지기 때문이다.

S 에 X 가 있는지 검사하려면

$$ S \& (1 << X) $$

0 이 나오면 없는 것이다. 그 외의 값이면 ( 1 << X ) 있는 것이다.

이미 있는 수를 또 추가되어도 무시가 가능하다.

$$ S | ( 1 << X ) $$

$$ S \& \~(1 << X) $$

마찬가지로 없는 수를 지워는 작업도 오류가 나지 않는다.

$$ S ^ (1 << X) $$

브루트 포스보다도, 다이나믹 알고리즘을 풀 때 가장 많이 사용한다.

브루트 포스에서의 가장 추천하는 방식은 재귀이다.

브루트 포스의 단점은 정수라는 것이다. 왜냐하면, 32비트, 64비트 를 사용하기 때문에 그 이상의 수를 저장할 수 없다.

더 큰 수를 저장해야한다면 비트마스크는 적절한 방법이 아니다. 0 ~ 31 혹은 32 ~ 64 범위 일 때 사용해보자.

이것 보다 큰 비트마스크를 사용하려면 C++ 의 bitset 을 사용하면 되지만, 크게 쓸 일은 없다.

private k