알고리즘 기법이라고 볼 수는 없지만 비트마스크 기법을 이용하여 풀 수 있는 문제가 꽤 보여서 알아보기로 하였다. 개념 컴퓨터의 최소 연산 단위 bit 이진수를 나타내기 위해 0과 1로만 이루어져 있는데, 비트 연산을 통하여 빠르게 해결 할 수 있다. 예를 들면 -> bfs나 dfs를 하며 visited를 체크 해줄 때, 크기가 10인 배열을 만드는 경우가 있는데 0b0000000000 와 같이 비트마스킹으로 똑같은 표현을 할 수 있다. 즉 더 작은 메모리를 사용하여 표현 가능하다. 장점 비트 연산은 삽입, 삭제, 조회가 빠르다. 코드가 간결해지며 정수 표현으로 dp문제 해결 가능 비트 연산 2022.08.10 - [ALGORITHM/알고리즘 알아보기] - 알고리즘 - 부분 집합 알고리즘 - 부분 집합 완..

목차 팬윅 트리? 구현 업데이트 1. Fenwick Tree ? Segment Tree 처럼 구간에 대한 연산을 저장하는 트리 Segment Tree 보다 적은 메모리로 사용 가능하다!! 절반 정도의 메모리만으로 사용 가능 시간 복잡도 O(logN) 비트를 이용한 구간 연산을 진행한다. Q. 3~5번째 인덱스 구간 합을 구하기 A. 두 구간의 차를 구하면 된다. 5번 인덱스까지의 값을 구하려면 2진수 101 인덱스 값과 100 인덱스 값을 더하면 된다. 101 인덱스에서 마지막 1의 값을 제거해주면 100이 된다. Q. 마지막 2진수 1의 값을 제거하는 방법은? Answer. N = N - (N & -N) 5 - ( 5 & -5 ) = 4 4 - ( 4 & -4 ) = 0 2. 구현 Val = 1 ind..