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취업준비방 내 피드백
'Python' 카테고리의 다른 글
[Python] Python에는 왜 long이 없을까? (0) | 2022.10.18 |
---|---|
[Python] *args 와 **kwargs 란? (0) | 2022.06.27 |
[Python] 딕셔너리의 키와 기본 값을 저장하기 (0) | 2022.03.24 |
[Python] 문자열 리스트를 정수 리스트로 변환 (0) | 2022.03.24 |
[Python] 두 딕셔너리의 합 구하기 (0) | 2022.02.08 |