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이 있다고 합시다.
이제
연습문제
BOJ 18439: LCS 6 / 이 문제의 풀이에 관한 아이디어는 다른 자료를 참고해주십시오.
번외
- 착각하기 쉬운 것
보통 시간복잡도를 계산할 때 우리는 '산술 연산'의 횟수가 주어지는 변수에 따라 얼마나 증가하는가에 집중합니다. 그래서 bitstring의 bit를 세는 연산이
- bit 연산
Bitset을 이용할 때 따로 template를 이용하지 않는 이상은 배열로 64개 정도의 bit를 따로 저장해야 합니다. 따라서 뺄셈이나 덧셈을 할 때는 받아올림이나 받아내림을 잘 생각해 봐야 합니다. 만약 덧셈, 뺄셈 뿐만 아니라 여러 연산이 섞여 있다면 신경쓸게 조금 더 많아집니다.
(LCS 6을 해결할 때 필요합니다.)
'잡다한것 etc.' 카테고리의 다른 글
[MacOS] iD4 MKII 오디오 인터페이스 Loopback 설정 (3) | 2024.02.13 |
---|