📌 비트 시프트 연산 (Bit Shift Operation)

이진수(2진수) 비트를 좌측(왼쪽) 또는 우측(오른쪽)으로 이동시키는 연산

C++에서는 <<(왼쪽 시프트)와 >>(오른쪽 시프트) 연산자를 사용

---

✅ 1. 왼쪽 시프트 (<<)

1 << n

• 비트를 왼쪽으로 n번 이동시키는 연산
• 결과적으로 2^n과 동일한 값이 됨

📌 예제

#include <iostream>
using namespace std;

int main() {
    cout << (1 << 0) << endl; // 1 (2^0)
    cout << (1 << 1) << endl; // 2 (2^1)
    cout << (1 << 2) << endl; // 4 (2^2)
    cout << (1 << 3) << endl; // 8 (2^3)
    cout << (1 << 4) << endl; // 16 (2^4)
    return 0;
}

🔹 출력 결과

1
2
4
8
16

💡 즉, 1 << n은 2^n과 같은 의미!

✅ 비트 이동 과정

1 << 3  // 1을 왼쪽으로 3칸 이동
0000 0001  (1)  →  0000 1000  (8, 즉 2^3)

---

✅ 2. 오른쪽 시프트 (>>)

n >> m

• 비트를 오른쪽으로 m번 이동시키는 연산
• 결과적으로 n을 2^m으로 나눈 것과 같음 (정수 나눗셈)

📌 예제

#include <iostream>
using namespace std;

int main() {
    cout << (16 >> 1) << endl; // 8  (16 / 2^1)
    cout << (16 >> 2) << endl; // 4  (16 / 2^2)
    cout << (16 >> 3) << endl; // 2  (16 / 2^3)
    cout << (16 >> 4) << endl; // 1  (16 / 2^4)
    return 0;
}

🔹 출력 결과

8
4
2
1

✅ 비트 이동 과정

16 >> 3  // 16을 오른쪽으로 3칸 이동
0001 0000  (16)  →  0000 0010  (2, 즉 16 / 2^3)

---

✅ 3. 왼쪽 시프트와 오른쪽 시프트의 차이

연산 의미 예제 결과

1 << n	2^n 배 증가	1 << 4	16
n >> m	2^m 배 감소	16 >> 2	4

---

✅ 4. 비트 시프트 연산 활용 예제

(1) 빠른 곱셈과 나눗셈

int a = 5;
int b = a << 3;  // a * 2^3 = 5 * 8 = 40
int c = a >> 2;  // a / 2^2 = 5 / 4 = 1

💡 왼쪽 시프트(<<)는 곱셈, 오른쪽 시프트(>>)는 나눗셈과 같은 역할!

---

(2) 특정 비트 체크

비트 연산을 이용하여 어떤 숫자가 포함되었는지 검사할 수 있습니다.

int mask = (1 << 3);  // 3번째 비트만 켜짐 (0000 1000)
int num = 10;         // 10 = 1010

if (num & mask) { 
    cout << "3번째 비트가 켜져 있습니다." << endl;
} else {
    cout << "3번째 비트가 꺼져 있습니다." << endl;
}

💡 비트 AND (&) 연산을 이용하면 특정 비트가 켜져 있는지 쉽게 확인 가능!

---

(3) 비트마스크 (TSP, 방문 상태 관리)

비트 시프트 연산은 비트마스크 (Bitmask) 알고리즘에서도 많이 사용됩니다.

예를 들어, 4개의 도시 방문 상태를 저장할 때:

• 0000 → 아무 도시도 방문하지 않음
• 0001 → 0번 도시 방문
• 0011 → 0번, 1번 도시 방문
• 1111 → 모든 도시 방문

비트마스크를 사용할 경우, 특정 도시를 방문할 때:

int visited = 0;  // 0000 (모든 도시 방문 X)
visited |= (1 << 2); // 2번 도시 방문 (0010)
visited |= (1 << 3); // 3번 도시 방문 (1010)

💡 비트 연산을 사용하면 방문 상태를 효율적으로 저장하고 관리할 수 있음!

---

🎯 5. 결론

✅ 1 << n → 2^n을 계산하는 빠른 방법
✅ n >> m → n / 2^m을 계산하는 빠른 방법
✅ 비트마스크와 함께 사용하여 효율적인 상태 관리 가능
✅ TSP(외판원 문제), 그래프 문제, 비트마스크 DP에서 많이 활용됨!

