[Swift] 순열과 조합(Permutation / Combination) 구현해보기

코딩 테스트 문제를 풀어보며 순열과 조합이 많이 사용되는 것을 느꼈다. 몇 번은 다른 분이 블로그에 작성해놓은 것을 그대로 가져다 사용하며 문제를 해결하는 데에 목적을 두었지만, 이제부터라도 확실하게 이해하기 위해 구현해보며 블로그에 적어두기로 하였다. 자세하게 작성해보자.

순열 Permutation

순열이란 서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것이라고 한다. 

 

예를 들어, [1, 2, 3]와 같이 3개의 원소를 가진 배열이 있을 때 순서에 상관있게 2개씩 나열하면 다음과 같은 결과가 나올 것이다.

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

위 결과에서 볼 수 있듯이 결과에는 같은 원소가 반복되지 않는 것을 알 수 있다. 이것이 순열을 구현할 때 가장 중요한 요소인 것 같다. 이를 이용해서 구현해보자.

 

전체적인 과정을 간단히 얘기해보면, 비어있는 배열의 count가 원하는 target Count가 될 때까지 인덱스를 증가시켜가며 재귀적으로 순열 함수를 호출한다. 이때, 각 원소가 이미 추가됐는지 확인하기 위해 체크해주는 변수를 따로 선언해주어 check 변수의 해당하는 인덱스 값이 false일 경우에만 배열에 추가해주었다.

 

아래의 코드를 보자.

func permutation(_ target: [String], _ targetNum: Int) {
    
    var result: [[String]] = []
    // 사용된 원소인지 확인하기 위한 변수
    var check = [Bool](repeating: false, count: target.count)
    
    // 위의 변수들을 이용하기 위해 안에 연산만 하는 함수 구현
    func permute(_ arr: [String]) {
        if arr.count == targetNum {
            result.append(arr)
            return
        }
        for i in 0..<target.count {
        	// 이미 사용된 원소인지 확인
            if check[i] == true {
                continue
            } else {
                check[i] = true
                permute(arr + [target[i]])
                check[i] = false
            }
        }
    }
    permute([])
    print(result)
}

target은 주어진 배열이다. 위의 예시에서 보았던 [1, 2, 3]을 생각하면 된다. targetNum은 내가 원하는 r이다. 위 예시에선 2개를 나열하므로 2라고 생각하면 된다. 

result는 만들어진 배열을 담기 위해 선언된 변수이다.

check는 위에서 말했듯이 사용된 원소인지 확인하기 위해 target과 동일한 개수의 원소를 false로 갖는 배열이다.

내가 원하는 구현 방법에서는 위의 두 변수를 이용해야 했으므로 permutation 내에서 실제 연산을 하는 함수를 선언하고 result와 check를 전역변수로 사용하였다.

 

이제 permutate함수를 보자. 

arr는 원소를 담을 배열이라고 생각하자. 즉, 위에서 말한 처음에 비어있는 배열을 나타낸다. 이를 프로퍼티로 갖는 이유는 재귀적으로 호출되기 때문에 지금까지 만들어진 arr에 계속해서 원소를 추가해야 하기 때문이다.

arr의 원소 개수가 targetNum과 같다면 result에 추가해주고 return을 통해 함수를 끝낸다.

아닐 경우엔 순서가 상관있으므로 첫번째 인덱스부터 target을 확인하여 해당 원소가 이미 사용됐는지 check변수를 통해 판단 후 arr에 넣거나 continue 하거나 결정한다.

 

구현할 때에는 string을 원소롤 갖는 배열을 이용했지만 그때그때 바꾸면서 하면 될 것 같다.

 

 

조합 Combination

 

조합이란 위의 순열의 정의에서 순서에 상관없게 선택 혹은 나열하는 것이라고 생각하면 된다. 

 

위와 같은 예시를 들어 설명해보겠다. [1, 2, 3]의 배열에서 순서에 상관없이 2개의 원소를 골라 나열해보면 다음과 같은 결과가 나온다.

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

순열을 구현했던 것을 통해 조합도 간단하게 구현할 수 있다. 차이점은 순서가 상관없으므로 앞의 인덱스를 다시 확인할 필요가 없을 것이다. 이것이 무슨 말인지 아래 코드를 보며 설명해보겠다.

 

import Foundation

func combi(_ targetArr: [String], _ targetNum: Int, _ index: Int, _ arr: [String]) {

    // 맨 앞의 인덱스부터 확인하지 않으므로 check변수 필요 없음
    if arr.count == targetNum {
        print(arr)
        return
    }
    
    // 순서가 상관없으므로 앞의 인덱스를 확인할 필요가 없음
    for i in index..<targetArr.count {
        combi(targetArr, targetNum, i+1, arr + [targetArr[i]])
    }
}

먼저 프로퍼티부터 확인해보자. 주어진 배열을 나타내는 targetArr, 순열 코드에서 보았던 것과 동일하게 원하는 개수를 나타내는 targetNum, 원소를 담을 배열인 arr는 순열과 동일하다.

위에서 말했듯이 순서가 상관없기 때문에 combi 함수 내에서 for문을 돌 때 첫 번째 인덱스부터 돌 필요가 없다. 예시를 들어 확인해보자. 

[1, 2, 3]이 주어진 배열이고 현재 배열이 [1]이라고 해보자. 함수를 통해 [1]은 뒤의 인덱스인 2와 3이 추가되어 [1, 2], [1, 3]을 출력할 것이다. 다음으로 배열에 2가 들어왔다고 가정해보자. 만약 이때, for문에서 0부터 시작한다면 arr에는 targetArr[0]인 1이 다시 추가된다는 의미이다. 즉 [2, 1]이 구해지게 되고 이는 [1, 2]와 동일하므로 조합의 목적에 맞지 않는다. 따라서 이전의 인덱스는 확인할 필요가 없는 것이다. 이러한 이유 때문에 index를 프로퍼티로 받게 되는 것이다.