글 읽기 - python 시간초과..

lainroses 6년 전 1

DFS로 방문할때 부모의 번호를 parent라는 list에 추가시키면서 탐색하는 구조입니다..

어떻게 고쳐야 시간초과없이 효율적으로 돌까요....?

import sys
def search(tree, root=1):
    stack = [root]
    visited = []
    parent = [0]*(len(tree)+1)
    while stack:
        visit = stack.pop()
        visited += [visit]
        child = list(set(tree[visit]) - set(visited))
        for c in child: parent[c] = visit
        stack += child
    return parent

tree = {}
for _ in '-'*(input()-1):
    a,b = map(int,sys.stdin.readline().split())
    if not a in tree: tree[a] = []
    if not b in tree: tree[b] = []
    tree[a] += [b]
    tree[b] += [a]
for i in search(tree)[2:]: print i

jh05013 6년 전 1

파이썬 내부 동작이 어떻게 돌아갈 지 유추하면서 시간복잡도를 계산하셨으면 좋겠습니다. set(visited)를 만드는 데 얼마나 걸릴까요? 두 집합을 빼는 연산은 또 얼마나 걸릴까요?

lainroses 6년 전 0

감사합니다. 로직 자체에 문제가 있는 알고 고민하였습니다. 말씀하신대로 while문 안에서 반복되는 set을 만드는 것 뿐만아니라 difference를 하는 연산이 worst case의 경우 O(n^2)까지 가는 것을 알았네요..

다행이 set으로 변환시키지 않고 애초에 만들어넣고 쓰니 통과는 하네요.

difference연산을 빼려면 visited 리스트를 0,1로 방문 체크하면서 하면 더 효율적이겠네요.

감사합니다.

jh05013 6년 전 0

set은 해시를 사용하기 때문에 set을 빼는 연산은 평균 O(n)입니다. 물론 n번 충돌이 계속 발생하면 O(n^2)지만, 그럴 일은 사실상 없습니다.

jh05013 6년 전 0

(물론 연산 한 번에 O(n)이 든다는 뜻입니다.)

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

문제

문제

출처

ICPC

python 시간초과..

lainroses 6년 전 1

jh05013 6년 전 1

lainroses 6년 전 0

jh05013 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말