비트 마스킹

비트란?

컴퓨터가 다루는 최소 단위의 데이터

0과 1만 표시 가능

비트로 표시하면 메모리도 절약되고 방문한 도시가 어디인지 편리하게 확인할 수 있다.( [true, false, false, true] )

비트 연산

AND 연산(=곱 연산/ &) : 두 입력이 모두 1인 경우에만 결과가 1
OR 연산(=합 연산 / |) : 두 입력 중 하나라도 1인 경우에 결과가 1
XOR 연산(^) : 입력에서 1의 계수가 홀수이면 결과가 1
비트 시프트 연산자 : << 또는 >>를 사용 모든 비트가 왼쪽으로 n칸 이동한다 (왼쪽으로 한 칸 이동할 때마다 2를 곱한 효과가 나타난다) 모든 비트가 오른쪽으로 n칸 이동한다 (오른쪽으로 한 칸 이동할 때마다 2를 나눈 효과가 나타난다)

비트 마스크란?

본인이 원하는 비트를 컨트롤 할 수 있는 방법

만약 1001 로 비트가 있을 때 2번째 비트를 1로 만드는 경우라면 논리 합을 이용하면 된다. 먼저 비트 시프트 연산자를 사용해 왼쪽으로 두 칸 옮기면 0100 이 되고, 1001과 0100을 합 연산(XOR 연산) 해주면 1101이 된다. 여기서 비트 시프트 연산자를 사용해 변경된 비트(0110)를 비트 마스크라고 부르고 대상 비트에 AND나 OR같은 연산으로 마스크를 씌위는 행위를 비트 마스킹이라고 한다.

🤔🤔 외판원 문제

외판원에 있는 도시에서 모든 도시를 한 번씩만 방문하고 다시 출발 도시로 오는 최소 비용의 경로를 구하는 문제

NP-Hard 문제이다.
최소 비용의 경로를 구하려면 모든 경로를 전부 구해서 그중에 최소 비용인 것을 선택해야 한다.
O(n^n)의 성능, 즉 지수 시간의 성능을 가진다.
너무 낮은 성능을 보이므로 동적 프로그래밍을 활용해 해결해야한다.

노드가 하나씩 증가할 때마다 팩토리얼 형태로 증가한다. ex) 노드가 3개일 때 2!, 4개일 때 3!, 5개일 때 4!

T(a, {b, c, d}) : a에서 출발해 b, c, d를 방문하는 최소 비용을 구하는 식

구현

const costs = [
	[0, 2, 9, 0],
	[1, 0, 6, 4],
	[0, 7, 0, 8],
	[6, 3, 0, 0]
]

// 계산 결과를 저장할 배열 선언
// 배열의 크기 == 각 도시에서 방문할 수 있는 모든 도시의 조합의 총 개수
// Array.from(행의 개수, 열의 개수)
// 행의 개수는 도시의 수 만큼
// 열의 개수는 도시의 수가 만들어 낼 수 있는 경우의 수보다 1 적은 만큼
// 1 << cost.length : 1(0001)을 왼쪽으로 4번 시프트 시키면 16(10000)이 된다.
const dp = Array.from(Array(costs.length), () => Array((1 << cost.length) - 1).fill(Infinity));

// 여기서 visited_cities는 비트 마스크. 방문한 모든 도시를 순서대로 오른쪽부터 0 또는 1로 표시 
function tsp(city, visited_cities) {
	// 기저조건 : 모든 도시를 방문한 경우
	if(visited_cities == (1 << costs.length) - 1) {
		// 0번에서 출발했으므로 0번 열을 참조해 리턴
		return costs[city][0];
	}
	
	// 메모이제이션으로 이미 계산한 결과가 존재하는 경우
	if(dp[city][visited_cities] != Infinity) {
		return dp[city][visited_cities];
	} else {
		for(let i = 0; i < costs.length; i++) {
			// 방문하지 않았고 자기 자신이 아닌 경우
			if((visited_cities & (1 << i)) == 0 && costs[city][i] != 0) {
				// 재귀적으로 호출하고 이 중에서 가장 작은 값을 결과로 저장
				dp[city][visited_cities] = Math.min(dp[city][visited_cities], costs[city][i] + tsp(i, visited_cities | (1 << i)));
			}
		}
		// 최솟값을 리턴
		return dp[city][visited_cities];
	}
}