[파이썬 알고리즘 인터뷰][그래프] 순열

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

순열 구현

 

책에서 구현된 코드

# 재귀
def permute(self, nums: list[int]) -> list[list[int]]:
    results = []
    prev_elements = []
    
    def dfs(elements):
        if len(elements) == 0:
            results.append(prev_elements[:])
        
        for e in elements:
            next_elements = elements[:]
            next_elements.remove(e)
            
            prev_elements.append(e)
            dfs(next_elements)
            prev_elements.pop()
    
    dfs(nums)
    return results
    
#itertools
def permute(self, nums: list[int]) -> list[list[int]]:
    return list(itertools.permutations(nums))

 

기억해야할 기법

• list copy
  
  • list[:]

 

내가 구현한 코드

def permute(nums: list[int]) -> list[list[int]]:
    discovered = [True for _ in range(len(nums))]
    result = []

    def dfs(depth: int, tmp_res: list[int]):
        for idx, val in enumerate(nums):
            if discovered[idx]:
                if depth == len(nums) - 1:
                    result.append(tmp_res + [val])
                else:
                    discovered[idx] = False
                    dfs(depth+1, tmp_res + [val])
                    discovered[idx] = True

    dfs(0,[])
    return result

• 비슷해보이는데 또 책이 더 빠르다
• 책에서는 매 재귀마다 element를 append pop, next_elements는 deepcopy임
• 리스트의 연산(+)이 느린가 싶다