[문제해결기법] 7. 이분 탐색
1. 탐색 오름차순으로 정렬된 N개의 정수 배열 A[0], ..., A[N-1]이 있다. X가 주어졌을 때, A[i] = X라면 i를 리턴하는 함수 find(N, X)를 작성하시오. 이 함수는 내부적으로 compare(i, val)을 호출하는데, 이는 A[i]=val이면 0, A[i] val이면 -1을 리턴하는 함수이다. N은 최대 100이다. int find(int sub, int N, int X) { int start = 0, end = N-1, t; while (start 0) start = mid + 1; // 기준값보다 작으면 start를 당기기 else if (v) end = mid - 1; // 기준값보다 크면 end를 당기기 else return mid; }..
[문제해결기법] 6. 세그먼트 트리
1. Segment Tree 부분합 문제에서 응용 가능 생성 코드 2. 합을 구하는 코드 [start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다. (1) [start, end]와 [left, right]가 겹치지 않음 -> 할 일이 없다 (2) [start, end]가 [left, right]를 포함 -> 미리 구해둔 [left, right]의 합을 사용한다. (3) [start, end]를 [left, right]가 포함 -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다. (4) [start, end]가 [left, right..
[문제해결기법] 3. 자료구조1
1. RMQ : Range Minimum Query (범위 최소 쿼리) 배열의 부분배열에서 최솟값을 찾기 (1) O(n^3) 전처리, O(1) 질의 : brute force 방식으로 가능한 RMQ(a,b)에 대한 답을 모두 저장해놓는다. n^2칸을 채워야하고, 한 칸을 채울 때 최대 O(n)시간이 걸린다. (2) O(n^2) 전처리, O(1) 질의 : 가능한 RMQ(a,b)에 대한 답을 모두 저장하는데, RMQ(a,b+1) = min(RMQ(a,b) , A[b+1])을 사용하여 n^2칸을 각각 O(1)의 시간으로 채울 수 있다. (3) O(n) 전처리, O(sqrt(n)) 질의 : 배열을 sqrt(n) 묶음으로 나눈 후 각 묶음의 최솟값을 구하는데에 O(n)이 걸리며, RMQ(a,b)를 구하..
