잡다한것 etc.

PS에 bitset이용하기

杉山空 2024. 2. 26. 20:24
728x90

INTRODUCTION

  PS(problem solving, 본문에서 문제 해결 프로그래밍을 뜻함)에서 bitset을 이용한 최적화는 널리 알려져 있지만, 그렇게 자주 이용되는 것은 아닙니다. 하지만, 몇 가지 경우에서 메모리나 실행 시간을 획기적으로 줄일 수 있는 방법이 되기도 합니다.

 

Reduce Memory

  메모리를 줄이는 방법은 생각보다 단순합니다. Boolean array를 이용해야 한다면, 대신 bitset을 이용하는 방법으로 메모리를 1/4정도로 줄이는 것이 가능합니다. 이 방법으로 BOJ 2814번을 sieve만으로 해결하는것이 가능합니다. 또, segment tree leaf node가 0 또는 1만 가진다면, segment tree가 큰 크기를 가지면서 상대적으로 적은 메모리를 가지게 하는 것이 가능합니다.

 

연습문제

BOJ 13701번: 중복제거 / boolean array를 bit set으로 표현하는 문제

BOJ 30399번: 홀짝홀짝 / 좌표압축을 이용하는 풀이가 더 쉽지만, bitset을 이용하여 도전해 보십시오.

 

Reduce Runtime

  Bit set을 이용한다고 해서 점근적 시간복잡도가 줄어드는 것은 아닙니다. 하지만 점근적 표현에 숨겨진 상수를 크게 줄일 수는 있습니다. Boolean array를 이용하는 대신, bitset을 이용하면, 어떤 부분이 같고 다른지 구분하는 것은 간단한 bit operation수행할 수 있습니다. 또, boolean array에서 true의 수를 알고 싶을 때도 비교적 빠르게 할 수 있습니다. 앞서 설명한 segment tree의 leaf node를 bitset으로 표현하는 것에서도 이러한 최적화가 가능합니다.

 

연습문제

BOJ 20501번: Facebook

 

Dynamic Programming Optimization

  아래와 같은 dynamic programming이 있다고 합시다.

Di+1=Di+f(i+1),f(x)[0, 1]

 

이제 Bi+1=Di+1Di라 하면, B는 bitset으로 표현할 수 있습니다. 그러면 모든 i에 대한 Di의 값을 따로 저장해두지 않아도 됩니다. 만약, B를 bit operation으로 계산할 수 있다면 시간 복잡도를 줄이는데에도 크게 도움이 됩니다.

 

연습문제

BOJ 18439: LCS 6 / 이 문제의 풀이에 관한 아이디어는 다른 자료를 참고해주십시오.

 

번외

- 착각하기 쉬운 것

보통 시간복잡도를 계산할 때 우리는 '산술 연산'의 횟수가 주어지는 변수에 따라 얼마나 증가하는가에 집중합니다. 그래서 bitstring의 bit를 세는 연산이 O(1)이라 생각할 수 있습니다. 하지만, bitstring의 크기에 따라 필요한 bit operation의 수는 당연히 달라집니다. 확실히 bit operation이 산술 연산보다 훨씬 빠르기는 하지만, 모든걸 바로 처리해주는 마법의 도구라는 것을 알아야하며, bit complexity라는 것을 공부하는것도 좋습니다. (long long 보다 int를 대상으로 하는 연산이 훨씬 빠른것도 이런 이유이며, '연산'의 수는 더 많은데 비해 '비트 연산'의 수는 더 적어 실제로 더 빠르게 작동하는 경우도 있습니다. ex] Stein GCD )

 

- bit 연산

Bitset을 이용할 때 따로 template를 이용하지 않는 이상은 배열로 64개 정도의 bit를 따로 저장해야 합니다. 따라서 뺄셈이나 덧셈을 할 때는 받아올림이나 받아내림을 잘 생각해 봐야 합니다. 만약 덧셈, 뺄셈 뿐만 아니라 여러 연산이 섞여 있다면 신경쓸게 조금 더 많아집니다.

(LCS 6을 해결할 때 필요합니다.)

728x90

'잡다한것 etc.' 카테고리의 다른 글

[MacOS] iD4 MKII 오디오 인터페이스 Loopback 설정  (3) 2024.02.13