[PS를 위한 자료구조 7강] 세그먼트 트리의 응용 (금광 세그)

PS를 위한 자료구조 1-7강

# 다양한 세그먼트 트리 테크닉, 금광 세그 # 에 대해 알아보겠습니다.

​

아래의 문제를 한 번 보겠습니다.

​

[연속합과 쿼리]

https://www.acmicpc.net/problem/16993

​

구간 합 구하기 4를 풀어보신 분들이라면 다음과 같은 생각을 할 수 있을 것 같습니다.

​

배열을 누적합으로 만든 다음, 구간 내 최댓값에서 최솟값을 빼면 되지 않을까요?

​

아쉽게도 해결하기 어려운 반례가 존재합니다.

최댓값이 최솟값보다 앞서서 나오는 경우에는 해결이 불가능하기 때문이죠.

​

위의 문제를 해결하기 위해 만들어진 테크닉이 바로 "금광 세그"라고 불리는 테크닉입니다.

​

금광이 나오는게 좀 뜬금없는데, 금광은 2014년 중등부 정보올림피아드에서 출제된 문제의 이름입니다.

당시 만점을 받은 학생이 단 한 명도 없었던 것으로 유명하죠.

이 때 유명해져서 이 테크닉의 이름이 금광 세그로 명명되었습니다.

​

​

앞서서 세그먼트 트리에 대해서 설명할 때, 짧게 언급되었던 부분이 있습니다.

​

세그먼트 트리의 노드는 두 자식의 결합으로써 만들어집니다.

여기서 결합이라고 하는 것은 단순히 합이나 곱이 아닌 복잡한 연산일 수 있습니다.

​

노드를 설계해보겠습니다.

​

Class 노드:
    int 왼쪽최대, 오른쪽최대, 최대, 구간합
    
# 1. 왼쪽 최대는 왼쪽 경계부터 시작해서 연속한 최댓값입니다.
# 2. 오른쪽 최대는 오른쪽 경계에서 시작해서 연속한 최댓값입니다.
# 3. 최대는 이 구간 내의 최댓값입니다.
# 4. 구간합은 구간 내의 총합입니다.

예시를 들어봅시다. 노드가 다음과 같은 배열을 포함하고 있다고 해볼게요.

[1, 1, 0, -1000, 1000, -1000, 0, 1, 1]

 

여기서 왼쪽 최댓값은 얼마일까요? 1+1+0 = 2 입니다.

오른쪽 최댓값은 얼마일까요? 1+1+0 = 2 입니다.

최댓값은 중간의 딱 하나, 바로 1000입니다.

구간합은 -996입니다.

​

또 다른 노드가 다음과 같다고 해볼게요.

[8000, 1, -10000, 1, 1000]

왼쪽 최댓값은 8001, 오른쪽 최댓값 1001, 최댓값은 1001, 구간합은 -998입니다.

​

이 두개의 노드가 담당하는 구간을 합친 새로운 노드를 만든다고 가정해봅시다.

​

[1, 1, 0, -1000, 1000, -1000, 0, 1, 1] + [8000, 1, -10000, 1, 1000]

 

​

실제로 배열을 보고 다시 연산을 한다면 매우 구하기 쉽겠지만, 자료가 많아진다면 시간이 매우 오래걸릴 겁니다.

따라서 주어져 있는 값들만을 가지고 새로운 노드의 값들을 갱신해야합니다.

​

​

1. 왼쪽최대

​

가장 왼쪽에서 연속한 가장 최대의 값을 가져야합니다.

이때 가능한 값을 추려보면 2가지 값밖에 없습니다.

​

(1) 왼쪽 노드의 왼쪽최대

(2) 왼쪽 구간합 + 오른쪽 노드의 왼쪽최대

​

따라서 다음과 같이 쓸 수 있습니다.

왼쪽최대 = MAX(LEFT.왼쪽최대, LEFT.구간합 + RIGHT.왼쪽최대)

2. 오른쪽최대

​위의 논리대로라면 오른쪽 최대 역시 다음과 같이 쓸 수 있습니다.

오른쪽최대 = MAX(RIGHT.오른쪽최대, RIGHT.구간합 + LEFT.오른쪽최대)

3. 최대​

가장 생각하기 힙든 부분입니다. 하지만 잘 생각해보면 후보는 3개뿐입니다.

 

(1) 왼쪽 노드의 최대

(2) 오른쪽 노드의 최대

(3) 왼쪽 노드의 오른쪽 최대 + 오른쪽 노드의 왼쪽 최대

​

각각 왼쪽이 가진 최대, 오른쪽이 가진 최대, 둘의 결합으로 생겨나는 최댓값인 것이죠.

