경우없는 개발 블로그

#비트연산

우선 비트연산에 대해서 알아보자

1. NOT 연산 (~)

• ~ (부정): NOT 연산은 단항 연산으로, 각 비트를 반전시킵니다. 즉, 1을 0으로, 0을 1로 바꿉니다.
• 예시:
  • 입력: A = 1010 (2진수)
  • 결과: ~A = 0101

2. AND 연산 (&)

• & (AND): AND 연산은 두 비트가 모두 1일 때만 1을 반환하고, 나머지 경우에는 0을 반환합니다.
• 진리표:

A                                           B                                                        A  & B

• 예시:
  • 입력: A = 1100, B = 1010
  • 결과: A & B = 1000

3. OR 연산 (|)

• | (OR): OR 연산은 두 비트 중 하나라도 1이면 1을 반환하고, 둘 다 0일 때만 0을 반환합니다.
• 진리표:

ABA | B

• 예시:
  • 입력: A = 1100, B = 1010
  • 결과: A | B = 1110

4. XOR 연산 (^)

• ^ (XOR): XOR 연산은 두 비트가 서로 다를 때만 1을 반환하고, 같을 때는 0을 반환합니다.
• 진리표:

A                                                     B                                                                       A  ^ B

• 예시:
  • 입력: A = 1100, B = 1010
  • 결과: A ^ B = 0110

#Left Shift 

비트를 좌측으로 옮길 경우에는

2제곱을 곱해주는 효과가 있다.

예를 들어서 

1 << 2 

인 경우에는 연산 결과로 

1 * 2^2

로 4가 되는걸 확인 할 수 있다.

좀 더 확인해보자면

3 << 3

결과값으론

2*3^3 = 24 가 된다는걸 알 수 있다.

#Right Shift

비트를 우측으로 옮길 경우에는 

반대로 2 제곱을 나눠주는 효과가 있다

10>>2 인경우

결과값으로 10/2^2 한 값인 2가 나오는걸 알 수있다. 

#Shift 활용

shift 연산을 활용하면 

중간값을 구하는 과정을 매우 빠르게 할 수 있다. ( >> 1) 을 활용해서

그리고 홀수 인지 판별하는 경우도 1과의 and 연산을 빠르게 해줄 수 있다.

왜냐면 홀수인 경우에는 가장 작은 비트가 1이기 때문에 & 1 연산을 해주면 

1이 나오고 짝수인 경우에는 &1 연산이후에 0이기 때문에

• 짝수: 마지막 비트(Least Significant Bit, LSB) 0이다.
  • 예: 2 (10₂), 4 (100₂), 6 (110₂)
• 홀수: 마지막 비트(LSB)가 1이다.
  • 예: 1 (1₂), 3 (11₂), 5 (101₂)

빠르게 구할 수 있다.

#비트마스크 Bit Mask

비트 마스크에 대해서 알아보자

비트 마스크는 

 특정 상태나 값이 들어있는지 확인하는데 유용하다

특히 방문배열 을 활용한 dfs 나 bfs 구현에서 유용하게 사용 할 수 있다.

예를 들어서

의 배열을 가지고 있다면 

1번 3번 4번 5번 9번을 방문했기때문에

이진수로 바꿔서 더해주게 되면

가 되고 

이 배열들의 인덱스에 값들이 들어가 있는걸 확인 할 수 있다

&연산을 통해서 

그 위치의 이진수가 존재하는지 확인해 주면 된다

특정 자리에 값이 있는지 확인하고 싶은 경우 (특정 순서의 비트에 값이 있는지 확인)

원하는 위치만큼 1을 << 연산 해주고

&연산을 해주게 되면 1을 반환하면 그 자리에 존재하고 

0을 반환하면 그 값이 없다는걸 알 수 잇다.

2가 들어있는지 알고싶기 때문에 1을 <<1 연산을 하고  & 연산을 하면

가 나오기 때문에 2가 비트마스크에 들어있다는 것을 알 수 있다.

즉 값의 인덱스에 존재하는지 알고싶다면 2진수로 변환한 뒤에

&연산을해서 그값이 똑같이 나온다면 존재한다는 것이다.

#비트마스크 Bit Mask 추가

비트 마스크는 

 | or 연산을 해서 추가해 줄 수 있다.

특정 인덱스 추가해주는경우

원하는 위치만큼 1 을 << 연산을 해준 뒤에

1과  연산을 해주면 값이 1이 나오기 때문에 비트마스크 추가를 할 수 있다

이 연산을 하게 되면

1을 넣을 수 있다.

값이 존재함을 비트마스크에 넣고싶다면

2진수로 바꾼뒤에 or 연산을 하면 된다

#비트마스크 Bit Mask 삭제

비트마스크 삭제인 경우에는

~연산을 해준 뒤에 & 연산을 함으로써 삭제를해준다

