글 읽기 - 세그먼트 트리 구현. 반례 또는 로직의 문제가 궁금합니다.

bbbjihan 2년 전 0

각 노드가 [구간 내 최소값의 배열 내 인덱스, 구간의 시작인덱스, 구간의 끝인덱스]로 구성되어있는 세그먼트 트리를 구현하였습니다. 루트노드부터 시작하여 탑-다운 방식으로 구현하였는데, 노드의 첫번째 값인 최소값의 배열 내 인덱스를 기준으로 좌측 구간과 우측 구간을 해당 노드의 좌,우 자식노드에 각각 입력하여 리프노드까지 완성합니다.

쿼리문은 어차피 트리의 크기가 2**ceil(log2(최대배열의 길이)+1)보다 작을 것이기 때문에 아무리 커도 30만보다 작을 것으로 예상되어 트리의 원소에 for문을 돌려 모든 노드의 구간 내에서의 최대사각형의 넓이로 최댓값을 갱신하여 리턴하였습니다.

테스트케이스의 최대 크기가 제한되어 있지 않기 때문에 쿼리문의 시간복잡도를 좀 더 고려하여 구현하기 해야겠지만, 답을 제출하였을 경우 시간초과가 나기 이전에 '틀렸습니다.'가 출력됩니다.

게시판에 나와 있는 모든 반례가 통과됩니다.

로직 상에 어떤 문제가 있는지 아무리 찾아봐도 모르겠습니다. 도움 부탁드립니다.

+테스트케이스로 N=100000, 모든 사각형의 높이가 1000000000인, 모든 값이 최대인 테스트케이스 입력해보았으나 문제가 없었습니다.

from math import log2
import sys;rl=sys.stdin.readline

#수열의 시작과 끝을 전달하면 최솟값의 인덱스를 반환하는 함수
def getMinIndex(start,end):
    global An
    if start<=end:
        return An[start:end+1].index(min(An[start:end+1]))+start
    return False

#탑다운 방식을 위해서 전역변수로 트리를 선언하고, 트리의 루트노드부터 리프노드까지 값을 채워나감
#트리의 각 노드는 [구간 내 최소값의 An에서의 인덱스,구간시작,구간끝]형태로 저장됨.
def init():
    global leafLevel,ST,An
    N = An[0]
    minIndex = getMinIndex(1,N)
    ST[0], ST[1] = None, [minIndex,1,N]
    level = 1
    while level <= leafLevel:
        for nodeIndex in range(2**(level-1),2**level,2):
            if ST[nodeIndex//2]:
                parentNodeValue,parentNodeStart,parentNodeEnd = ST[nodeIndex//2]
                if parentNodeValue > 0 and getMinIndex(parentNodeStart,parentNodeValue-1):
                    ST[nodeIndex] = [getMinIndex(parentNodeStart,parentNodeValue-1),parentNodeStart,parentNodeValue-1]
                if parentNodeValue < N and getMinIndex(parentNodeValue+1,parentNodeEnd):
                    ST[nodeIndex+1] = [getMinIndex(parentNodeValue+1,parentNodeEnd),parentNodeValue+1,parentNodeEnd]
        level+=1

def query():
    global ST
    Max = 0
    for node in ST:
        if node == None:
            continue
            #구간 내에서의 최소높이 * 구간의 길이를 사각형의 크기로 하여 최댓값과 계속 비교,갱신해줍니다.
        Max = max((node[2]-node[1]+1)*An[node[0]],Max)
    return Max

while 1:
    inp = rl().rstrip()
    if inp == '0':
        break
    An = list(map(int,inp.split()))
    #각 직사각형의 높이값을 의미하는 배열이 입력, An[0]은 직사각형의 갯수
    leafLevel = int(log2(An[0]))+2
    ST = [None for _ in range(2**leafLevel)]
    init()
    print(query())

azaraks 2년 전 2

이 문제를 세그먼트 트리로 푼다면, 구간 최솟값을 로그 시간에 구하기 위해서입니다.
그러니 getMinIndex 같은 녀석이 필요하지 않도록 구현해야 의미가 있습니다.
지금 코드는 그냥 query에 getMinIndex 넣은 것 보다 느릴 것으로 예상됩니다. 당연히 그보다 더 빠른건 매번 min을 사용한 경우입니다. (물론 이 경우 TLE 입니다.)

세그먼트 트리 구현이 어렵다면 스택을 사용해서도 풀이가 가능하다는 점도 고려해보시면 좋을 것 같습니다.
세그먼트 트리로 푸신다면 getMinIndex가 0을 리턴하면 False 취급 된다는 점이 고려가 안되어있으나 세그먼트 트리가 잘 구현 된 경우 애초에 필요가 없었을 함수이므로 다시 짜실 때 고려하실 필요는 없을 것 같습니다.

bbbjihan 2년 전 0

답변 감사드립니다. 제가 지금 구현한 방식이 세그먼트 트리의 시간복잡도에 대한 장점을 제대로 다루지 못한다는 부분은 이미 알고 있습니다.

query가 지금 작성한 코드 그대로 통과한다면 굳이 시간복잡도를 줄일 필요가 없어서 혹시나해서 제출하였으나, 문제는 query문의 시간초과 문제 이전에 틀렸습니다 가 출력되는 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그먼트 트리 구현. 반례 또는 로직의 문제가 궁금합니다.

bbbjihan 2년 전 0

azaraks 2년 전 2

bbbjihan 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말