[Swift] 조합구현

코딩 테스트 준비를 하면서 조합 코드를 작성해 두고 긁어와서 조금 수정해서 쓴다거나 하는 일이 많아졌다. 그래서 오늘은 조합을 Swift로 구현하는 방법에 대해 포스팅하려고 한다. 여기에서의 조합 코드란 주어진 Collection의 원소들을 주어진 수 n개 포함하는 조합의 개수가 몇개인지를 구하는 코드를 의미한다. 조합의 개수야 점화식으로 재귀 돌리면 되니...

 

IDEA : 지금 이 원소를 뽑거나 뽑지 않거나

 보통 우리가 손으로 {1, 2, 3, 4, 5} 집합에서 2개를 뽑는 조합을 다 적는다고 하면, 다음과 같은 순서를 생각하며 적는다.

{1, 2, 3, 4, 5} 집합에서 2개의 원소를 순서 없이 뽑는다.

1. 1을 뽑는 경우
   1) 2를 뽑는 경우 -> {1, 2}
   2) 2를 뽑지 않는 경우
        1) 3을 뽑는 경우 -> {1, 3}
        2) 3을 뽑지 않는 경우
        ...
                     1) 5를 뽑는 경우 -> {1, 5}
2. 1을 뽑지 않는 경우
   1) 2를 뽑는 경우
        1) 3을 뽑는 경우 -> {2, 3}
        2) 3을 뽑지 않는 경우
        ...

 1. 어떤 숫자를 뽑는다고 가정한다.

 2. 남은 숫자들에 대해 n-1개를 뽑는다.

 3. 어떤 숫자를 뽑지 않는다고 가정한다.

 4. 남은 숫자들에 대해 n개를 뽑는다.

전체적인 구조가 한 경우를 끝까지 팠다가 다시 나왔다가 팔 수 있는 다음 경우를 끝까지 파는, DFS 방식이다.

DFS 방식은 재귀로 구현할 수도 있고, stack으로 구현할 수도 있다. 사실상 재귀를 활용한 방식은 컴퓨터 내부의 함수호출 stack을 사용하는 거나 마찬가지라 따지고 보면 둘 다 stack을 활용한 구현인데 이렇게 분류하는게 맞는지 모르겠다. 아무튼 stack 자료구조를 프로그래머가 활용하느냐에 따라 stack, 재귀가 구분된다고 생각하고... 아래는 코드이다. https://inuplace.tistory.com/1189 이분의 코드를 중점적으로 참고했다. 아포카토가 먹고 싶다.

 

1. 재귀로 구현하는 경우

func combination_recursive<T: Comparable>(_ array: [T], _ target_len: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < target_len {
        return result
    }
    
    func recursive(_ now_index: Int, _ now_array: [T]) {
        if now_array.count == target_len { // 더 이상 숫자를 뽑을 필요가 없으니 종료
            result.append(now_array)
            return
        }
        
        for idx in now_index..<array.count {
            //각 index에 대해, 해당 index를 뽑는 경우와 아닌 경우(다른 index를 뽑는 경우)를 recursive하게 수행
            recursive(idx + 1, now_array + [array[idx]])
        }
    }
    
    recursive(0, [])
    
    return result
}

 

2. Stack으로 구현하는 경우

func combination_stack<T: Comparable>(_ array: [T], _ target_len: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < target_len {
        return result
    }
    var stack = array.enumerated().map{([$0.element], $0.offset)}
    
    while stack.count > 0 {
        let now = stack.removeLast()
        let elements = now.0
        let index = now.1
        
        if elements.count == target_len {
            result.append(elements)
            continue
        }
        
        guard index+1 <= array.count-1 else {continue}
        
        for i in index+1...array.count-1 {
            stack.append((elements+[array[i]], i))
        }
    }
    
    return result
}

이제 빵을 먹을 것이다. 호기심에 눈이 멀어서 메모리&시간 사용량을 재고 있는데 느려서 화딱지가 나는 하루. 이거 진짜 어떻게 못하나? 결과가 나오는 대로 이어서 공유하겠다. 재밌겠다.