최근에 본 코딩테스트에서 비트마스킹과 관련한 문제가 나왔다(물론 풀지 못해서 정확히 비트 마스킹 문제인지는 확신하지 못한다ㅎㅎ). 이전에 바킹독님의 알고리즘 영상을 정주행 하던 중 비트마스킹이 어렵기도 하고 자주 출제되는 범위는 아닌지라 그냥 포기했었다. 이번 기회에 가장 기본적인 문제라도 풀면서 기본적인 개념은 짚고 넘어가고자 한다.

사실 이 문제는 백트래킹을 사용해 부분집합을 구해줘도 된다. 하지만 비트 마스킹으로 풀 수 있는 최적의 문제라서 문제집에 넣어두었겠지 싶어서 해당 접근법을 사용하려고 한다.

🤔접근

비트 마스킹 기법에서 중요하게 고려할 요소는 대략 아래와 같다.

• 연산자의 우선순위가 상대적으로 낮다.
• 여러 상태를 한 정수로 표현할 수 있다.

컴퓨터구조 시간 때 비트 연산을 이해하기 위해, 아래와 같은 여러 전구가 켜지고 꺼져있는 상태의 그림을 본 적이 있을 것이다.

[출처: 혼자 공부하는 컴퓨터 구조+운영체제]

이 문제에서 이중 for 문의 바깥 for 문의 i가 한 전구 조합을 나타내는 대표값(정수)라고 생각하면 쉽다. 단, 전구가 모두 꺼져있는 공집합은 고려할 필요가 없으므로 i는 1부터 시작한다. 이후 안쪽 for 문의 & 연산에서 이 대표값은 전구의 켜짐/꺼짐 상태를 대변하게 된다. & 연산을 통해 각 자리(2^0, 2^1, ..., 2^(n-1))에 해당하는 수가 1(켜짐)인지 0(꺼짐)에 따라 sum 변수에 더해주는 것이다.

😎풀이

const readline = require('readline');
let n,arr=[],ch=Array(2000001).fill(0)

const sol=()=>{
	for(let i=1;i<(1<<n);i++){
		let sum=0
		for(let j=0;j<n;j++){
			if(i&(1<<j)){
				sum+=arr[j]
			}
		}
		ch[sum]=1		
	}
}
	
(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	for await (const line of rl) {
		if(!n){
			n=+line
		}else if(!arr.length){
			arr=line.split(' ').map(e=>+e)
		}
		if(n&&arr.length){
			rl.close();
		}
	}
	
	sol()
	const ans=ch.indexOf(0,1) // 1 이상의 정수 중 첫 번째로 없는 수 반환
	console.log(ans)
	
	process.exit();
})();