데이터 구조와 알고리즘의 이해는 개발자로서의 성장에 필수적인 요소입니다. C++는 고성능의 프로그래밍 언어로, 특히 코딩 테스트와 같은 알고리즘 문제를 해결하기 위해 널리 사용됩니다. 이번 강좌에서는 ‘구간 곱 구하기’라는 문제를 다루며, 이를 해결하기 위한 다양한 접근 방식을 설명하겠습니다.
문제 정의
주어진 배열과 몇 개의 질의(query)에 대해, 지정된 구간의 곱을 빠르게 계산하는 문제를 고려해보겠습니다.
문제:
주어진 정수 배열 A와 질의의 수 Q가 있다.
A[i]는 배열의 i번째 원소를 의미하며, 1 ≤ i ≤ N입니다. 각 질의는 두 수 L과 R을 포함하여, L ≤ R일 때 A[L] × A[L+1] × ... × A[R]의 값을 구하는 것이다.
입력:
- 배열의 크기
N(1 ≤ N ≤ 105) - 정수 배열
A[1...N](1 ≤ A[i] ≤ 109) - 질의의 수
Q(1 ≤ Q ≤ 105) - 각 질의는 두 정수
L와R(1 ≤ L ≤ R ≤ N)
출력:
각 질의에 대한 구간 곱을 한 줄씩 출력한다.
문제 접근 방식
이 문제를 해결하기 위해 몇 가지 접근 방식을 생각할 수 있습니다.
첫 번째로, 단순한 방법은 각 질의를 위해 주어진 구간의 곱을 순차적으로 계산하는 것입니다.
그러나 이 방법은 최악의 경우 O(N * Q)의 시간이 걸리므로 비효율적입니다.
두 번째 방법은 세그먼트 트리를 사용하는 것입니다.
세그먼트 트리는 적은 시간 안에 구간에 대한 합, 곱 또는 최대/최소 값을 계산하는 데 효과적입니다.
세 그 영역 트리의 각 노드는 그 지역의 곱을 저장하고, 이를 통해 구간 곱을 O(log N) 시간 안에 구할 수 있습니다.
세그먼트 트리의 구조
세그먼트 트리는 이진 트리의 형태로 구성되며, 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다.
세그먼트 트리는 대개 다음 가지 주요 작업을 수행할 수 있습니다:
- 구간 곱 조회:
query()함수 - 원소 업데이트:
update()함수
최종 코드 구현
아래는 세그먼트 트리를 이용하여 구간 곱을 계산하는 C++ 코드입니다:
#include <iostream>
#include <vector>
using namespace std;
// 세그먼트 트리 클래스 정의
class SegmentTree {
private:
vector tree; // 트리 저장
int size; // 원본 배열의 크기
// 하위 배열의 곱을 계산하는 함수
long long buildTree(const vector& arr, int node, int start, int end) {
if(start == end) {
return tree[node] = arr[start];
}
int mid = (start + end) / 2;
return tree[node] = buildTree(arr, node*2, start, mid) * buildTree(arr, node*2+1, mid+1, end);
}
public:
// 생성자
SegmentTree(const vector& arr) {
size = arr.size();
tree.resize(4 * size);
buildTree(arr, 1, 0, size - 1);
}
// 특정 구간의 곱 구하기
long long query(int node, int start, int end, int L, int R) {
if(R < start || end < L) return 1; // 곱셈 항등원
if(L <= start && end <= R) return tree[node]; // 전체 노드 범위
int mid = (start + end) / 2;
return query(node*2, start, mid, L, R) * query(node*2 + 1, mid + 1, end, L, R);
}
// 외부에서 호출할 수 있는 함수
long long query(int L, int R) {
return query(1, 0, size - 1, L, R);
}
};
int main() {
int N, Q;
cin >> N; // 배열 크기
vector A(N);
for(int i = 0; i < N; i++) {
cin >> A[i]; // 배열 요소 입력
}
SegmentTree segtree(A); // 세그먼트 트리 생성
cin >> Q; // 질의 수
for(int i = 0; i < Q; i++) {
int L, R;
cin >> L >> R; // 질의 범위 입력
cout << segtree.query(L - 1, R - 1) << endl; // 결과 출력 (0-based index 변환)
}
return 0;
}
코드 설명
- buildTree() 함수는 세그먼트 트리를 구축하는 데 사용됩니다.
- query() 함수는 주어진 구간에 대한 곱을 계산합니다.
- main() 함수에서 입력을 받고, 처리된 구간 곱을 출력합니다.
시간 복잡도
세그먼트 트리의 구축 시간은 O(N), 각 질의에 대한 응답 시간은 O(log N)입니다.
따라서 전체 알고리즘의 최악의 시간 복잡도는 O(N + Q log N)입니다.
이는 큰 입력 데이터도 효율적으로 처리할 수 있도록 해줍니다.
마무리
코딩 테스트에서 주어지는 문제에 대해 적절한 자료 구조와 알고리즘을 선택하는 것은 매우 중요합니다.
이번 강좌에서는 세그먼트 트리를 이용한 구간 곱 구하기 문제를 다뤄보았고, 이를 통해 효율적인 방법이 무엇인지 살펴보았습니다.
알고리즘 문제를 풀며 코딩 능력을 향상시키기를 바라며, 앞으로도 다양한 주제를 다루어 가겠습니다.