---

 

📌 1 << MAX_N의 의미와 차이점

#define MAX_N 16
int n, dp[MAX_N][1 << MAX_N], dist[MAX_N][MAX_N];

 

---

✅ 1. 1 << MAX_N의 의미 (비트 시프트 연산)

📌 1 << MAX_N 계산

• 1 << 16은 비트 시프트 연산
• 2의 거듭제곱을 계산하는 연산으로, 다음과 같이 해석

1<<16=216=655361 << 16 = 2^{16} = 65536

즉, 1 << MAX_N은 2의 MAX_N 승을 의미

---

✅ 2. dp[MAX_N][1 << MAX_N]의 의미

int dp[MAX_N][1 << MAX_N];

이 배열은 TSP(외판원 문제, Traveling Salesman Problem) 또는 비트마스크 DP에서 자주 사용

표현 의미

dp[i][j]

i번째 도시까지 방문했을 때, 방문 상태가 j일 때의 최소 비용

📌 dp[MAX_N][MAX_N]과 dp[MAX_N][1 << MAX_N]의 차이점은 배열의 크기와 의미가 다르다는 점

표현 의미

dp[MAX_N][MAX_N]	최대 16 x 16 크기의 2차원 배열
dp[MAX_N][1 << MAX_N]	16 x 65536 크기의 비트마스크 DP 테이블

---

✅ 3. dp[MAX_N][1 << MAX_N]을 사용하는 이유

• 1 << MAX_N은 비트마스크를 사용하여 방문한 도시의 집합을 저장하기 위해 사용
• 각 비트는 특정 도시의 방문 여부를 나타냄
  • 예를 들어, 1 << 3 = 1000 (2진수)는 세 번째 도시(인덱스 3)를 방문한 상태를 의미
  • 1011(2진수) = 11(10진수)은 0, 1, 3번 도시를 방문한 상태를 의미

📌 예제 (MAX_N = 4일 때)

비트마스크 방문한 도시

0000 (0)	아무 도시도 방문 X
0001 (1)	0번 도시 방문
0010 (2)	1번 도시 방문
0011 (3)	0번, 1번 도시 방문
0101 (5)	0번, 2번 도시 방문
1111 (15)	0~3번 도시 방문 (완전 탐색 완료)

💡 따라서, dp[i][bitmask]는 i번째 도시에서 현재 방문 상태(bitmask)일 때 최소 비용을 저장하는 DP 테이블

---

✅ 4. dist[MAX_N][MAX_N]의 의미

int dist[MAX_N][MAX_N];

• dist[i][j]는 i번 도시에서 j번 도시로 가는 거리(비용)을 저장하는 2차원 배열
• 일반적인 그래프 탐색 문제에서 인접 행렬처럼 사용

---

✅ 5. 결론

📌 dp[MAX_N][1 << MAX_N] vs dp[MAX_N][MAX_N] 비교

표현 의미 크기 용도

dp[MAX_N][MAX_N]	i번 도시에서 j번 도시로 가는 경우 저장	16 x 16	단순 DP
dp[MAX_N][1 << MAX_N]	i번 도시까지 방문했을 때, 방문 상태(bitmask)를 저장	16 x 65536	비트마스크 DP (TSP 문제)

🚀 dp[MAX_N][1 << MAX_N]을 사용하는 이유

1. 모든 방문 조합을 비트마스크로 표현 가능 (O(2^N * N) 복잡도)
2. 중복 탐색을 줄여서 최적의 경로 탐색 가능 (TSP, 경로 최적화 문제 해결)

📌 즉, 이 구조는 TSP(외판원 문제)에서 "방문한 상태를 효율적으로 저장하고 관리"하는데 사용

---

🎯 6. 요약

✔ 1 << MAX_N는 2의 거듭제곱 (2^16 = 65536)
✔ dp[MAX_N][1 << MAX_N]은 비트마스크를 사용하여 방문 상태를 저장하는 DP 테이블
✔ dp[MAX_N][MAX_N]은 단순한 2차원 DP 테이블
✔ dist[MAX_N][MAX_N]은 도시 간 이동 거리 저장용 배열
✔ dp[MAX_N][1 << MAX_N]을 사용하면 모든 방문 상태를 효율적으로 탐색 가능 (TSP 해결에 사용)