Sample : Caetano Veloso - Avarandado ( http://www.youtube.com/watch?v=yI5XZrwAkyk )
이제 인덱스드 트리가 다양한 형태의 문제들에 어떻게 적용될수있는지 알아보자.
--------------------------------------------------------------------
처음에 소개할 문제는 다음과 같다.
링크 - PKU 2750 : Potted Flower
http://poj.org/problem?id=2750
설명하자면, 원탁에 N개의 화분이있고, 각각의 화분에는 그 화분이 얼마나 매력적인지를 나타내는 수치가 정해져있다.
그 수치는 양수일수도, 음수일수도 있으며 큰 숫자일수록 그 화분은 더 매력적으로 보인다.
이제 이 원탁에 아치 모양의 둥근 의자를 배치하려 하는데, 의자에 접해있는 화분들의 매력수치의 총합을 최대로 하려고 한다.
의자의 길이조절은 자유롭게 할 수 있다. 단, 의자가 N개의 화분을 모두 포함하는 경우는 제외한다.
그런데, 고양이가 난입해서 특정 위치에 있는 화분을 다른 화분으로 바꿔 놓는 경우가 있단다 -_-...
이런 경우는 M번 일어나며, 그때마다 매력수치의 총합이 최대가 되도록 의자를 다시 만들어 배치해야 한다.
N, M의 범위는 100,000이하이다.
Sample Input
5 // N이 입력된다.
3 -2 1 2 -5 // N개의 화분의 매력지수가 입력된다.
4 // M이 입력된다.
2 -2 // 고양이가 2번째 위치의 화분을 -2의 매력지수를 갖는 화분으로 바꿔치기했다는 뜻
5 -5 // 고양이가 5번째 위치의 화분을 -5의 매력지수를 갖는 화분으로 바꿔치기했다는 뜻
2 -4 // 고양이가 2번째 위치의 화분을 -4의 매력지수를 갖는 화분으로 바꿔치기했다는 뜻
5 -1 // 고양이가 5번째 위치의 화분을 -1의 매력지수를 갖는 화분으로 바꿔치기했다는 뜻
Sample Output
4 // 첫번째 바꿔치기 이후의 답
4 // 두번째 바꿔치기 이후의 답
3 // 세번째 바꿔치기 이후의 답
5 // 네번째 바꿔치기 이후의 답
요약하자면 그냥 숫자 N개가 원형으로 배열되어 있을 때, 그것의 부분구간들 중 합이 최대인 것을 찾아서 그 최대값을 출력하는 문제이다. 여기서 나올 수 있는 부분구간의 개수는 (N-1) * N이다. 구간의 길이가 1부터 (N-1)까지 가능하고, 일정 길이를 가진 구간은 N개가 나올 수 있기 때문이다.
이 문제를 인덱스드 트리를 써서 쉽게 해결할 수 있다. 아 물론 트리를 원형으로 만들지는 않는다.
우선, 이 숫자들이 원형이 아닌 일직선으로 배열되어 있다고 가정하고 문제를 풀어보자.
이전에 포스팅에서 다룬 것처럼 인덱스드 트리의 노드의 대표값을 단순히 자기 자식들의 총합으로 설정한다음 부분구간의 합들을 모조리 구해서 그중 최대를 구하는 방식은 당연히 Time Limit Exceeded가 뜬다. 부분구간의 개수가 N의 제곱에 비례하기 때문에 시간복잡도가 N^2 * logN 이 되기 때문이다.
인덱스드 트리의 기본적인 쓰임만을 기억하고 있다면 응용 문제를 풀 수가 없다. 좀더 머리 굴려 생각을 해보시라.
우선 대표값을 4개를 설정하자.
하나는 자기 자식들의 총합으로 하고, 이를 sum이라고 하자.
두번째는 자기 자식들의 부분구간의 합 중 최대인 값으로 하고, 이를 maxsum이라고 하자.
예를 들어 어떤 노드가 포함하고 있는 최말단 노드들의 데이터가 차례로 3, -4, 2, -1, 4, -6, 1, 3 이라면, 그 노드의 maxsum 값은 5가 된다. [2, -1, 4] 이 부분구간의 숫자의 합이 5이고, 다른 부분구간들의 숫자의 합은 5보다 작기 때문이다.
세번째는 자기 자식들 중 제일 왼쪽에 있는 값을 포함하는 구간들 중 합이 최대인 값으로 하고, 이를 leftmax 라고 하자.
예를 들어 어떤 노드의 자식들 중 최말단 노드들의 데이터가 3, -4, 2, -1, 4, -6, 1, 3 인 경우 leftmax의 값은 4이다. 제일 왼쪽 숫자인 3을 포함하는 구간들 중에서 [3, -4, 2, -1, 4] 이 구간의 합이 4로 최대이기 때문이다.
마지막으로 네번째는 자기 자식들 중 제일 오른쪽에 있는 값을 포함하는 구간들 중 합이 최대인 값으로 하고, 이를 rightmax 라고 하자.
예를 들어 어떤 노드의 자식들 중 최말단 노드들의 데이터가 3, -4, 2, -1, 4, -6, 1, 3 인 경우 rightmax의 값은 4이다. 제일 오른쪽 숫자를 포함하는 구간들 중에서 [1, 3] 이 구간의 합이 4로 최대이기 때문이다.
이렇게 대표값을 정해 놓고, 자식들의 대표값으로부터 부모의 대표값을 어떻게 구해야 되는지를 알아보자.
1. sum
우선 sum은 당연히 자식들의 sum 값의 합이다.
트리를 구조체로 선언했다고 하고 이를 식으로 쓰면 아래와 같다.
(아래 표현이 컴파일러에서 제대로 돌아가는 식은 당연히 아니다.. 이해를 위해 저렇게 적어놓았을 뿐)
tree[부모].sum = tree[왼쪽자식].sum + tree[오른쪽자식].sum
2. maxsum
maxsum 값은 왼쪽 자식의 maxsum값, 오른쪽 자식의 maxsum값, 그리고 왼쪽 자식의 rightmax + 오른쪽 자식의 leftmax 요 세 값들 중 큰것을 선택하면 된다.
tree[부모].maxsum = max{ tree[왼쪽자식].maxsum,
tree[오른쪽자식].maxsum,
tree[왼쪽자식].rightmax + tree[오른쪽자식].leftmax }
왜 이렇게 되는지 잘 생각해보길 바란다. 점화식을 많이 다뤄본 사람이거나 Dynamic Programming을 많이 해보았다면 이해가 빠를 것이다.
3. leftmax
그냥 이제 식으로만 쓰겠다.
tree[부모].leftmax = max{ tree[왼쪽자식].leftmax, tree[왼쪽자식].sum + tree[오른쪽자식].leftmax }
4. rightmax
tree[부모].rightmax = max{ tree[오른쪽자식].rightmax, tree[왼쪽자식].rightmax + tree[오른쪽자식].sum }
이렇게 해서 트리의 아래부터 루트까지 올라가면서 쭉 값을 설정해주면 된다. 물론 최말단 노드에서의 초기값은 sum, maxsum, leftmax, rightmax 다 그 노드의 숫자값으로 해주면 된다. 그러면 문제의 답은 루트의 maxsum값이 된다.
시간을 생각해보면, 처음 데이터를 집어넣고 트리의 모든 노드의 값들을 설정하는 데에는 2*N 정도의 시간이 든다. 그 다음 고양이가 화분을 M번 바꿨다고 했을 때, 바꾼 노드의 부모 노드들만 갱신해주면 되니까 logN개의 노드만 갱신해 주면 된다. 따라서 처리 시간은 M * logN이 걸린다. 따라서 문제는 2*N + M * logN 정도의 시간이 걸리며, 이는 충분히 1000ms 내에 수행 될 수 있다.
하지만 우리는 화분이 일직선으로 있을 때의 문제를 해결했을 뿐이다. 화분이 원형으로 있을 경우에는 어떻게 해야 할까? 우리가 추가로 생각해야 하는 건, 직선형으로 배열했을 때는 나올 수 없지만 원형으로 배열되었을 때에는 나올 수 있는 구간들만 추가로 고려해주면 되는 것이다. 즉, 다시 말해 1번째 화분과 N번째 화분이 모두 포함되어있는 구간을 고려해주면 된다.
답은 아주 간단하다. 원형으로 배열되었을때만 나올 수 있는 구간의 합은, 전체 숫자들의 합에서 나머지 화분들로 이루어진 구간의 합을 뺀 값으로 생각해볼 수 있다. 이에 착안하여 발상을 전환하자. 대표값 3개를 더 설정하자. minsum, leftmin, rightmin 이렇게. 이것들의 정의는 이것들의 이름만 딱 봐도 알것이다. 구하는 방법도 위에 maxsum, leftmax, rightmax를 구하는 방식이랑 비슷하게 하면 된다. 이렇게 하면 구간의 합의 최소값을 구할 수 있다. 이를 전체 숫자의 합에서 빼버리면, 바로 원형으로 배열되었을 때만 나올 수 있는 구간의 숫자의 합의 최대값이 나온다.
따라서, tree[루트].maxsum 이것과 tree[루트].sum - tree[루트].minsum 요 두개의 값들 중 큰 것을 택해 출력하면 되는 것이다!
아직 우리가 생각을 안한 조건이 딱 하나 남아있는데, 뭐냐면 구간이 모든 N개의 숫자들 다 포함하면 안된다는 것이다. 그거는 굳이 설명 안해도 여기까지 잘 따라온 분들이라면 알아서 처리할 수 있을 것이다. 그냥 힌트를 주자면, 모든 N개의 숫자를 포함하는 구간의 합이 답이 되는 경우는 모든 숫자가 양수일 때만 가능하다는 걸 이용하면 된다.
이상으로 이 문제의 풀이를 마치겠다. 풀이 방법에서 Dynamic Programming을 푸는 듯한 느낌을 받을 수가 있는데, 엄밀히 말하면 인덱스드 트리 자체가 DP에 포함된다. 이전의 결과를 이용하여 다음의 결과를 구하는 방식이니까.
위 문제를 이해했다면 요 문제도 한번 생각해 보시라.
링크 - PKU 2479 : Maximum sum
http://poj.org/problem?id=2479
--------------------------------------------------------------------
위에 소개한 문제가 인덱스드 트리의 대표값의 사용의 극대화를 요하는 문제였다면,
이제부터 소개할 문제는 인덱스드 트리의 갱신 순서를 이용한 문제이다.
링크 - PKU 2352 : Stars
http://poj.org/problem?id=2352
좌표평면상의 0 <= x <= 32000, 0 <= y <= 32000 범위 내에 N개의 별이 있다. 각각의 별은 정수 좌표에 위치해 있으며, N은 최대 15,000이다. 각각의 별에는 "level"이 존재하는데, 각각 별의 level은 자기보다 위에 있지 않은, 그리고 자기보다 오른쪽에 있지 않은 별들의 개수로 정의된다(자기 자신도 포함시킨다).
예를 들어, 별이 5개고 각각의 좌표가 (1, 1), (5, 1), (7, 1), (3, 3), (5, 5) 라면
5번째 별의 level은 4이다. 3번째 별을 제외한 모든 별들이 x좌표가 5이하이고 y좌표또한 5 이하이기 때문이다.
마찬가지로 구해보면 1번째별은 level 1, 2번째별과 4번째별은 level 2, 3번째 별은 level 3 이다.
출력은 첫줄엔 level 1짜리 별의 개수, 두번째 줄엔 level 2짜리 별의 개수, … , N번째 줄엔 level N짜리 별의 개수를 출력해주면 된다.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
0
어떤 두 별에 대해서 x값과 y값 이렇게 2개의 잣대를 가지고 비교를 해야 하므로, 선형적으로 정렬을 할 수가 없다.
무슨 말이냐면, 단순히 level이 "자기보다 x값이 크지 않은 별들의 개수" 이렇게 정의되어 있었다면, 그냥 x값을 기준으로 쭉 정렬을 한 다음 문제를 간단히 해결하면 된다.
하지만 비교해야 될 값이 2개이므로, 단순히 정렬만 해서는 풀기가 좀 까다로울 것이다.
그렇다고 N개 중 임의의 2개를 택해 일일이 비교를 하자니 N^2 만큼의 시간이 들 테고, 이는 당연히 시간초과이다. N이 15,000이니깐. 방법은 인덱스드 트리를 쓰는 것이다.
어떤 식으로 생각을 하면 되냐면, 일단 인덱스드 트리를 x축이라고 생각하고, 인덱스드 트리의 최말단 노드들을 각각 0 부터 32000까지의 정수에 대응시킨다. 좌표의 범위가 32000이기 때문이다.
노드의 대표값은 그냥 자식들의 숫자의 합으로 설정하고, 초기에는 모든 노드들의 값을 다 0으로 만들어 준다.
그리고 사전에 별들을 y값을 기준으로, 만약 y값이 같다면 x값을 기준으로 오름차순 정렬을 시켜논다. 정렬은 물론 퀵소트나 힙소트 같은 방법으로 해야 된다. 별의 개수가 15,000개니깐.
정렬을 시킨 상태에서 우선 맨 첫번째 별을 인덱스드 트리에 추가한다. 어떻게 추가하냐면 첫번째 별의 x좌표를 보고, 그 위치에 대응되는 인덱스드 트리의 최말단 노드의 값에 +1 을 해준다. 그리고 그 위로 올라가면서 쭉 갱신해준다. 여기에 드는 시간이 log(32000) ≒ 15 이다. 그 다음, 최말단 노드의 맨 왼쪽 값(0의 좌표에 대응된다)과 방금 +1 해줬던 값 까지의 구간의 합을 구한다. 여기에 수행되는 시간은 log(구간의 길이) = log(별의 x좌표) <= log(32000) ≒ 15 이다. 따라서 별 하나당 이 일련의 작업은 30 정도의 시간이 든다.
방금 구한 구간의 합이 바로 그 별의 level이다. 같은 방법으로 다음 별에 대해서도 위와 같은 작업을 수행하면 된다.
이제 감이 좀 잡히는가?
설명하자면, y값 기준으로 별들을 정렬한 상태에서 차례로 인덱스드 트리에 추가하는 것이므로, 어떤 별을 인덱스드 트리에 추가 하는 시점에는 이미 그 별보다 y값이 같거나 작은 별들은 이미 인덱스드 트리에 추가 되어 있다. 또한 인덱스드 트리는 x축 기준으로 설정되어 있다. 따라서, 해당 별을 인덱스드 트리에 추가한 후에 0부터 그 별의 x값까지 구간의 합은, 해당 별보다 x값이 같거나 작고, y값 또한 같거나 작은 별들의 개수와 똑같다. 즉, level을 구한 것이다.
시간이 얼마나 걸리냐를 보면,
(별 정렬하는데에 걸리는 시간) + (인덱스드 트리 작업의 수행시간) = NlogN + N*30 <= 15,000 * 14 + 15,000 * 30 = 660,000.
이는 1억보다 훨씬 작다. 따라서 제한시간 내에 해결 가능하다.
요점은, 2차원 좌표의 점들 처럼 비교해야할 대상이 2개이면, 하나를 시간축(인덱스드 트리에 갱신하는 순서), 다른 하나를 공간축(인덱스드 트리에 갱신하는 위치)으로 보아서 해결하면 된다는 얘기이다.
만일 이 문제에서 좌표의 범위가 아주 커서 이 방식으로 하면 Memory Limit Exceeded가 뜨게 될 경우에는, 사전에 별들을 x값 기준으로 정렬해 놓아서 각각의 별을 인덱스드 트리에 추가할 위치를 미리 설정해놓고 인덱스드 트리를 별의 개수만큼 크기를 잡아서 만들면 되겠다. 한번 더 정렬해야하니까 시간은 더 들겠지만 메모리를 많이 절약할 수 있을 것이다.
이같은 방법으로 풀 수 있는 문제를 하나 더 소개한다.
링크 - PKU 3067 : Japan
http://poj.org/problem?id=3067
참고로 최대 부분증가수열(Longest Increasing Subsequence) 문제도 이같은 방법으로 풀면 NlogN의 시간 안에 해결할 수 있다!
--------------------------------------------------------------------
인덱스드 트리가 단순히 구간의 합이나 구간의 최대, 최소값을 구하는데만 쓰인다고 생각하는 사람들은 위의 문제들에서 컬쳐쇼크를 느낄 것이다(본인 얘기임...ㅠ) 다른 자료구조들도 마찬가지로 예상치 못한 기상천외한 방법으로 응용될 수 있으니 항상 탐구하는 정신을 길러야 할 것이다.
아이유 - 너랑나 이곡을 편곡해봤다
bpm 120대로 맞추느라 목소리 피치를 반음 내렸음
원곡이 하도 전조가 많아서 만들때 많은 고민을 했다
히히 나는 재해석킹!
최근 덧글