개발일지

개념 파란점에서 빨간점까지 탐색한다고 생각할 때 파란점 기준으로 탐색하면 초록색 영역만큼 탐색해야한다. 하지만 파란점과 빨간점을 기준으로 만나는 노란색 점을 탐색하면 탐색해야 하는 불필요한 영역이 줄어든다. 이처럼 기준을 바꿔서 다르게 생각하면 좀 더 연산을 줄일 수 있다. 문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 코드 #include using namespace std; int n, c; vector input; vector..

개념 탐색 범위를 반으로 줄이면서 값을 찾는 방법이다. 작동원리 1. 탐색 범위를 정렬한다. 2. l -> 탐색 범위 최소값, r -> 탐색 범위 최대값, m -> 탐색 범위 중간값 3. m에 찾으려는 위치가 있는지 확인한다. 4. m에 찾는 값보다 큰 값이 존재하면 r을 m - 1로 바꾼다. ( 정렬되어있기 때문에 m보다 큰 인덱스에 저장된 값은 m에 저장된 값보다 크기 때문에 확인할 필요가 없다.) 5. m에 찾는 값보다 작은 값이 존재하면 l을 m + 1로 바꾼다. (정렬되어있기 때문에 l보다 작은 인덱스에 저장된 값은 m에 저장된 값보다 작기 때문에 확인할 필요가 없다.) 6. l > n >> k; vector ve(n); for (auto &i : ve) { cin >> i; } long lon..