반응형

Bitmask

컴퓨터는 이진번 관련 연산들을 매우 빠르게 진행할 수 있는데, 이러한 특성들을 사용하여 이진수 표현을 자료구조로 사용하는 기법을

비트마스크라고 합니다. 비트마스크는 자료구조라고는 할 수는 없지만 종종 굉장히 유용하게 사용됩니다. 비트마스크를 사용하면 

수행시간이 빨라짐, 간결한 코드, 더 적은 메모리 사용량등 과 같은 장점들이 있습니다.


AND(&)

AND 연산은 두 정수를 한 비트씩 비교하면서 해당 비트가 모두 켜져있을때(1)만 결과비트를 킵니다. 즉 11(2) 10(2)를 AND연산한다면 10(2)의 결과가 나오는 것이죠.

OR(|)

OR 연산은 두개의 비트중 하나만 켜져있어도 결과비트를 키는 연산입니다. 11(2) | 10(2) 의 결과는 11(2)입니다.

XOR(^)

XOR 연산은 두개의 비트가 서로 달라야 결과비트를 키는 연삽입니다. 11(2) ^ 10(2) 의 결과는 01(2)입니다.

시프트연산(<< , >>)

시프트 연산은 해당비트를 왼쪽으로, 오른쪽으로 밀어내는 연산입니다. 1<<2는 0001을 2비트 왼쪽으로 밀어내므로 0100이 됩니다.


* Example 1) 비트마스크를 이용한 집합
* n비트 정수 변수는 0 ~ n-1까지의 정수 원소를 가질 수 있는 집합입니다.
* 이때 원소 x가 집합에 속해있는지 여부를 알기 위해서는
* 2^x를 나타내는 비트가 켜져있는지 확인하면 됩니다.
* 예를 들어 {1,4,5,6,7,9}를 표현하는 정수는 정수 754임을 다음과 같이 알 수 있습니다.
* 2^1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^9 = 10 1111 0010(2) = 752(10)
*
* Example 2) 꽉찬 집합 / 공집합 구하기
* 공집합은 너무 간단합니다. 아무것도 없기 때문에 상수 0이 공집합을 나타냅니다.
* 꽉찬 집합도 간단한데 위의 예제에서 볼 수 있듯이 10비트의 꽉찬 집합은 (1<<10)-1을 해주면 됩니다.
* 1을 왼쪽으로 10비트 시프트하면 해당 비트만 1이고 모두 0인데 -1을 해주면 모든 비트가 켜지기 때문입니다.
*
* Example 3) 원소 추가하기
* 원소를 추가하는 방법은 OR연산을 사용합니다. 만약 현재 집합을 tmpset이라고 가정합시다.
* tmpset집합에 어떤 원소를 추가하고 싶다면 tmpset |= (1<<x) 와 같이 표현할 수 있습니다.
* 1을 x비트만큼 왼쪽 시프트하면 x번 비트만 켜진 정수가 되는데 이값과 tmpset을 OR연산한다면
* 해당 비트는 반드시 켜지기 때문이죠.
*
* Example 4) 원소 삭제하기
* 원소를 삭제하는 방법은 AND와 NOT연산을 사용합니다. tmpset &= ~(1<<x)와 같이 표현할 수 있는데
* ~(1<<x)는 해당 비트만꺼지고 모두 1인 값입니다.
* 이 값과 원래 집합을 AND 연산한다면 tmpset의 나머지 비트는 유지되고 x비트만 꺼지게 됩니다.
*
* Example 5) 원소의 포함여부 확인하기
* 만약 해당 집합내에 원소가 포함되어 있는지 알기 위해서는 다음과 같이 알 수 있습니다.
* if(tmpset & (1<<x)) 와 같이 표현하면 1을 x비트만큼 왼쪽 시프트한 결과와
* tmpset집합의 x번째 비트가 모두 켜져있어야 true를 반환하겠죠.
* tmpset이 1<<x한 비트를 포함하고 있다면 if조건을 통과할 것입니다.
*
* Example 6) 원소의 Toggle
* 해당 비트가 켜져있다면 끄고, 꺼져잇다면 키는 방법입니다. XOR연산이 사용되는데
* tmpset ^= (1<<x)와 같이 표현할 수 있습니다.
* tmpset의 x번째 비트가 켜져있다면 끄고 꺼져있다면 끌수 있겠죠.


반응형

'Algorithm 이론' 카테고리의 다른 글

[알고리즘 이론] 재귀함수  (0) 2019.01.11
반응형

문제풀이에 앞서서 재귀함수에 대해 간단히 알아보고자 한다.


재귀는 작은문제로 나눠서 동일한 알고리즘을 반복적으로 적용하여 작은문제를 해결한 뒤 큰 문제를 해결할 수 있을 때 사용한다.

재귀적 정의는 base case(재귀함수를 종료)inductive part(재귀함수를 호출)으로 구성된다.


재귀함수 작성 절차

더 작은 문제로 표현할 수 있는가?

문제를 직접 풀 수 있는 것이 어떤 경우인지 base case로 확인

그럼 위 작성절차에 따라 팩토리얼 함수를 재귀적으로 생각해보자.


1
2
3
4
5
6
7
팩토리얼 재귀함수
 
base case:
    n<=1 return 1
 
inductive part:
    return n*factorial(n-1);
cs



이를 소스로 나타내면 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
int factorial(int n) {
 
    if(n<=1)    //base case
 
        return 1;
 
    else         //inductive part
 
        return n*factorial(n-1);
 
}
cs


반복 / 재귀를 사용해야 할 때

사실 재귀함수는 반복문으로 구현할 수 있고 반복문으로 구현하는것이 조금이라도 더 효율적이기 때문에 반복문으로 구현하는 것이 성능상으로는 더 좋다. 하지만 문제에 따라 재귀적 구현이 더 간단하고 자연스러운 경우가 있으므로 문제에 따라 적절하게 사용하는 것을 추천한다.(분할정복등을 통해 시간복잡도를 줄일 수 있는 경우와 같은 특수 케이스는 제외)


 * 참고

재귀함수는 함수를 반복해서 호출하므로 함수 인자를 반복해서 생성하기 때문에 stack 메모리에 계속 할당하며 부가적인 오버헤드가 생긴다.



반응형

'Algorithm 이론' 카테고리의 다른 글

[Bitmask] 비트마스크 기초  (0) 2019.01.28

+ Recent posts