알고리즘

비트마스크 > 1. 비트마스크란? 이진수를 사용하는 컴퓨터 연산방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 이진수 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. 보통 어떤 비트가 1이면 "켜져 있다

배열의 부분합을 구할 때에 브루트포스(완전탐색)로 구하게 된다면 시간 복잡도가 O(n)이 걸린다. 하지만 누적합을 이용한다면 O(1)의 시간이 걸리게 된다.더 자세하게 설명하자면 구간의 길이가 M이고 N개의 구간의 갯수를 가지고 있다면 시간 복잡도는 O(NM)이 된다.