Programming/Python

비트마스킹

안녕하세요 laeto입니다. 이번 글에서는 비트마스크에 대해 다뤄보도록 하겠습니다. 비트 마스크란? 컴퓨터의 최소 연산 단위는 bit입니다. bit는 이진수를 나타내기 위해 0과 1로만 이루어져 있죠. 우리는 이 비트 연산을 이용하여 문제를 빠르게 풀 수 있습니다. 예를 들어, 많은 알고리즘 문제에서 방문을 체크하는 리스트가 존재할 수 있습니다. 가령 10곳을 우리가 방문 체크해야 한다면 기존에는 아마 아래처럼 리스트를 이용하여 확인할 수 있습니다. visited = [False] * 10 하지만 비트마스크 기법을 이용한다면 똑같이 표현할 수 있습니다. visited = 0b0000000000 비트마스크에서 각 비트는 하위 주소(오른쪽)부터 인덱스를 세면 됩니다. 예를 들어 4번째 도시를 우리가 방문했다..