넘치게 채우기

기본적인 브루트 포스 방법은 O(2^n)이 걸린다.그래서, n=20인 경우에만 시간 효율적으로 사용할 수 있다. 개선해서, n MITM, Meet-in-the-Middle알고리즘이다. n길이의 배열 arr이 주어지고, 합이 s인 부분배열의 개수를 구한다고 해보자. 핵심 아이디어는 다음과 같다:배열을 절반으로 나눠서, 각각 브루트 포스로 모든 조합을 구한다. 각각 left, right라 한다.이진탐색을 이용할 것이기에, right를 정렬해준다.  left의 조합들에서 각각 right에서  target = s-leftsum값에 대해 upper_bound(target보다 초과인 큰 요소의 첫 인덱스), lower_bound(target이상인 요소의 첫 인덱스)를 구해서 upper_bound - lower_bo..

https://www.acmicpc.net/problem/1182BOJ - 부분수열의 합문제 유형: 브루트포스, 백트래킹, 비트마스킹문제 난이도: Silver II시간 제한: 2초메모리 제한: 256MB 문제N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 풀이백트래킹 또는 비트마스킹으로 풀 수 있다.백트래킹으로 ..

https://leetcode.com/problems/maximum-number-of-integers-to-choose-from-a-range-i/description/leetcode - Maximum Number of Intergers to Choose From a Range I문제 유형: 그리디문제 난이도: Medium 문제You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:The chosen integers have to be in the range [1, n].Each integer can be chosen ..