Permutations

Permutations - LeetCode

접근 방법 [필수 작성]

제한조건 체크

• nums 길이 최대 6이므로 최대 6! 의 연산
• 모든 정수는 유니크한 값 (같은 숫자 중복 우려 x)

수업에서 배웠던 재귀함수를 활용한 구현으로 접근

기본 구조

candidate.append()
permute()
candidate.pop()

코드 구현 [필수 작성]

# 4시40분 시작 - 5시00분 끝

class Solution:
    def permute(self, nums):

        def backtrack():
            #print(candidate)
            if len(candidate) == len(nums):
                #print(candidate)
                answer.append(candidate[:])
                return
            
            else:
                for num in nums:
                    if num not in candidate:
                        candidate.append(num)
                        backtrack()
                        candidate.pop()

        answer = []
        candidate = []

        backtrack()

        return answer

배우게 된 점 [ 필수 X ]

오류코드

answer.append(candidate[:])

사본을 복사해서 저장하지 않으면 실제 answer 에 적용되지 않는 문제

# 4시40분 시작

class Solution:
    def permute(self, nums):

        def backtrack():
            #print(candidate)
            if len(candidate) == len(nums):
                print(candidate)
                answer.append(candidate)
                return
            
            else:
                for num in nums:
                    if num not in candidate:
                        candidate.append(num)
                        backtrack()
                        candidate.pop()

        answer = []
        candidate = []

        backtrack()

        return answer

Input

nums =

[1,2,3]

Stdout

[1, 2, 3][1, 3, 2]
[2, 1, 3][2, 3, 1]
[3, 1, 2][3, 2, 1]

Output

[[],[],[],[],[],[]]

Expected

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

질문 [ 필수 X ]

Q1 참조에 대한 이해 → Combination에도 동일 질문 존재

파이썬의 작동방식에 따른 얕은 복사와 깊은 복사의 차이에 대한 이해가 어렵습니다.

왜 꼭 candidate 를 복사해서 answer 에 저장해주어야 하는가?

append 할 당시에는 candidate 는 적절한 순열세트를 가지고 있는게 아닌가?

얕은 복사만 되어서 최종적으로 모든 list 가 pop 되었을때, 참조해서 가져오기 때문에 그런것인가?

그럼 answer.append(candidate[:]) 또한 얕은 복사인데 왜 이런 문제가 발생하지 않는가?

피드백 [ 코치 작성 ]

파이썬은 모든 변수를 객체로 다루는 언어입니다. 변수의 값이 변경되는 방법은 mutable immutable 속성마다 다른데 immutable 객체는 변경할 값을 갖는 새로운 객체(또는 사전에 생성되어 존재하는 객체)를 생성하여 참조를 변경하는 방식으로 진행되고 mutable 객체는 객체 내부에 존재하는 다른 객체에 대한 참조를 변경하는 방식으로 진행됩니다.(mutable 객체의 내부 값이 아닌 그 자체의 참조를 변경하는 것과는 다른 얘기입니다.) 그렇기에 다른 언어들의 복사와는 차이를 갖게 됩니다.

이에 파이썬 사용자들은 복사를 할 때 재귀적으로 객체 내부의 원소들에 대해서도 복사를 하는 행위를 깊은 복사라고 정의내렸으며 이는 복사를 할 대상이 immutable 객체가 될 때 까지 재귀를 진행하겠다는 의미입니다.

이제 candidate를 복사하는 이유를 살펴보겠습니다.

candidate는 append할 당시 적절한 순열 세트를 가지고 있습니다. 하지만 이를 깊은 복사를 하지 않고 append를 할 경우 이후 재귀에서 진행되는 candidate와 참조를 공유하며 이후 candidate의 값의 변동에 따라 이미 answer에 append된 candidate또한 값이 변하게 됩니다. 그렇기에 candidate를 깊은 복사 하여 append를 해야 합니다.

candidate[:]는 인덱스 슬라이싱을 통한 복사이며 기본적으로 인덱스 슬라이싱은 재귀적인 복사를 지원하지 않기에 얕은 복사라고 불립니다. 하지만 candidate의 내부 원소들은 모두 immutable 객체인 int형이며 재귀적으로 복사를 하지 않더라도 깊은 복사와 같은 결과를 반환합니다. 그렇기에 앞서 설명한 참조가 공유되는 문제가 발생하지 않습니다.