따라서 최댓값은 다음과 같습니다.

최대 = MAX(LEFT.최대, RIGHT.최대, LEFT.오른쪽최대 + RIGHT.왼쪽최대)

​4. 구간합

둘을 더해주면 됩니다. 생략.

​​

그림으로 요약하면 다음과 같습니다.

​그럼 위의 예시에서 구해볼까요?

[1, 1, 0, -1000, 1000, -1000, 0, 1, 1] + [8000, 1, -10000, 1, 1000]

​

왼쪽최대 = MAX(2, -996 + 8001) = 7005

오른쪽최대 = MAX(1000, -998 + 1) = 1000

최대 = MAX(1000, 8001, 2 + 8001) = 8003

구간합 = -996 -998 = -1994

​

그럼 이제 두 노드를 합쳐주는 결합 연산을 만들어줍시다.

def 결합(노드 LEFT : int, 노드 RIGHT : int) -> 노드:
    // 두 노드를 결합한 새로운 노드를 반환
    NEW노드 = 노드() // 반환해줄 새로운 노드 형성
    // 값을 등록
    NEW노드.왼쪽최대 = MAX(LEFT.왼쪽최대, LEFT.구간합 + RIGHT.왼쪽최대)
    NEW노드.오른쪽최대 = MAX(RIGHT.오른쪽최대, RIGHT.구간합 + LEFT.오른쪽최대)
    NEW노드.최대 = MAX(LEFT.최대, RIGHT.최대, LEFT.오른쪽최대 + RIGHT.왼쪽최대)
    NEW노드.구간합 = LEFT.구간합 + RIGHT.구간합
    // 반환
    return NEW노드

세그먼트 트리는 다음과 같이 일반화 될 수 있습니다.

 

int 트리[사이즈]
int 절반 = 사이즈 >> 1

def 전처리(구간의왼쪽 : int, 구간의오른쪽 : int, 노드 : int) -> None:
    if 구간의왼쪽 == 구간의오른쪽:
        트리[노드] = 해당값
        return
    중간 = 구간의왼쪽 + 구간의오른쪽 >> 1
    전처리(구간의왼쪽, 중간, 노드<<1)
    전처리(중간+1, 구간의오른쪽, 노드<<1|1)
    # 노드는 두 자식간의 결합으로 완성
    트리[노드] = 결합(트리[노드<<1], 트리[노드<<1|1])

def 업데이트(번호 : int, 추가값 : int, 구간의왼쪽 : int, 구간의오른쪽 : int, 노드 : int) -> None:
    if 구간의왼쪽 == 구간의오른쪽:
        수정(트리[노드], 추가값)
        return
    중간 = 구간의왼쪽 + 구간의오른쪽 >> 1
    if 번호 <= 중간:
        업데이트(번호, 추가값, 구간의왼쪽, 중간, 노드<<1)
    else:
        업데이트(번호, 추가값, 중간+1, 구간의오른쪽, 노드<<1|1)
    트리[노드] = 결합(트리[노드<<1], 트리[노드<<1|1])

def 쿼리(L : int, R : int, 구간의왼쪽 : int, 구간의오른쪽 : int, 노드 : int) -> None:
    if 구간의오른쪽 < L or R < 구간의왼쪽:
        return 항등원 // 답에 전혀 영향을 주지 않는 존재여야함
    if L <= 구간의왼쪽 and 구간의오른쪽 <= R:
        return 트리[노드]
    중간 = 구간의왼쪽 + 구간의오른쪽 >> 1
    # 두 자식간의 결합으로 반환
    return 결합(쿼리(L, R, 구간의왼쪽, 중간, 노드<<1), 쿼리(L, R, 중간+1, 구간의오른쪽, 노드<<1|1))

세그먼트 트리의 가장 일반화된 모습입니다.

여기서 '결합'함수만 바꾸면 대부분의 형태의 세그먼트 트리를 만들어낼 수 있습니다.

​

정답코드를 첨부합니다.

​

[재귀]

http://boj.kr/db7662f7ae2e45349741c37685898f6f

​

[비재귀]

http://boj.kr/19658c410d884cbcb43b09925087734f

​

​

연습문제를 투척합니다.

​

[수열과 쿼리 10]

https://www.acmicpc.net/problem/13557

​

[금광]

https://www.acmicpc.net/problem/10167

​

피드백 및 오류 지적은 언제나 환영입니다.

​

질문은 댓글로 해주셔도 되고, 제 유튜브 채널을 방문해서 하셔도 되고, 오픈채팅방으로 하셔도 됩니다.

​

[유튜브 : 승욱은] 승욱은 - YouTube

[ 1:1 오픈채팅방] 카카오톡 오픈채팅 (kakao.com)