문제 https://www.acmicpc.net/problem/15573 15573번: 채굴 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., www.acmicpc.net 채굴기의 성능 D보다 강도가 약하고, 공기와 맞닿은 광물만 채굴할 수 있을 때 K 이상을 채굴할 수 있는 최소 강도 D를 구하는 문제였다. 문제 풀이 D가 최대 1000000이고, map의 크기가 최대 1000000인 문제였기 때문에 완전 탐색이 불가능했다. 이전에 이와 비슷한 문제를 푼 적이 있어서 바로 이분탐색으로 D를 구하는 방법을 생각했다. 각 D마다 bfs를 진..
문제 https://www.acmicpc.net/problem/12892 12892번: 생일 선물 첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0 www.acmicpc.net 가격의 차이가 D 미만이 되는 최대 만족도를 구하는 문제였다. 문제 풀이 투포인터를 사용하는 문제였는데 정렬을 한 후에 투포인터를 이용해 구간을 옮기며 해당 구간의 만족도를 구하고 최댓값을 갱신해 해결했다. /* 가격의 차이가 최대 D가 되는 최대 만족도 구하기 정렬 후 투포인터 */ int main() { int N, D; v..
이진 탐색 문제는 left, right를 정하고 mid값을 비교해가며 풀면 된다. 이진 탐색 문제를 풀 때 배열은 항상 정렬되어 있어야 한다. 부품 찾기 배열 N 에서 배열 M의 값들을 찾는 문제였다. 배열 N의 값들을 오름차순으로 정렬한 후 M의 값들을 차례대로 이진탐색한 결과를 출력했다. 또, 찾아야 하는 값을 findNum으로 두고 초기 left와 right 값은 각각 0과 N 배열의 최댓값의 index인 N-1로 정했다. 이진탐색을 할 때 총 4가지 경우가 있다. narr[mid] 값이 findNum 보다 클 경우 → 왼쪽 범위를 탐색해야 함 (right 값을 mid-1로 바꿔줌) narr[mid] 값이 findNum 보다 작을 경우 → 오른쪽 범위를 탐색해야 함 (left 값을 mid+1 로 바..
이분 탐색 배열이 정렬되어 있어야 사용 가능 반으로 쪼개면서 탐색함 시간 복잡도 O(logN) (순차 탐색은 O(N)) 시작점, 중간점, 끝점을 가리키는 변수를 가짐 재귀, 반복문으로 구현 가능 1. 시작점, 중간점, 끝점 (left, mid, right) 정하기 2. 중간점과 찾는 값 비교 후 작으면 right를 mid-1로, 크면 left를 mid+1로 한 후 mid 값 다시 정하기 3. 2번을 반복 Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 이분 탐색으로 결정 문제를 해결하면서 범위를 줄여 최솟값, 최댓값을 찾음 결정 문제인지 아닌지의 차이 (이분탐색과) 1. left, mid, right를 정한 후 mid가 조건을 만족하는지 확인 2. 만족하지 않으면 mid 이전의 ..
