순열(Permutation)이란?
서로 다른 정수들로 이루어진 집합이 주어졌을 때, 만들 수 있는 모든 순열을 구하는 문제를 생각해 보겠습니다. 예를 들어 배열이 [2, 1, 3]이라면, 세 개의 원소를 나열할 수 있는 모든 경우의 수인 다음과 같은 결과를 얻게 됩니다.
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
원소가 n개일 때 순열의 총 개수는 n!개입니다. 따라서 위 예시에서는 3! = 6가지의 순열이 생성됩니다.
해결 접근 방식
이 문제는 재귀(recursion)와 백트래킹(backtracking) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 재귀 함수에서 사용할 변수로 대상 리스트(list), 시작 인덱스(start), 현재까지 만든 순열(curr), 결과를 저장할 리스트(res)를 준비합니다.
- start가 리스트 길이 - 1보다 커지면, 지금까지 만든 curr를 res에 추가하고 재귀 호출을 종료합니다.
- start부터 리스트 길이 - 1까지 반복하며 다음 작업을 수행합니다.
- start 위치의 원소와 start + (i - start) 위치의 원소를 교환(swap)합니다.
- permutation(list, start + 1, curr + [list[start]], res)를 호출해 다음 자리의 원소를 결정합니다.
- 탐색이 끝나면 원래 상태로 되돌리기 위해 두 원소를 다시 교환합니다(백트래킹).
- 처음에는 permutation(arr, 0, [], res) 형태로 함수를 호출합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작 방식을 더 명확하게 이해할 수 있습니다.
class Solution(object):
def permute(self, nums):
result = []
self.permute_util(nums, 0, [], result)
return result
def permute_util(self, given_list, start, curr, result):
if start > len(given_list) - 1:
result.append(curr)
return
for i in range(start, len(given_list)):
self.swap(given_list, start, start + (i - start))
self.permute_util(given_list, start + 1, curr + [given_list[start]], result)
self.swap(given_list, start, start + (i - start))
def swap(self, nums, index1, index2):
temp = nums[index1]
nums[index1] = nums[index2]
nums[index2] = temp
ob1 = Solution()
print(ob1.permute([1, 2, 3, 4]))입력
[1,2,3,4]
출력
[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2],[1,4,2,3],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[2,4,1,3],[3,2,1,4],[3,2,4,1],[3,1,2,4],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,2,3,1],[4,2,1,3],[4,3,2,1],[4,3,1,2],[4,1,3,2],[4,1,2,3]]
시간 복잡도와 마무리
이 알고리즘은 각 단계마다 아직 사용되지 않은 원소를 하나씩 선택하고, 탐색이 끝나면 원래 상태로 되돌리는 백트래킹 방식으로 동작합니다. 시간 복잡도는 O(n!)이며, 공간 복잡도는 재귀 호출 스택을 포함해 O(n)입니다. 원소 개수가 많아지면 결과의 수가 급격히 늘어나므로, 실무에서는 itertools.permutations 같은 내장 라이브러리를 활용하는 것도 좋은 대안이 됩니다.