백준 2357번 최솟값과 최댓값 (Python)

N개의 정수가 주어질 때, 구간 a~b 사이에 최소, 최대값을 찾는 문제입니다.

 

 

아이디어 1. 세그먼트 트리

주어진 숫자 개수 N과 구간 쌍 M개의 범위가 (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)이므로 모두 탐색하면서 찾는다면 시간 초과가 발생할 것으로 예측됐습니다. 그래서 세그먼트 트리를 활용하게 됐습니다.

 

세그먼트 트리는 데이터가 연속적으로 존재할 때 특정 범위의 데이터의 합을 구하는 방법입니다.

 

세그먼트 트리

5 3 8 11 2 9 4 14 8 6 의 연속된 데이터가 있다고 가정해보도록 하겠습니다.

이 숫자들 중 여러 개의 특정 구간의 숫자 합을 구할 때, 계속해서 반복을 통해 구하게 된다면 O(N) 시간이 걸리게 되므로, 데이터의 개수가 많아진다면 시간 초과가 발생해 불가능하게 될 것입니다.

 

트리 구조 활용

트리구조를 활용해서 특정 구간의 합을 구한다면 O(logN)으로 구할 수 있게 됩니다.

 

각 노드가 구간의 합을 가지는 세그먼트 트리의 구조는 기존 데이터들을 트리구조로 나타내는 것과 조금 다릅니다.

최상단 노드는 전체 데이터를 더한 값이 됩니다.

최상단 노드의 자식 노드들은 각각 데이터들을 반씩 나눠가지게 되고, 반씩 나눠가진 데이터들의 합을 노드의 값으로 가지게 됩니다.

다음 자식노드들도 반씩 데이터를 나눠가지고 나눠가진 데이터의 합을 노드의 값으로 가지게 됩니다.

최상단 노드를 1번이라고 했을 때 자식 노드는 2, 3번 노드가 됩니다. 2번 노드의 자식들은 4, 5번이 되고 3번 노드의 자식들은 6, 7번 노드가 됩니다. 이러한 구조를 보았을 때 n번 노드의 자식 노드는 n*2, n*2+1번이 되는 구조임을 파악할 수 있습니다.

이런 식으로 반복하면 전체 노드가 자신의 범위 안에 있는 데이터들의 합으로 나타나게 되고, leaf노드 상에 실제 연속된 데이터 본연 값이 존재하는 것을 알 수 있습니다.

 

예시)

세그먼트 트리 예시

 

세그먼트 트리 구하는 방법

세그먼트 트리를 저장할 변수는 segTree입니다. segTree의 크기는 데이터 의 개수 N*4를 해주면 적당합니다.

그 이유는, 실제 데이터들은 모드 leaf 노드에 위치하게 되므로 leaf노드의 개수가 최대 N개가 존재해야하기 때문입니다. 그러므로 위의 데이터 개수는 10개이므로 leaf노드는 10개 이상이 필요한 2**4인 16개가 됩니다. 이 때 모든 트리의 노드의 개수는 31개가 되므로 약 N*4를 해주면 넉넉한 크기로 데이터들을 저장할 수 있습니다.

 

segTree의 원소들을 재귀를 통해 구해보도록 하겠습니다.

def init(start, end, node):
    if start == end:
        segTree[node] = A[start]
        return segTree[node]

    mid = (start+end)//2
    segTree[node] = init(start, mid, node*2) + init(mid+1, end, node*2+1)
    return segTree[node]

start와 end는 데이터의 범위입니다.

start==end라는 것은 start<=X<=end 범위의 데이터를 구하는 것이므로 X는 연속된 데이터 A의 start번째 데이터입니다.

만약 start!=end라면 start와 end 범위의 데이터들을 반으로 나누어서 다시 재귀적으로 init 함수를 호출해줌으로써 범위 내의 데이터를 모두 더해줄 수 있도록 해줍니다.

