(백준 2104 부분배열 고르기

• tags : (algorithm

  No matching post could be found

  - (segment tree
• 문제 링크 : https://www.acmicpc.net/problem/2104
• 풀이 링크
  • Python

• 모든 구간을 확인하여 값을 도출해야하고, 각 구간별 합과 최솟값을 찾아야 한다.
• 당연히 완전 탐색 등의 방식은 시간초과가 나게 될 것이고, 다른 방식을 고민해야 한다.

• 처음에는 세그먼트 트리를 활용해서 해결했다.
  • 세그먼트 트리는 합을 구성하는 트리, 최솟값의 인덱스를 가지는 트리 두개로 구성했다.

def __init__(self, N: int, seq: list) -> None:
    self.N = N
    self.seq = [0] + seq
    self.sum_tree = [0] * (1 << ceil(log2(N) + 1))
    self.min_tree = [0] * (1 << ceil(log2(N) + 1))
    self.init(1, 1, N)

def init(self, node: int, start: int, end: int) -> None:
    if start == end:
        self.sum_tree[node] = self.seq[start]
        self.min_tree[node] = start
        return
    mid = (start + end) // 2
    self.init(node * 2, start, mid)
    self.init(node * 2 + 1, mid + 1, end)
    self.sum_tree[node] = self.sum_tree[node * 2] + self.sum_tree[node * 2 + 1]
    if self.seq[self.min_tree[node * 2]] < self.seq[self.min_tree[node * 2 + 1]]:
        self.min_tree[node] = self.min_tree[node * 2]
    else:
        self.min_tree[node] = self.min_tree[node * 2 + 1]

• 다음과 같이 클래스 초기화할 때 sum_tree, min_tree를 선언하고, init()메서드를 활용해서 트리를 초기화한다.
  • 한번에 두개의 트리를 모두 초기화하여 코드가 길어지는 문제가 있지만, 한 번의 탐색으로 가능해서 아마도 시간적인 이점이 있을 것 같다.

def solve(self, start: int, end: int) -> int:
    if start == end:
        return self.seq[start] * self.seq[start]
    values = self.get_values(1, 1, self.N, start, end)
    if values[1] == -1:
        return 0
    sums = [
        values[0] * self.seq[values[1]],
        self.solve(start, values[1] - 1),
        self.solve(values[1] + 1, end),
    ]
    return max(sums)

• 마지막으로 solve()메서드를 활용하여 해결한다.
  • 여기서는 분할 정복을 활용했는데, 각 구간별 최솟값 인덱스 위치를 찾고, 해당 인덱스 기준 왼쪽, 오른쪽으로 나누어 탐색했다.

• 그런데 풀이를 제출하고 보니 새로운 방식의 풀이가 보였고, 모노톤 스택을 활용했다는것을 알게 되었다.
• 모노톤 스택은 하나의 배열을 O(N)의 시간 복잡도로 배열을 오름차순, 내림차순을 유지할 수 있다.

def solution(seq: tuple) -> int:
    stack = []
    answer = 0
    now = 0
    for x in seq:
        left = now
        while stack and x < stack[-1][0]:
            y, left = stack.pop()
            answer = max(answer, y * (now - left))
        stack.append((x, left))
        now += x
    return max(answer, *(x * (now - left) for x, left in stack))

• 코드는 간단하지만, 이해하기에는 시간이 조금 걸렸고, 나름대로 나만의 코드로 녹이는데도 시간이 걸렸다.
• 우선 now값을 통하여 누적합을 구현했고, 구간합을 구하는데 사용했다.
• 만약 스택이 비어있으면 수열의 지금 값과 누적합을 저장한다.
• 스택이 비어있지 않은 경우, 다음을 확인하며 진행한다.
  • 스택의 top에 저장된 값을 확인하여, 오름차순 조건이 안된다면 top의 값을 pop한다. 이 때 저장된 값과 지금 누적합을 활용하면 구간 누적합, 최솟값을 알 수 있고, 정답을 갱신한다.