46 순열
46 순열
문제
Given an array nums of distinct integers, return all the possible permutations.
You can return the answer in any order.
조건
- $1 \le nums.length \le 6$
- $-10 \le nums[i] \le 10$
- All the integers of nums are unique.
예제
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Input: nums = [1]
Output: [[1]]
해결
1st
1 생각
- 순열이란?
- 순서 있는 집합을 다른 순서로 뒤섞는 연산
- n개의 원소에 대해 $n! = n \times (n - 1) \times (n - 2) \times \dotsb \times 2 \times 1$ 경우의 수
# 4자리 수: 4 x 3 x 2 x 1 = 24 경우의 수
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
- 배열의 숫자는 같은데 인덱스만 다양하게 바꿔야 하는 상황
- 근데 사실 어떻게 바꿔야 할지 모르겠다
- 개념을 모르나? 순서 있는 집합을 다른 순서로 뒤섞는 연산임을 안다
- 규칙을 모르나? 위에처럼 규칙에 따라 나열할 수 있다
- 근데 개념과 패턴을 코드로 못 바꾼다?
- 개념에 대한 이해가 부족하거나
- 규칙에 대한 이해가 부족하거나
- 개념이나 규칙이 아닌 다른 무엇에 대한 이해가 필요하거나
- 개념과 규칙 외에, 개념과 규칙을 개발 언어로 바꾸고 최적화하는 능력은 별개
- 어떻게 보면 창조의 영역 같은데, 이걸 어떻게 잘할 수 있을까?(#TODO)
- 일단 지금으로 봐서는 규칙에 대한 이해가 부족한 거 같다.
- 모를 땐? 검색
# source: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
def do_permutation(nums, nums_len):
# 1. 1 6 7 3 5 4 2
idx1 = nums_len - 1
while idx1 > 0 and nums[idx1 - 1] >= nums[idx1]:
idx1 -= 1
# 2. idx1이 0보다 작으면 모두 내림차순으로 종료 케이스
if idx1 <= 0:
return False
# 3. 찾아낸 오름차순인 수보다 큰 수가 우측에 있으면, `다음 내림차순` 준비
idx2 = nums_len - 1
while nums[idx2] <= nums[idx1 - 1]:
idx2 -= 1
# 다음 내림차순 위한 치환
# 4. 1 6 7 4 5 3 2
nums[idx1 - 1], nums[idx2] = nums[idx2], nums[idx1 - 1]
# 다음 내림차순이 시작된 후 idx1과 idx2 사이의 숫자는 다시 정순으로 정렬되어야 다음 순열이 진행되므로, 뒤집는다
# 5. 1 6 7 4 2 3 5
idx2 = nums_len - 1
while idx1 < idx2:
nums[idx1], nums[idx2] = nums[idx2], nums[idx1]
idx1 += 1
idx2 -= 1
return True
- 어떻게 위의 규칙을 알고리즘화 했을까?
# 1. 1 6 7 3 5 4 2
- 첫번째
while문의 목적: 오름차순인 인덱스(nums[4] = 3) 찾기
# 2. 종료 케이스
- 오름차순으로 정렬된 숫자를 내림차순 순열로 바꾸는 과정
- 따라서 원래는 가장 큰 우측의 수보다 좌측의 모든 수들이 크다면, 더 이상 진행할 순열이 없다는 의미이므로 종료
# 3. 다음 내림차순 수의 인덱스 찾기
- 두번째
while문의 목적: 다음 내림차순 순열을 만들기 위한 다음 수의 인덱스 찾기 - 내림차순이 아닌 인덱스의 수보다 큰 수의 인덱스(
nums[6] = 4) 찾는다
# 4. 1 6 7 4 5 3 2
- 내림차순이 아닌 인덱스의 수를 다음 내림차순 순열의 수와 치환한다
# 5. 1 6 7 4 2 3 5
- 핵심인 부분인 거 같은데 너무 간단하게 되어 있다. 정렬의 이해가 선행되어야 할 것 같다
- 위에서
nums[4]와nums[6]을 바꾼 것은 다음 내림차순 순열 시작을 의미한다- 그 말은
1 6 7 3 5 4 2에서5 4 2는 이미 역순 정렬이 끝났음을 의미 1 6 7 4 5 3 2에서2와5를 치환하는 것만으로 정순 정렬이 됨을 의미5 4 3 2 1에서5와1을 치환하고,4와2를 치환하면1 2 3 4 5가 되는 것과 같다
- 그 말은
정리
- 결국 코드 자체는 발견한 규칙과 마찬가지다. 오름차순에서 시작해서 내림차순으로 끝난다
- 오름차순인 수를 내림차순으로 바꿔 나간다
- 오름차순인 부분을 찾고,
- 내림차순 수로 바꾸고,
- 나머지 수를 정순으로 만들어 다시 내림차순으로 바꿔 나간다
- 세 while문을 정리하자면
첫번째 while문: 오름차순인 부분의 인덱스를 찾고두번째 while문: 다음 내림차순이 될 수를 찾는다세번째 while문: 다음 내림차순이 된 수 다음 이미 역순 정렬되어 있는 수를 정순 정렬로 바꾼다
- 개발과 코딩에 익숙해진다는 건, 규칙을 컴퓨터에 맞게 코드를 쓸 수 있는 능력이란 건 알고 있었는데, 새삼 새롭게 느껴진다. 저 세 while문은 규칙을 컴퓨터에 맞게 필요 최소한으로 구현해 냈다. 설명을 코드로 바꾸는 능력은 어떻게 기를 수 있을까?
1 코드
def permute(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
ans = [nums[:]]
def do_permutation(nums_curr, nums_len):
# 1. 1 6 7 3 5 4 2
idx1 = nums_len - 1
while idx1 > 0 and nums_curr[idx1 - 1] >= nums_curr[idx1]:
idx1 -= 1
# 2. 종료 케이스
if idx1 <= 0:
return False
# 3.
idx2 = nums_len - 1
while nums_curr[idx2] <= nums_curr[idx1 - 1]:
idx2 -= 1
# 4. 1 6 7 4 5 3 2
nums_curr[idx1 - 1], nums_curr[idx2] = nums_curr[idx2], nums_curr[idx1 - 1]
# 5. 1 6 7 4 2 3 5
idx2 = nums_len - 1
while idx1 < idx2:
nums_curr[idx1], nums_curr[idx2] = nums_curr[idx2], nums_curr[idx1]
idx1 += 1
idx2 -= 1
ans.append(nums_curr[:])
return True
while result := do_permutation(nums, len(nums)):
continue
return ans
1 결과: 성공
25 / 25 test cases passed.
Status: Accepted
Runtime: 40 ms
Memory Usage: 14.2 MB
2nd
2 생각
- DFS로 구현을 해보자
- 모든 경우의 수를 조합해 나가면 되지 않을까? 그러면 어떻게 모든 경우의 수를 DFS로 조합할 수 있을까?
DFS?
- Depth First Search, 깊이 우선 탐색
- 방식은?
- 자료 구조를 그래프로 볼 때
- 가장 말단의 노드(리프 노드)까지 도달하여 종료 조건을 만나 백 트래킹할 때까지
- 재귀적으로 함수를 호출하여
- 원하는 데이터를 탐색하는 방법
경우의 수?
- DFS로 경우의 수를 만든다면 아래와 같이 자기 자신을 제외한 수가 자식 노드로 붙어 가는 형식이 될 것이다.
depth
1 [ 1, 2, 3 ]
2 [2] [3] [1] [3] [1] [2]
3 [3] [2] [3] [1] [2] [1]
종료 종료 종료 종료 종료 종료
- 종료 지점은?
- 전달된 배열 nums(
[1, 2, 3])의 길이와 depth가 같아지는 경우
- 전달된 배열 nums(
2 코드
def second(self, nums: List[int]) -> List[List[int]]:
ans = []
nums_len = len(nums)
'''
nums: 원본 배열. 요소를 계속 붙여 나가야 하므로 계속 전달
permutaion: 순열을 만들어 나갈 배열
depth: 백 트래킹 조건
'''
def dfs(nums, permutaion, depth):
# 배열의 길이만큰 깊어지면 종료
if depth == nums_len:
ans.append(permutaion)
return
for num in nums:
if not num in permutaion:
"""
permutaion.append(num) (X)
- append를 하면 기존 permutation에 추가되고, 유지된다.
- 리프 노드에서 백 트래킹 후 기존 permutation 배열이 있어야 하므로, 전달 시에는 이전 배열 유지 위해 + 연산자 사용
"""
dfs(nums, permutaion + [num], depth + 1)
dfs(nums, [], 0)
return ans
2 결과: 성공
25 / 25 test cases passed.
Status: Accepted
Runtime: 32 ms
Memory Usage: 14.3 MB
3rd
3 itertools
- itertools에는 permuation과 combination 등 유용한 함수들 있다
- permuation의 소스 코드는 링크 참조
3 코드
def third(self, nums: List[int]) -> List[List[int]]:
return list(map(list, itertools.permutations(nums)))
회고
- dfs가 더 빠른 것 같지만, 함수 콜 스택이 많이 쌓이면 안 좋다고 들었던 거 같다
- 알고리즘 공부를 통해 배울 것은 결국 아래 세 가지일 것 같다
- 문제에 해당하는 샘플들을 통해 규칙을 찾고,
- 규칙을 사람의 말로 설명하고,
- 그 설명을 컴퓨터에 맞는 코드로 변환