[알고리즘][그래프] - 3. 순열

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/permutations/

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라

---

[DFS를 활용한 순열 생성]

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        prev_elements = []

        def DFS(elements):
            #리프 노드일 때 결과 추가
            if len(elements) == 0:
                result.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 result

[itertools 모듈 사용]

import itertools
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

• iterable에서 원소 개수가 r개인 순열 뽑기
• 라이브러리를 사용해서 진행하면 매우 빠르고 효율적이다.. 실제 실무에서 이를 쓰지 않을 이유가 없다. 

---

[객체 복사]

• 파이썬은 모든 것이 객체이다. 문자, 숫자 모두 객체이기 때문에 별도로 값을 복사하지 않는 한 변수에 값을 할당하는 모든 행위는 값 객체에 대한 참조가 된다.
• 이 말은 참조가 가리키는 원래의 값을 변경하면 모든 참조, 즉 모든 변수의 값 또한 함께 변경된다는 말이기도 하다. 
• 참조가 되지 않도록 값 자체를 복사하기 위해서는 [:]를 사용해서 처리하는 방법이 있다.

[[ : ]를 사용한 값 자체만 복사하는 방법]

a = [1,2,3]
b = a
c = a[:]

[결과]
a = [1,2,3]
b = a
c = a[:]
>>>>
id(a) 2295409289984
id(b) 2295409289984
id(c) 2295409866240

• 살펴보듯 c만 새로운 객체가 되었음을 알 수 있다. (즉, a와 b는 같은 객체를 참조하고 있지만 c는 아예 별개의 객체를 참조하고 있다는 뜻이다. 그래도 값은 같다.)

[copy( ) 메소드를 사용해서 값 자체만 복사하는 방법]

d = a.copy()
id(d)


#결과 2295408703680

• 새로운 객체가 되었음을 알 수 있다. 

[copy.deepcopy( ) 중첩된 리스트를 값 자체만 복사하는 방법]

import copy
a = [1,2,[3,5],4]
b = copy.deepcopy(a)

[결과]
id(a) 2295410032128
id(b) 2295410211520
b [1, 2, [3, 5], 4]