문제 설명
주어진 정수 배열이 있습니다. 이 배열에서 특정 범위 내의 최솟값을 찾아야 합니다.
뿐만 아니라, 이 범위는 동적으로 주어지며 여러 쿼리에 대해 요구될 수 있습니다.
즉, 배열의 특정 인덱스 i와 j가 주어졌을 때,
i에서 j 사이의 최솟값을 찾아야 합니다.
이러한 문제를 해결하기 위한 효율적인 알고리즘을 설계하고 구현하는 것이 이번 강좌의 목표입니다.
문제 형식
입력: 정수 배열 nums와 쿼리 리스트 queries가 주어집니다.
– nums: n개의 정수로 이루어진 배열 (0 ≤ n ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9)
– queries: 여러 (i, j) 쌍이 포함된 리스트 (0 ≤ queries.length ≤ 10^5, 0 ≤ i ≤ j < n)
출력: 각 쿼리에 대한 최솟값을 리스트로 반환합니다.
문제 예시
예시 1
입력:
nums = [2, 0, 3, 5, 1]
queries = [[0, 2], [1, 4], [0, 4]]
출력:
[0, 1, 0]
예시 2
입력:
nums = [1, 2, 3, 4, 5]
queries = [[0, 0], [0, 4], [2, 3]]
출력:
[1, 1, 3]
해결 전략
이 문제를 해결하기 위해서는 여러 가지 접근 방식이 있습니다.
가장 단순한 방법은 각 쿼리에 대해 선형 탐색을 사용하는 것입니다.
그러나 이 방법은 최악의 경우 O(m * n)의 시간 복잡도를 가지므로,
더 효율적인 방법이 필요합니다.
우리는 세그먼트 트리(Segment Tree) 또는 희소 테이블(Sparse Table)과 같은 자료구조를 활용하여
각 쿼리에 대해 O(log n) 또는 O(1)의 시간 복잡도로 최솟값을 찾도록 하겠습니다.
세그먼트 트리 사용하기
세그먼트 트리는 주어진 배열에서 특정 구간에 대한 쿼리를 효율적으로 처리하는 자료구조입니다.
이를 통해 우리는 O(n)으로 세그먼트 트리를 구축하고, 각 쿼리를 O(log n)으로 처리할 수 있습니다.
다음은 세그먼트 트리를 구축하고 쿼리를 처리하는 방법입니다.
세그먼트 트리 구현
// 세그먼트 트리 클래스
class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int[] nums) {
n = nums.length;
tree = new int[4 * n]; // 충분한 크기의 트리 배열
build(nums, 0, 0, n - 1);
}
private void build(int[] nums, int node, int start, int end) {
if (start == end) {
tree[node] = nums[start]; // 리프 노드에 값 저장
} else {
int mid = (start + end) / 2;
build(nums, 2 * node + 1, start, mid);
build(nums, 2 * node + 2, mid + 1, end);
tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]);
}
}
public int query(int L, int R) {
return query(0, 0, n - 1, L, R);
}
private int query(int node, int start, int end, int L, int R) {
if (R < start || end < L) {
return Integer.MAX_VALUE; // 해당 구간에 포함되지 않으면 무한대 반환
}
if (L <= start && end <= R) {
return tree[node]; // 구간 포함 시 노드 값 반환
}
int mid = (start + end) / 2;
int leftMin = query(2 * node + 1, start, mid, L, R);
int rightMin = query(2 * node + 2, mid + 1, end, L, R);
return Math.min(leftMin, rightMin); // 두 자식의 최소값 반환
}
}
최종 구현 및 실험
이제 각 쿼리들을 처리하고 결과를 반환하는 메인 함수를 구현하겠습니다.
사용자가 쿼리를 요청할 수 있도록 하여, 이를 통해 효율적으로 최솟값을 가져올 수 있습니다.
최종 구현은 다음과 같습니다.
public class MinValueFinder {
public int[] minInRange(int[] nums, int[][] queries) {
SegmentTree segmentTree = new SegmentTree(nums);
int[] results = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
results[i] = segmentTree.query(queries[i][0], queries[i][1]);
}
return results;
}
}
시간 복잡도 분석
– 세그먼트 트리 구축: O(n)
– 각 쿼리 처리: O(log n)
전체 시간 복잡도는 O(n + m * log n)입니다.
이는 매우 효율적이며, 제한된 입력 조건에서도 충분히 수행할 수 있습니다.
결론
이번 강좌에서는 주어진 배열에서 특정 범위 내의 최솟값을 찾는 문제를 세그먼트 트리를 활용하여 해결했습니다.
세그먼트 트리는 여러 쿼리를 효율적으로 처리할 수 있어, 대규모 데이터에서 자주 사용되는 자료구조입니다.
이를 통해 문제 해결 능력을 향상시키기를 바랍니다.