비트마스킹(백준 알고리즘 2961번)

♣ 비트마스킹 개념

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 한다. 비트마스크를 사용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다. 

 

♣ 비트 연산자

 

♣ 비트를 이용한 집합 연산

 

1. 원소 추가

현재 상태 bit가 있을 때 x번 원소를 추가한다고 하자. 현재 상태 bit에서 x번 비트를 1로 바꿔줘야 한다. 

bit = bit | (1<<x)

 

2. 원소 삭제

현재 상태 bit에서 x번 원소를 삭제한다. 현재 bit에서 x번 비트를 0으로 바꿔줘야 한다. 

bit = bit & ~(1<<x)

 

3. 원소 토글

x번 비트가 1이면 0, 0이면 1로 바꾼다. 

bit = bit ^ (1<<x)

 

 

♣ 백준 알고리즘  2961번

 

 

 

 

음식을 만드는데, 한 가지 이상의 재료를 사용해야 하는 문제이다. 각 재료에는 신맛과 쓴맛이 모두 들어가고, 요리를 만들고 나서 요리에서 나는 신맛은 들어간 재료의 신맛을 모두 곱한 값이고, 쓴맛은 들어간 재료의 쓴맛을 모두 합한 값이다. 

 

재료를 선택하는 경우의 수를 모두 따져야 한다. 비트마스킹을 이용하여 전체 집합에 대해 부분 집합을 만든다고 생각하면 편하다. 모든 조합 중 신맛의 정도와 쓴맛의 정도 차가 가장 작은 값을 구한다. 

 

 

먼저 for문을 사용하여 각 재료의 신맛 정도와 쓴맛 정도를 받아온다. 부분 집합으로 만들 수 있는 신맛 정도와 쓴맛 정도 조합의 차이 중 가장 작은 값을 구할 예정이므로 정답인 answer에 Max를 넣어준다. 

 

그 뒤에는 이중 for문을 작성한다. 첫 번째 for문은 가능한 부분집합을 만드는 역할을 한다. 

만약 입력에서 n = 4, foods = [(1, 7), (2, 6), 3, 8), (4, 9)] 라고 해보자. 

 

1 << n 은 1을 n만큼 오른쪽으로 민다는 것을 의미한다. 입력에서 n이 4이므로 10000 이다. 

즉 item의 범위가 1부터 10000(2) 이므로 가능한 item은 아래와 같다. 

 

0001 = 첫 번째 재료만 넣음
0010 = 두 번째 재료만 넣음
0011 = 첫 번째, 두 번째 재료만 넣음
0100 = 세 번째 재료만 넣음
0110 = 첫 번째, 세 번째 재료만 넣음
0101 = 첫 번째, 두 번째 재료만 넣음
0111 = 첫 번째, 두 번째, 세 번째 재료만 넣음
1000 = 네 번째 재료만 넣음
1001 = 첫 번째, 네 번째 재료만 넣음
1010 = 두 번째, 네 번째 재료만 넣음
1100 = 세 번째, 네 번째 재료만 넣음
1011 = 첫 번째, 두 번째, 네 번째 재료만 넣음
1101 = 첫 번째, 세 번째, 네 번째 재료만 넣음
1110 = 두 번째, 세 번째, 네 번째 재료만 넣음
1111 = 네 가지 재료 모두 넣음

 

재료를 적어도 한 가지는 넣어야 하므로 0000은 제외해서 가능한 부분 집합이 총 15개가 된다. 

이제 부분 집합을 만들었으니, 각 부분 집합에서의 신맛과 쓴맛을 계산하고, 두 맛 사이의 차 중 가장 작은 값을 answer로 저장하여 구하면 된다. 

 

 

(item & (1<<j)) 는 현재의 상태에서 j 번째 재료가 1인지를 확인하는 것이다. 그래서 j 번째 재료가 1이면(0이 아니면) 해당 재료의 신맛과 쓴맛을 곱하고 더해서 계산한다. 

 

예를 들어 현재 item이 1001 이고 j가 0이라면 item에서 0번째 숫자를 확인하는 것이다. 이 문제에서 치면 첫 번째 재료를 사용했는지 확인하는 것이다. 1001 에서 첫 번째 재료를 쓰고 있으므로(0번째의 숫자가 1이므로) 0이 아니라는 조건에 맞는다. 그러면 신맛과 쓴맛을 계산한다. 

 

j가 1, 2 일때는 1001에서 두 번째, 세 번째 재료를 사용하고 있지 않으므로 조건을 만족하지 못하고, j가 3일 때는 네 번째 재료를 사용하고 있으므로 조건을 만족한다. 따라서 부분 집합 1001 의 신맛과 쓴맛은 아래와 같이 계산된다. 

 

s * 첫 번째 재료의 신맛 * 네 번째 재료의 신맛

b + 첫 번째 재료의 쓴맛 + 네 번째 재료의 쓴맛

 

이런 식으로 부분 집합이 가지는 신맛과 쓴맛을 계산해서 그 차를 구한다. 그리고 그 중 가장 작은 값을 answer에 부여한다. 

 

 

♣ 참고 자료

https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC

[Python] 비트 마스킹 정리

https://travelbeeee.tistory.com/451

[알고리즘] 비트마스킹(bitmasking) 이란

https://hongcoding.tistory.com/82

[백준] 11723 집합 (파이썬 비트마스크)

https://sjevie.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BOJ-2961%EB%B2%88-%EB%8F%84%EC%98%81%EC%9D%B4%EA%B0%80-%EB%A7%8C%EB%93%A0-%EB%A7%9B%EC%9E%88%EB%8A%94-%EC%9D%8C%EC%8B%9Dpython3

[알고리즘] BOJ 2961번 - 도영이가 만든 맛있는 음식(python3)