비트마스킹 사용에 관한 질문입니다.

작성한 질문수 2

1

안녕하세요 구인님 ㅎㅎ

1.경우의 수를 탐색하는 문제에서 사용하는 것 같은데 나중에는 무조건 비트마스킹을 사용해야만 하는 문제도 있나요? 아니면 이 문제처럼 그냥 완전탐색으로 풀어도 대부분 풀리는 건지 궁금합니다!

>> 모든 경우의 수를 탐색할 때 비트마스킹을 쓰면 좀 더 간단해집니다. (다만 완탐으로 풀어도 상관은 없습니다.)

nC1, nC2, nC3 .. 이런식으로 모든 경우의 수를 탐색해야 할 때는 비트마스킹 쓰는게 좋습니다. (코드가 더 간단해짐)

하지만 n이 30이하 또는 31 이하 일 때만 사용가능하다는 제약조건이 있긴 합니다.

2. 비트마스킹의 장점은 속도 인가요? 시간 초과가 타이트할 때 사용하는 건지 아니면 다른 장점이 있는 건지 궁금합니다.

>> 네 속도가 빠릅니다. 기본적으로 재귀함수보다는 비트마스킹 - 반복문 돌려서 하는게 더 빠릅니다.

코드리뷰.

	for (int i = now; i < n; i++)
	{
		choice.push_back(i);
		food[0] += foods[i][0];
		food[1] += foods[i][1];
		food[2] += foods[i][2];
		food[3] += foods[i][3];
		select(i + 1, price + foods[i][4]);
		choice.pop_back();
		food[0] -= foods[i][0];
		food[1] -= foods[i][1];
		food[2] -= foods[i][2];
		food[3] -= foods[i][3];

	}

근데 정말 대단하시네요 ㅎㅎ

다이어트를 이렇게 푸신건 아마 구인님이 처음이신 것 같아요. i + 1해서 하신 것도 좋고... 코드가 깔끔하고 너무 좋습니다.

아름다움 그 잡채네요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.