[Algorithm] 조합(Combination)이란? (feat.Swift)

 

안녕하세요 Foma 👟 입니다!

 

오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "조합" 에 대해서 알아보도록 하겠습니다.

 

바로 시작할게요~

---

조합이란?

 

n개의 원소에서 r 개의 원소를  순서에 상관없이 뽑는 경우의 수 - 나무  위키 -

 

순열과 다르게 순서는 중요하지 않아요.

 

쉽게 설명하면 물건을 사고 총 가격을 구하는 것과 비슷해요.

 

과일로 예를 들면 사과,포도,수박이 있다면

 

사과,포도,수박

 

포도,사과,수박

 

수박,사과,포도

 

... 등 어떤 방식으로 사도 총 가격을 똑같겠죠?

 

즉, 이루어진 과일이 똑같다면 하나의 조합으로 생각하는 것입니다.

---

코드 구현

 

먼저 경우의 수를 담을 배열을 만들어줍니다.

 

var cases:[[Int]] = []

 

combination의 파라미터를 설정해주는데

 

인덱스들을 담고있는 indexes

 

뽑아야할 갯수를 정할 pickCount

 

현재 인덱스를 표시할 current

 

뽑은 인덱스를 저장할 picked

 

로 받아줍니다.

 

func combination(indexes: [Int], pickCount: Int, current: Int, picked: [Int]) {...}

 

만약 현재 인덱스가 뽑아야 할 인덱스까지 왔다면 cases에 picked를 넣어줍니다.

 

   if current == pickCount {
        cases.append(picked)
        return
    }

 

 

indexes를 순회하면서 방문한 곳을 true로 해주고 새롭게 뽑은 숫자들을 넣어 재귀해줍니다.

 

 indexes
        .enumerated()
        .forEach{
            if !initialVisited[$0.offset] {
                initialVisited[$0.offset] = true
                var newPicked = picked
                newPicked.append($0.element)
                combination(indexes: indexes, pickCount: pickCount, current: current+1, picked: newPicked,visited: initialVisited)
            }
        }

 

아래와 같이 원하는 조건으로 실행시키면 아래와 같이 조건에 맞게 조합들이 출력되는걸 볼 수 있습니다.

 

combination(indexes: [1,2,3,4,5], pickCount: 3, current: 0, picked: [], visited: [])
print(cases)
  
//[[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

---

전체 소스 코드