2020.12.23 TIL: enumerate, segment tree

파이썬

• enumerate: stack을 사용 할 때 index와 value를 함께 다루기 위해 enumerate을 사용하면 좋다.
  for index, value in enumerate(l):

BOJ6548번을 푸는데 사용한 enumerate() function

import sys
ans = []
while True:
    N, *l = list(map(int, input().split()))
    l.append(0)
    if N == 0:
        break
    stack = []
    area = 0
    for i, h in enumerate(l):
        while stack and l[stack[-1]] > h:
            ih = l[stack.pop()]
            w = i-stack[-1]-1 if stack else i
            if area < w*ih:
                area = w*ih
        stack.append(i)
    ans.append(area)
for i in range(len(ans)):
    print(ans[i])

자료구조

• 세그먼트 트리(segment tree):

관련영상 https://youtu.be/DpSYj7t1sbQ
귀에 쏙쏙 들어오는 설명!
관련문제 https://www.acmicpc.net/problem/6549
분할정복 + 세그먼트 트리(구간에서 min 찾기) 활용

• 요소들의 구간합을 구하는 경우
• 특정 구간에서 가장 큰 값 또는 작은 값을 구하는 경우
• 특정 구간에 대한 정보를 필요로 하는 경우
  에 사용하면 좋다.

세그먼트 트리의 node수는 2^log(n)올림-1 (단, n은 요소의 총 갯수

세그먼트 트리(구간최소값) 만드는 함수와 구간 최소값의 인덱스를 구하는 함수

import sys


def init(input_array, tree_list, node, start, end):
    if start == end:
        tree_list[node] = start
        return start

    # left side
    init(input_array, tree_list, node*2+1, start, (start+end)//2)
    # right side
    init(input_array, tree_list, node*2+2, (start+end)//2+1, end)

    if input_array[tree_list[node * 2+1]] <= input_array[tree_list[node * 2+2]]:
        tree_list[node] = tree_list[node * 2+1]
    else:
        tree_list[node] = tree_list[node * 2+2]


def minIdx(input_array, tree_list, node, start, end, range_left, range_right):

    if end < range_left or range_right < start:
        return -1

    if range_left <= start and end <= range_right:
        return tree_list[node]

    m1 = minIdx(input_array, tree_list, node*2+1, start, (start+end) //
                2, range_left, range_right)
    m2 = minIdx(input_array, tree_list, node*2+2, (start+end) //
                2+1, end, range_left, range_right)

    if m1 == -1:
        return m2
    elif m2 == -1:
        return m1
    else:
        if input_array[m1] <= input_array[m2]:
            return m1
        else:
            return m2