세그먼트트리 (백준 2042) : https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
슬라이딩 윈도우 (백준 11003) : https://www.acmicpc.net/problem/11003
11003번: 최솟값 찾기
N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
www.acmicpc.net
삼성 B형 한번 본적 있는데,, 문제에서 요구하는 건 간단한데 시간을 엄청나게 줄여야 한다는 느낌을 받은 적있다.
데이터를 변경하고 그 데이터 안에서 필요한 특정 데이터를 조회하고,, 여튼 curd를 구현하는 문제였는데 이 두 문제에서 비슷한 느낌을 받아서 정리해 본다.
세그먼트 트리
부분 합을 구하는 알고리즘이다. 알고리즘 설명자체는 https://www.acmicpc.net/blog/view/9 여기 설명이 잘 되어있지만 설명 하자면
선형데이터의 부분합을 나타내는 2진트리 데이터를 만들어서 해당 문제를 풀 수 있다.
말하자면
처럼 data[1] = a, data[2] = b, ..., data[9] = i 이고 left번째 데이터 부터 right 번째 데이터 까지의 합을 구하는 방법을 생각해보는 것이다.
위의 선형데이터의 부분합을 나타내는 2진트리 데이터를 다음과 같이 작성한다.
위와 같이 루트노드의 노드 번호를 1로 하고 1번 노드는 모든 데이터의 합을 저장한다.
2번노드와 3번노드는 각각 부모노드의 왼쪽 부분합 오른쪽 부분합을 저장한다.
저장해야하는 범위의 시작과 끝이 같은 노드는 리프노드가 된다.
조회
이렇게 하면 만약 뭐 4번째 부터 7번째 데이터까지의 합을 구하고 싶다고 한다면 5번노드와 6번노드의 합을 구하면 된다
이것을 위해서는 4개의 인자가 필요한데
i) 구하려고 하는 데이터의 시작 인덱스
ii) 구하려고 하는 데이터의 끝 인덱스
iii) 어떤 노드가 합으로 가지고 있는 범위의 시작 인덱스
iv) 어떤 노드가 합으로 가지고 있는 범위의 끝 인덱스
루트노드 부터 차례대로 탐색하면서 탐색된 노드의 범위가 구하려는 데이터 범위를 아예 벗어난다면 0을,
일부 벗어난다면 두 자식 노드의 합을
완전히 포함된다면 해당 노드의 값을 리턴 하면 결과적으로 부분합을 구해낼 수 있다.
초기화
그렇다면 이 이진트리는 어떻게 만드는 걸까
이진트리의 어떤 노드(N)의 자식노드는 N*2와 N*2+1이라는 점을 이용해서 배열형식으로 만든다.
배열을 선언할 때 배열의 크기는 1에 2를 반복적으로 곱하면서 데이터 길이보다 길어지는 곱회수를 지수로 하는 2의 제곱수정도로 해주면 될거 같다.
이걸 만들어 주기 위해서는 다음과 같은 인자가 필요하다.
i) 만드려고 하는 노드의 번호,
ii) 현재 만들고 있는 부분합의 시작 인덱스,
iii) 현재 만들고 있는 부분합의 끝 인덱스
루트 노드의 합을 두 자식노드의 합으로 하는데 만약 자식노드가 리프노드(시작 인덱스와 끝인덱스가 같은경우) 일경우 리프노드의 값을 데이터의 시작(혹은 끝)인덱스의 값을 리턴하여 구하면 된다.
수정
만약 10번째 데이터를 수정한다면 다음과 같이 logN의 시간 복잡도로 해결할 수 있다.
바꾸려는 타겟인덱스를 보유하는 노드만 파고들면서 리프노드가 나올때까지 탐색하면서 해당 데이터와 바꾸려는 데이터의 차이만큼 노드의 값을 수정해주면 해결이다..
위와같이 엄청난 속도로 부분합을 구하고 수정할 수 있는 대단한 알고리즘이다.
슬라이딩 윈도우
슬라이딩 윈도우는 당연히 아는 개념이지만, 탐색이 진행되면서 바뀌는 데이터들 사이의 최솟값을 구해야 되서 어렵다.
여기서는 슬라이딩 윈도우를 이용해 데이터를 넣되 빼버리는 데이터를 고려해야만 한다.
크기가 3인 슬라이딩 윈도우를 진행하면서 각 진행단계의 최솟값을 구하는 문제였는데,,
각진행단계에서 데이터를 넣긴 넣어야 된다.
이때 만약 새로넣는 값 직전값이 이번에 넣는 값보다 크다면 그 수는 더이상 고려할 필요가 없다.
예를 들어 (3, 4, 9)라는 값이 저장되어 있는데 여기에 2를 넣는다면 3, 4, 9모두 더이상 고려할 필요가 없다. 왜냐하면 슬라이딩 윈도우가 진행되도 각진행단계에서 최솟값이 될리가 없기 때문, 이는 새로 들어온 2가 기존 값보다 작기 때문이다.
이렇게하면 슬라이딩 윈도우의 데이터는 오름차순을 보장하게 된다. 즉 각단계의 처음 값이 최솟값임을 보장 할 수 있다.
이 후 데이터의 첫 번째 값의 index가 현재 단계에서 슬라이딩 윈도우가 가져야하는 범위를 벗어나면 해당 값을 제거해 주는것을 반복해 주면 된다.