[Swift 알고리즘] 순열(Permutations)과 조합(Combinations)

안녕하세요 여러분~!

오늘은 코테에서 종종 나오게 되는 순열과 조합을 살펴볼게요.

이 또한 파이썬에서는 내장함수가 있지만

우리의 Swift는 직접 구현해야 합니다 🥲

하지만 이자식 나름 쉽더라구요? 같이 한번 뿌셔봅시당!

 

순열(Permutation)이란?

순열의 정의부터 살펴볼게요. 순열이란

서로 다른 n개 중에서 r개를 택하여 일렬로 배열하는 경우 입니다.

 

예제를 통해 알아볼까요?

array = [1,2,3]

 

array에서 2개의 요소를 고른다고 해봅시다.

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

 

이렇게 6개의 경우가 나올거에요.

이때 순열은 순서가 다르면 다른 경우로 보기때문에

[1,2] 와 [2,1] 은 다른 경우로 인식하게 됩니다.

 

조합이란?

조합은 순열과 비슷한 개념인데

서로 다른 n개 중에서 순서 상관없이 r개를 택하는 경우 입니다.

 

예제를 통해 알아볼까요?

array = [1,2,3]

 

array에서 2개의 요소를 고른다고 해봅시다.

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

 

이렇게 3개의 경우가 나올거에요.

조합은 순서에 영향을 받지 않기 때문에

[1,2] 와 [2,1] 은 같은 경우로 보기에 중복으로 추가하지 않습니다.

 

순열(Permutation) 코드

먼저 파이썬에서는 순열을 어떻게 간단하게 쓰는지 볼까요?

import itertools
cases = itertools.permutations([1,2,3], 2)

# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

너무너무 간단하게 함수 하나만 호출하면 되거든요..!

저희도 순열을 함수로 쓸 수 있도록 직접 만들어봅시다

 

func permutations<T>(_ array: [T], _ k: Int) -> [[T]] {
    var result: [[T]] = [[]]

    func backtracking(_ ans: inout [T], _ visited: inout [Bool]) {
        if ans.count == k {
            result.append(ans)
            return
        }

        for i in 0..<array.count {
            if visited[i] {
                continue
            }

            visited[i] = true
            ans.append(array[i])
            backtracking(&ans, &visited)
            ans.removeLast()
            visited[i] = false
        }
    }

    var ans = [T]()
    var visited = Array(repeating: false, count: array.count)
    backtracking(&ans, &visited)
    return result
}

 

코드를 하나하나 살펴보겠습니다.

 

먼저 inout 키워드를 사용하여 ans와 visited를 백트래킹 함수에 전달하여 완전탐색을 하겠습니다.

ans는 완전탐색을 하면서 값들을 넣고 빼는 용도의 리스트입니다.

visited는 해당 요소가 방문했는지 여부를 체크하는 리스트입니다.

 

이때 inout 키워드를 왜 쓰나요?

기본적으로 Swift에서 함수에 값을 매개변수 전달하면 값타입으로 전달합니다.

매개변수가 상수(let) 이기 때문에 수정이 불가능합니다.

 

어어..? 우리는 값을 넣고 뺄때마다 ans와 visited를 수정해야되는데요?

그래서 매개변수를 수정할 수 있도록 inout을 사용하여 매개변수를 참조값으로 전달하는 것입니다.

참조값이기 때문에 이 코드 내에 존재하는 모든 ans와 visited는 같은 값을 바라보게 됩니다.

 

요약하자면,

매개변수로 보내는 값을 모두 공유하고 싶을 때 inout 키워드를 사용한다.

 

그럼 이제 backtracking함수를 살펴볼까요?

백트래킹함수는 완전탐색을 할 때 많이 사용했던 템플릿인데요.

순열과 조합도 백트래킹의 일부이기 때문에 코드가 비슷합니다.

 

재귀함수이고, DFS와 비슷한 형태입니다.

리스트의 요소를 한번씩 순회하며 모든 경우의 수를 탐색하는 로직입니다.

재귀 함수를 돌며 방문한 node개수가 k개가 되는 순간의 ans를 result에 넣어줍니다.

(위 트리에서 검정색 노드가 모두 해당 경우입니다.)

if ans.count == k {
    result.append(ans)
    return
}

 

 

이때 중복되는 노드값이 ans에 들어가면 안되기 때문에

visited에 해당 노드가 이미 있는지 확인하는 코드를 넣어줍니다.

(위 트리에서 회색 노드가 모두 이 구문에서 막힌 경우입니다.)

if visited[i] {
    continue
}

 

 

만약 permutations([1,2,3], 2) 를 호출한다면,

결과값은 [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)] 이 나올겁니다.

 

조합(Combination) 코드

이번에는 조합을 살펴보겠습니다.

파이썬에서 조합을 어떻게 쓰는지 볼까요?

import itertools
cases = list(itertools.combinations([1,2,3], 2))

# [(1, 2), (1, 3), (2, 3)]

 

 

조합도 Swift 함수로 만들어봅시다.

순열보다 코드가 훨씬 간단한데요.

func combinations<T>(_ array: [T], _ k: Int) -> [[T]] {
    var result: [[T]] = [[]]
    
    func backtracking(_ start: Int, _ ans: inout [T]) {
        if ans.count == k {
            result.append(ans)
            return
        }
        
        for i in start..<array.count {
            ans.append(array[i])
            backtracking(i + 1, &ans)
            ans.removeLast()
        }
    }
    
    var ans: [T] = []
    backtracking(0, &ans)
    return result
}

 

 

순열과 마찬가지로 조합도 백트래킹 함수로 완전탐색을 하겠습니다.

이번에는 visited 리스트를 고려하지 않습니다.

대신 시작점을 나타내는 start 매개변수를 넣어주도록 하겠습니다.

 

시작점 start를 이용하는 이유는 다음과 같습니다.

조합은 순서를 고려하지 않기 때문에 앞선 순회에서 방문한 노드를

다시 방문할 필요가 없기 때문입니다.

 

 

재귀 함수를 돌며 방문한 node개수가 k개가 되는 순간의 ans를 result에 넣어줍니다.

(위 트리에서 검정색 노드가 모두 해당 경우입니다.)

if ans.count == k {
    result.append(ans)
    return
}

 

이번에는 노드를 순회할 때 start 매개변수를 활용하여 필요한 노드만 순회하겠습니다.

for i in start..<array.count {
    ans.append(array[i])
    backtracking(i + 1, &ans)
    ans.removeLast()
}

 

이렇게 되면

만약 combinations([1,2,3], 2) 를 호출한다면,

결과값은 [(1,2),(1,3),(2,3)] 이 나올겁니다.