~를 해주면 값은 0이되고 그 외의 비트들은 1이 되므로

~를 해주고 & 연산을 해주면 인덱스를 삭제 할 수 있다

2번째 인덱스를 삭제 하고 싶은 경우에 

1을 <<연산을 2번 해주고 & 연산을 해준다

2번째 비트 의 값만 삭제할 수 있는 것을 알 수 있다.

#Exclusive OR 활용

Exclusive OR 는 

값을 swap 하는데 사용 할 수 있는데

XOR 스왑 알고리즘은 두 변수를 임시 변수 없이 스왑하는 방법으로, XOR 연산을 사용합니다. 이는 메모리를 절약하고 코드의 간결성을 유지하는 데 유용합니다. 

설명

XOR 연산

XOR (exclusive OR) 연산은 두 비트가 서로 다를 때 1을 반환하고, 같을 때 0을 반환합니다. 이를 통해 다음과 같은 성질을 이용할 수 있습니다:

• a ^ a = 0
• a ^ 0 = a
• a ^ b ^ b = a (교환 법칙과 결합 법칙에 따라)

XOR 스왑 알고리즘

1. Step 1: x = x ^ y
   • 이 단계에서 x는 x와 y의 XOR 값이 됩니다.
   • 예: x = 5 (0101), y = 9 (1001) => x = 0101 ^ 1001 = 1100 (12)
2. Step 2: y = x ^ y
   • 이 단계에서 y는 x의 새로운 값(즉, x XOR y)과 y의 XOR 값이 되므로, 원래의 x 값을 얻습니다.
   • 예: y = 1100 ^ 1001 = 0101 (5)
3. Step 3: x = x ^ y
   • 이 단계에서 x는 x의 새로운 값(즉, x XOR y)과 새로운 y의 XOR 값이 되므로, 원래의 y 값을 얻습니다.
   • 예: x = 1100 ^ 0101 = 1001 (9)

매크로로 

선언하여 쉽고 빠르게 사용 할 수 있다.

그래프:

(Graph)

자료구조의 일종으로 그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조이다.

정점(Node,Vertex) 간선(EDGE):정점간의 관계 로 표현된다

G =(V,E)로 나타낸다

경로: 1에서2에서 가는경로, 1에서 3에서 가는 경로 등이 있다.

사이클 : 정점 1에서 다시 1로 돌아오는 경로

단순경로/단순사이클 : 경로/사이클에서 같은 정점을 두번 이상 방문하지 않는 경로/사이클

    보통 말이 없으면 일반적으로 사용하는 경로와 사이클은 단순경로/사이클을 뜻한다

방향있는 그래프/ 방향없는 그래프

양방향 그래프 라고도 한다

루프: 간선의 양 끝점이 같은경우

가중치: 있다면 A에서 B로 이동하는  거리 시간 비용 등등..

차수 : 정점과 연결되어 있는 간선의 개수

그래프의 표현 방법

정점: {1,2,3,4,5}

간선: {(1,2),(1,3),(2,5),(2,3),(3,4),(4,5)}

그래프의 표현 방법에는 인접행렬과 인접 리스트를 활용한 방법 두가지가 있다.

인접 행렬을 사용한 경우

인접 리스트를 사용한 경우 

(리스트는 동적으로 변경할 수 있어야 하고,연결 리스트나 동적으로 변경이 가능한 배열을 사용한다)

A[1] : 2 3

A[2]: 1 3 4

A[3]: 1 2 4

A[4]: 3 5

A[5]: 2 4

EX) 가중치가 있는 경우 A[2]: (2,3) (3,5) 등으로 가중치도 함께 저장

인접리스트 VS 인접 행렬

.인접 행렬은 정점 1000개의 그래프를 표현하기 위해서는 1000x1000의 행렬이 필요하고

인접 리스트는 1000개의 노드가 있으면 된다 

만약에 이 그래프에 5개의 간선이 있다고 한다면

인접행렬은 1000x1000개 인접리스트는 1000(정점노드)+5(간선노드)개 의 노드가 필요하다 

인접행렬의 공간복잡도는O(V^2)

인접리스트는 O(V+E) V는 정점 E는 간선의 개수

때문에 인접리스트는 희소 그래프를 표현하는데 적당하다

반면 1000개의 정점이있고 간선이 1000개인 경우 인접행렬로 구현하는게 더 효과적이면

이는 행렬의 접근성 때문이다 인접행렬은 인덱스를 사용하므로 O(1)으로 연결되었는지 확인 가능하지만

인접리스트는 헤드부터 노드를 찾을 때 까지 탐색을 진행해야 되므로 시간이 많이 걸린다

전자의 경우 희소 그래프 후자의 경우 밀집 그래프 이다

관련문제:

https://www.acmicpc.net/problem/13023