글 읽기 - 파이썬 시간초과가 뜨는 이유를 모르겠네요

jww0418 2년 전 1

이진 탐색 아이디어로 구현했습니다. 최악의 경우 sum을 구하는 과정에서 2 * 10^6, 전체적으로 이진 탐색 하는 while구문에서 log2 10^9이라 nlogn으로 문제가 없다고 생각했는데 시간초과의 이유를 모르겠습니다.

import sys

n, m = map(int, sys.stdin.readline().strip().split())
li = list(map(int, sys.stdin.readline().strip().split()))

up = max(li)
down = min(li)
height = (up + down) // 2

while True:
    sum = 0
    for i in li:
        if i > height:
            sum += i - height
    
    if sum >= m:
        down = height
        height = (up + down) // 2
    else:
        up = height
        height = (up + down) // 2
    
    if up - down == 1:
        height = down
        break
print(height)

djm03178 2년 전 1

반례입니다.

1 1
1

jww0418 2년 전 0

이런식으로 제대로 바꿔도 시간초과가 납니다. 아무래도 알고리즘 상의 문제인것 같은데, 진짜 도저히 모르겠습니다.

import sys

n, m = map(int, sys.stdin.readline().strip().split())
li = list(map(int, sys.stdin.readline().strip().split()))

up = max(li)
down = min(li) - 1
height = (up + down) // 2

while True:
    sum = 0
    for i in li:
        if i > height:
            sum += i - height
    #얻은 나무의 높이 sum에 저장 
    
    if sum >= m:
        down = height
        height = (up + down) // 2
    else:
        up = height
        height = (up + down) // 2
    #이진 탐색 과정 
    
    if up - down == 1:
        height = down
        break #이진 탐색 종료 조건
print(height)

jww0418 2년 전 0

문제는 max와 min함수를 사용해서였습니다. 거기서 시간복잡도가 많이 증가했더군요;; 그냥 최대범위, 최소범위(상수)로 바꾸니 바로 통과되었습니다.

djm03178 2년 전 2

그 문제가 아닙니다. 고치신 코드는 아래와 같은 케이스에서 여전히 무한 루프를 돕니다.

max나 min이나 매우 빠른 O(N)의 시간 복잡도이기 때문에 그것만으로 516ms와 5초의 시간 제한을 넘기는 차이가 생길 수는 없습니다.

2 3
2 2

jww0418 2년 전 1

아 위에처럼 했다는 것은 아닙니다. 위에서는 단순한 예외처리를 이용하였으나 본질적인 문제는 down을 -1부터 출발시켜야 한다는 것을 실수했음을 깨닫고 아래 코드와 같이 고쳤습니다. 그러나 이게 제가 이 문제를 맞은 본질적인 이유는 아니라고 봅니다. max와 min을 고치니 그제서야 통과되었습니다.

저도 max나 min이 시간복잡도가 N이여서 작을 것이라고 생각했는데, 다른 질문글에서 max와 min에서 시간을 많이 잡아먹으니 주어진 상수로 고치라는 글을 보았습니다. 이렇게 바꾸니 바로 통과가 되었습니다. 이 부분에 대해서는 저도 궁금한데, 상세히 알려주실 수 있으신가요? 제가 초보라서 많이 부족하니 구체적으로 말씀해주시면 감사하겠습니다.

import sys

n, m = map(int, sys.stdin.readline().strip().split())
li = list(map(int, sys.stdin.readline().strip().split()))

up = 1000000000
down = -1
height = (up + down) // 2

while True:
    sum = 0
    for i in li:
        if i > height:
            sum += i - height
    #얻은 나무의 높이 sum에 저장 
    
    if sum >= m:
        down = height
        height = (up + down) // 2
    else:
        up = height
        height = (up + down) // 2
    #이진 탐색 과정 

    if up - down == 1:
        height = down
        break #이진 탐색 종료 조건
print(height)

다시 말씀드리지만 max와 min은 문제가 아닙니다. 어디에서 max와 min이 느리다는 글을 보셨는지 모르겠으나, 증거를 보여드립니다. max와 min이 문제였다면 맞은 코드에 그 둘을 추가하는 것만으로도 시간 초과가 나야 할 텐데 (아니면 최소 5초에 가깝게 나오거나), 통과된 코드랑 별 차이가 없습니다. http://boj.kr/464f5dedc0f14274...

문제가 되는 것은 탐색 범위가 어떻게 정해지느냐에 따라 25번째 줄에 영영 걸려들지 않게 될 수가 있다는 점입니다. 제가 위에서 제시해드린 케이스들은 각 코드에서 그렇게 되도록 하는 것을 찾은 것입니다. up과 down을 저렇게 고정하면 통과되는 것은 만드신 코드 로직상 처음 up과 down이 2 이상 차이나면 무한 루프를 돌 수가 없기 때문입니다. 하지만 1 이하로 차이날 경우 25번째 줄에 걸리지 않게 되는 것이 가능하고, 그러면 무한히 루프를 돌게 됩니다.

djm03178 2년 전 3

down이 min이 아닌 0부터 시작해야 한다는 점은 맞지만 그건 답이 틀려야 할 뿐 시간 초과의 원인은 아닙니다. 처음 코드에서 max와 min을 그대로 남겨놓고 통과하는 코드를 보여드립니다.

http://boj.kr/a3392224bd0b4639...

jww0418 2년 전 0

수정된 코드를 보고 무엇이 문제인지 확실히 알았습니다. 상세한 답변 정말 감사드립니다. 이진 탐색의 종료 조건으로, 굳이 1차이가 아닌 1 이하의 차이가 나면 되는 것을 깨달았습니다.

다시 한번 시간내어서 답변해주셔서 감사드립니다.

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

문제

문제

출처

ICPC

파이썬 시간초과가 뜨는 이유를 모르겠네요

jww0418 2년 전 1

djm03178 2년 전 1

jww0418 2년 전 0

jww0418 2년 전 0

djm03178 2년 전 2

jww0418 2년 전 1

djm03178 2년 전 1

djm03178 2년 전 3

jww0418 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말