해당 값들을 segTree 배열 안에 node 인덱스에 넣어줍니다. node는 왼쪽 자식으로 이동할 경우 *2, 오른쪽 자식으로 이동할 경우 *2+1을 해줍니다.

 

특정 범위의 데이터 합을 구하는 방법

segTree의 원소들이 특정 범위의 데이터 합을 담고 있습니다. 구하려는 범위 내의 데이터 합을 재귀를 통해 구해보도록 하겠습니다.

def find(start, end, left, right, node):
    if start > right or end < left:
        return 0
    if left <= start and end <= right:
        return segTree[node]

    mid = (start+end)//2
    return find(start, mid, left, right, node*2) + find(mid+1, end, left, right, node*2+1)

start, end는 현재 노드가 가지고 있는 구간을 뜻합니다. left, right는 구하려는 특정 구간을 뜻합니다. node는 현재 segTree에서의 index를 뜻합니다.

 

첫 번째 if문은 현재 노드가 가지는 구간의 데이터와 구하려는 데이터 구간이 다른 곳을 의미하므로 0을 반환해줍니다.

두 번째 if문은 현재 노드가 가지는 구간의 데이터가 구하려는 데이터 구간에 포함됐다는 뜻이므로 해당 노드의 값을 반환해줍니다.

두 조건문을 모두 통과했다면 구하려는 데이터 구간이 현재 노드의 구간에 걸쳐져 있다는 뜻이므로 노드의 자식 노드로 이동해서 다시 구간의 합을 찾아줍니다.

 

위와 같이 구할 경우 O(logN)으로 특정 구간의 데이터 합을 구할 수 있습니다.

 

 

문제 풀이

위의 segTree를 구하는 방식을 조금 바꾸어서 segTree의 원소들이 해당 구간의 데이터들 중 최소값이나 최대값을 들고 있도록 했습니다.

def minInit(start, end, node):
    if start == end:
        minSegTree[node] = A[start]
        return minSegTree[node]

    mid = (start+end)//2
    minSegTree[node] = min(minInit(start, mid, node*2),
                           minInit(mid+1, end, node*2+1))
    return minSegTree[node]


def minFind(start, end, left, right, node):
    if start > right or end < left:
        return 1_000_000_001
    if left <= start and end <= right:
        return minSegTree[node]

    mid = (start+end)//2
    return min(minFind(start, mid, left, right, node*2), minFind(mid+1, end, left, right, node*2+1))

minInit의 경우 해당 구간의 데이터들 중 최소값을 원소로 갖을 수 있는 minSegTree를 만들어주고

minFind를 통해 해당 구간의 최소값을 구할 수 있도록 했습니다.

 

최대값 또한 같은 방식으로 구현했습니다.

def maxInit(start, end, node):
    if start == end:
        maxSegTree[node] = A[start]
        return maxSegTree[node]

    mid = (start+end)//2
    maxSegTree[node] = max(maxInit(start, mid, node*2),
                           maxInit(mid+1, end, node*2+1))
    return maxSegTree[node]


def maxFind(start, end, left, right, node):
    if start > right or end < left:
        return 0
    if left <= start and end <= right:
        return maxSegTree[node]

    mid = (start+end)//2
    return max(maxFind(start, mid, left, right, node*2), maxFind(mid+1, end, left, right, node*2+1))

 

그 다음 M개의 구간에 해당하는 값들의 최소값과 최대값을 출력해주도록 했습니다.

for a, b in B:
    print(minFind(0, N-1, a-1, b-1, 1), maxFind(0, N-1, a-1, b-1, 1))

 

 

 

 

 

 

 

세그먼트 트리의 문제를 이전에 풀었었는데, 다시 풀 때 기억이 잘 나지 않아 조금 오래걸리게 되었습니다. 다음 세그먼트 트리의 문제를 다시 확실하게 풀어 제대로된 풀이 방법을 기억해보도록 하겠습니다.