yiyun11   2달 전

1번 코드는 단순 list에 본 위치의 정보가 있는지 없는지를 이용하여 방문체크를 한 코드이고,

2번 코드는 다른 분들의 코드에서 아이디어를 얻어 3차원 리스트를 이용하여 방문체크를 한 코드입니다.

이외에 다른 부분은 동일하며, 두 코드 모두 제가 아는 케이스에 한해서 정상적으로 작동합니다.

그런데 1번 코드는 시간초과가 뜨고 2번 코드는 pass를 받았습니다. 그 실행시간의 차이도 심한듯 합니다.

혹시 왜 이같은 차이가 발생하는 걸까요?

list에 값이 있는지 없는지 찾는 시간이 3차원 리스트에 인덱스로 접근하는 시간보다 오래걸려서 그런건가요?

정확한 이유를 알고 싶습니다.

luniro   2달 전

네 맞습니다 3차원 배열이면 O(1)의 시간복잡도로 방문여부 확인이 가능하지만 #1같은 경우는 최악의 경우 거의 매번 리스트 전체를 순회하게 됩니다

pezlunakr   2달 전

파이썬의 in 연산은 기본적으로 선형 탐색입니다.

따라서 가장 앞의 값부터 순회하며 검사하기에, 최악의 경우 O(N)이 걸리게 됩니다.

반면, 인덱스를 통해 바로 접근하는 방식은 순회나 탐색을 하지 않고 직접 메모리 주소를 참조하기 때문에 O(1)입니다.

aksndk123   2달 전

1번처럼 사용하고 싶으면 visit을 리스트가 아닌 set으로 두고 value를 리스트가 아닌 튜플로 사용해서 사용하면 됩니다.

이론상 set에서 in연산은 O(1)의 시간복잡도를 가지니까요.

ex)

visited = set()

visited.add((0,0,0))

비슷한 방식으로  from collections import defaultdict 을 사용해서 defaultdict형식의 key값을 튜플로 사용해서 visit 체크를 할수도 있습니다.

ex)

visit = defaultdict(int) # 기본적으로 모든 key값에 대해서 value의 초기값으로 0을 가짐
visit[(0,0,0)] = 1

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