가능한 모든 경우의 수를 다 해보는 것
개념
이진수를 이용하여 하나의 정수로 여러 부분집합을 표현하는 테크닉
장점
개념
리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
언제?
특정한 합을 가지는 부분 연속 수열을 찾을 때
시간복잡도 : O(N)
코드
// <코드>
int l = 0, r = 0, sum = 0, ans = 0;
while (l <= r && r < n) {
if (sum < m) {
sum += a[r++];
}
else if (sum == m) {
sum += a[r++];
ans++;
}
else {
sum -= a[l++];
}
}
while (sum >= m) {
if (sum == m) {
ans++;
}
sum -= a[l++];
}
// <타당성 증명>
수열 A의 원소는 모두 양수이고 A[a] + ... +A[b] < M, A[a] + ... +A[b+1] > M이라고 할 때,
A[a+1] + ... + A[j] (a+1 <= j <= b) == M인 경우는 존재하지 않는다.
왜?
만일 존재한다고 하면 A[a] + ... + A[b] < M을 만족할 수 없기 때문이다.
따라서 j를 줄이는 것은 의미가 없고, i를 올려야 한다
개념
문제의 크기를 절반으로 나누어, 양쪽 절반에서 모든 경우를 다 해보는 방법
장점
탐색의 크기 역시 절반으로 줄어든다.
문제