[삼성 알고리즘] 비트 알고리즘

안녕하세요 Blue-Moon 입니다.

이번에 포스팅할 내용은 비트 연산 알고리즘 입니다.

 

1. 비트 알고리즘

알고리즘의 반복문 등을 비트로 변환하여 계산하면 20배~30배 이상의 큰 알고리즘 효율을 얻을 수 있다.

이러한 비트 병렬 알고리즘으로 변환이 유용한 알고리즘은 해밍거리, 부분 격자 세기, 그래프의 도달 가능성(DAG)이 존재 한다.

 

1) 비트 알고리즘 표현

비트 알고리즘으로 데이터를 표현하는 방법은 크게 0b를 이용한 방법과 bitset STL을 이용하는 방법이 존재한다.

두 방법을 통해서 bit단위로 데이터 관리가 가능하고 여기에 비트 연산자를 통해 비트 단위의 조작이 가능하다.

 

2) 소스 코드

#include<iostream>

#include<bitset>

using namespace std;

 

int main(void)

{

unsigned char bit1 = 0b00000001;

unsigned char bit2 = 0b00000000;

bitset<2> bitset1;

bitset<2> bitset2;

bitset1.set(0);

 

cout << (bit1 | bit2) << endl;

cout << (bitset1 | bitset2) << endl;

return 0;

}

 

2. 해밍 거리

해밍 거리 알고리즘은 오류 값을 찾아내기 위한 방법으로 100011과 100010이 있을 때 다른 bit는 몇 개 인지 찾아내는 알고리즘이다. 위와같이 마지막 bit만 다른경우 1개의 bit가다르므로 해밍거리는 1이된다.

 

위 문제를 풀이하는 방법은 매우 간단하다

 

1. ^를 이용해서 XOR 연산을 진행 함.
2. ^연산을 진행한 후 결과 값을 STL인 __builtin_popcount(); 함수로 1의 개수를 파악
3. 1의 개수가 바로 다른 bit의 개수이므로 해밍 거리가 된다.

 

 

3. 부분 격자 세기

해당 알고리즘은 아래와 같이 격자가 있을 때 격자 4개의 색칠된 꼭짓점을 가지는 사각형의 개수를 구하는 문제이다.

위 그림은 격자에서 4개의 색칠된 사각형을 꼭짓점으로 구한 예시 중 하나이다.

위와 같이 부분 격자 세기 알고리즘을 해결하기 위해서는 (a,b)의 행 쌍을 바탕으로 반복문을 2개 중첩하고

추가로 열에 해당하는 반복문을 통해 삼중문으로 문제를 해결할 수 있다.

 

예를 들어 행의 2개 중첩 반복문은

for(int i=0;i<N;i++) 안에 for(int j=i+1; j<N; j++)와 같이 될 것이고 여기에 열에 대한 반복문 for(int k=0; k<N; k++)과 같이 되어

실제적으로 (I,k) 가 1이고(색칠) (j,k)가 1인

(I,k)==1 && (j,k)==1인 개수(count)를 구한 뒤 꼭짓점의 두 행이 I,j일 때 만들 수 있는 사각형의 개수를 count*(count-1)/2 공식을 통해서 구할 수 있다.

 

이러한 부분 격자 세기 문제는 색칠된 곳을 1, 아닌 곳을 0 으로 bit로 계산하여 각각의 행을 하나의 integer data등으로 표현할 수 있고 각각의 행을 &연산을 통해 count 값을 구할 수 있다. 이렇게 구해진 count값을 그대로 count*(count-1)/2 공식을 통해서 부분 격자 세기 알고리즘의 풀이가 가능하다.

 

 

4. 그래프의 도달 가능성(DAG)

그래프의 도달 가능성은 DAG 그래프에 대해 각각 임의의 노드 값을 input값으로 입력 받으면 해당 노드에서 이동할 수 있는 노드의 개수를 output으로 나타내는 알고리즘 이다. 여기서 자기자신은 갈 수 있는 노드로하여 모든 노드가 최소 1의 output을 가질 수 있다.

 

해당 문제를 풀이하는 방법은 매우 간단합니다.

위와 같은 DAG 그래프가 있을 때

1. 가장 먼저 각각의 노드에서 이동할 수 있는 노드는 bit값 1 아닌 곳은 0으로 표기합니다.(자기자신은 1)
2. 자신이 이동할 수 있는 노드의 bit값과 OR연산을 진행합니다.(내가이동할수 있는 노드가 이동할 수 있는 곳은 해당 노드를 통해 내가 이동할 수 있는 곳이기 때문이다)
3. 각각의 OR연산을 통해 결과 그래프의 도달 가능성 알고리즘 풀이를 할 수 있다.(이 떄 재귀에 빠지지 않도록 주의)