Python

[Python] DFS에서 리스트 접근 방법

torimuk 2023. 10. 23. 01:15

Problem


DFS 내에서 리스트를 인덱싱하여 재귀함수의 인자로 넘겨주었는데, 시간초과가 발생하였다.

def cal(_list):
    for num in _list:
        ...
        cal(_list[1:])

 

Solution


이유는 리스트를 슬라이싱 할 때 시간이 걸리기 때문이다.

_list[a:b] 면 b-a만큼 시간복잡도가 발생하는데, 이러한 작업이 DFS 내에서 매번 발생하여 시간이 초과되는 것이다. 따라서 DFS내에서 리스트를 접근하려면, 인자로 리스트가 아닌 리스트의 인덱스를 넘겨주는 것이 성능상 더 좋다.

_list = [1,2,3,4,5]
def cal(start):
    for i in range(start, len(_list)):
        ...
        cal(start+1)

 

URL


삼성그룹 SW, IT취업준비방 내 피드백