[알고리즘] 완전 탐색 - 부분집합

요즘 알고리즘으로 코딩문제를 많이 풀어보고 있는데, 예전처럼 문제에 속도가 많이나지 않는 상황이 안타깝다..
많은 테스드 중에는 생길 수 있는 모든 상황에 대해 만들고, 그 값들이 결과와 일치하는 문제들이 많다보니까

부분집합을 만드는 코드가 유용해서 따로 정리하려고 한다.

 

비트 마스크를 이용해서 배열의 모든 부분집합을 구하는 코드이다.

column 배열의 원소들도 만들 수 있는 모든 조합을 includes 배열에 담는 내용이다.

 

1 << column.length 는

column.length === 4  → 1 << 4 → 16

즉, 0~15까지의 숫자의 이진 수 0000 부터 1111까지의 각 자리에 해당하는 값을 대입한다고 생각하면 된다.

배열이 [0,1,2,3]이 아닌 다른 배열이라도 적용된다.

 

비트마스크를 통해 각 자리의 포함 여부를 체크하여,

i & (1 << j) → i의 j번째 비트가 1인지 확인해서 1이면 column[j]를 부분집합에 포함하는 코드이다.

const included = [];
const column = [0,1,2,3];
for(let i=1; i<(1<<column.length); i++){
      const base = [];
      for(let j =0; j<column.length;j++){
          if (i & (1<<j)) base.push(column[j]);
      }
      included.push(base);
 }
 
 // included = 	[
//   [ 0 ],          [ 1 ],
//   [ 0, 1 ],       [ 2 ],
//   [ 0, 2 ],       [ 1, 2 ],
//   [ 0, 1, 2 ],    [ 3 ],
//   [ 0, 3 ],       [ 1, 3 ],
//   [ 0, 1, 3 ],    [ 2, 3 ],
//   [ 0, 2, 3 ],    [ 1, 2, 3 ],
//   [ 0, 1, 2, 3 ]
// ]

 

 

참고 자료: https://velog.io/@min00/JS-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-Exhaustive-Search-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9