출처 : https://www.acmicpc.net/problem/10868
해답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/10868.cpp
위 문제는 n만큼 입력을 받고 m개의 구간을 입력받아 그 구간내에서 최소값을 출력하는 문제이다.
입력에서 구간이 입력되는데 이 구간은 앞수가 작고 뒷수가 크다. 역으로 입력이 들어오진 않는다.
언뜻보면 굉장히 쉽지만 쉬운 문제는 아니다. 단순히 생각만 한다고 풀 수 있는 문제는 아니다.
먼저 이문제를 정확히 이해하기 위해서는 시간복잡도를 계산해 봐야한다. 우선 입력은 어떻게 하지 못하므로 O(N)이 있고 계산시에는 특정 구간이지만 최악의 경우 시작값이 1이고 끝값이 N일수도 있다. 그럼 M이 100,000이 최대라고할때 O(100,000*100,000) 이 된다. 그러므로 당연히 단순 탐색으로는 TL을 피할 수 없다.
이 문제의 풀이방법은 여러가지가 있겠지만, 나는 세그먼트 트리(Segment Tree)로 풀었다. 세그먼트 트리로 풀게 되면 딱히 알고리즘이 있는게 아니고 그냥 그 자체가 된다. 그렇기에 세그먼트 트리란 무엇인지 정리해보겠다.
필자는 https://www.acmicpc.net/blog/view/9#comment-42 여기서 공부하였으며, 내가 이해한바를 다시 정리해보겠다.
우선 세그먼트 트리는 배열안의 특정 구간의 어떤 값을 찾을때 아주 용이하다 이 알고리즘의 시간복잡도는 O(logN)이다.
트리가 다음과 같이 구성되어 있다고 가정하자. 물론 입력에서 n은 2의 제곱수가 아닐 경우는 아주 많을 것이다. 그러나 개념만 이해하면 된다. 우선 n이 8이고 배열 값으로 1부터 8까지 입력을 받았다고 가정하자. 세그먼트 트리의 상위 값으로는 왼쪽 오른쪽 값을 비교하여 문제가 원하는 최소값을 넣는다. 그럼 아마 이런식으로 구성이 될 것이다.
위로 올라가면 두 수를 비교하여 작은 값을 놓고 다시 위로 올라가고 다시 작은 값을 놓고 이런식으로 할 것이다. 하지만 문제에서는 4 7을 입력할수 있다. 그럼 구간 4부터 7까지를 비교해야 하는데 다음과 같은 노드가 체크가 될 것이다.
그럼 저 3가지를 비교하면 최소값을 찾을 수 있다. 이런식으로 비교하면 모든 구간에 대해 최소값을 찾을 수 있다. 바로 소스부터 살펴보겠다.
int init(vector &arr, vector &tree, int node, int start, int end)
{
if (start == end)
return tree[node] = arr[start];
else
return tree[node] = min(init(arr, tree, node * 2, start, (start + end) / 2),
init(arr, tree, node * 2 + 1, (start + end) / 2 + 1, end));
}
//초기화 부분이다
먼저 인자를 살펴보면 처음은 입력받은 배열이 되고, 두번째는 값이 담길트리이다. 트리는 당연히 원래 배열보다 커야한다. 위만 보더라도 8개의 입력배열이 있지만 트리는 (2^4)-1개의 노드를 가지고 있으므로 그만큼의 배열이 되야한다. 계산해보면 대략적으로 3배 미만으로 가지고 있다. 필자는 최대인풋이 10만이므로 트리는 30만개를 가지도록 하였다.
그리고 들어오는 노드는 시작 노드이다. 당연히 시작노드는 1번노드가 되는것이고 시작값은 구간을 의미하고 start와 end는 그 노드가 가지고있는 구간을 의미 한다 즉 1~2, 1~4 등을 의미한다. 그 구간내에서 가장 작은 값을 찾으라는 것이다. 밑 부분에 node*2, node*2+1은 트리의 기본개념을 보면 이해가 가능할것이다. 왼쪽 노드와 오른쪽 노드의 순서 배치를 어떻게 하는지 모른다면 지금 바로 트리의 기본을 다시 공부해야한다.
if문으로 구분한 것은 start==end인경우는 현재 node값이 끝에 도달하여 더이상 왼쪽과 오른쪽이 없다고 생각하면 된다. 그렇기에 값을 주는것이고 그외의 경우는 계속 왼쪽과 오른쪽을 뻗어나가도록 한다.
int MIN(vector &tree, int node, int start, int end, int left, int right)
{
if (left > end || right < start)
return MAX;
if (left <= start && end <= right)
return tree[node];
return min(MIN(tree, node * 2, start, (start + end) / 2, left, right),
MIN(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right));
}
//최소값을 찾는 부분이다
이 부분의 인자를 살펴보면 트리를 넘겨주고 node번호와 이번엔 left, right가 주어지는데 실제 입력에서 구간을 의미 한다. 그리고 해당 구간내에서 최소 값을 계속 찾아간다. min()은 algorithm 헤더에 있으며 구현도 쉽기 때문에 설명을 생략한다.
처음 if (left > end || right < start)이 부분은 node가 담당하는 부분과 찾고자하는 구간이 전혀 겹치지 않을 경우이다. 이때는 찾을 수 없는 경우이므로, MAX값을 리턴해준다. 필자는 MAX를 21억으로 설정했는데, 문제 설명에서 입력값의 최대는 10억이라고 하였기 때문이다. 10억보다 큰 수면 된다.
그리고 두번째 if (left <= start && end <= right)는 노드의 구간값이 찾고자 하는 범위내에 완전히 포함되었다면 그 밑으로는 갈 필요가 없기 때문에 해당 노드의 값을 리턴해준다. 그리고 그 외의 경우는 계속 왼쪽 오른쪽으로 찾으면서 최소값을 찾는다.
쉽지는 않았던 문제이며, 혼자서 완전히 코딩하려면 많은 연습이 필요할 듯 싶다.