코딩 테스트에서 빈번하게 사용되는 순열과 조합 알고리즘에 대해 공부해보자.
직접적으로 몇 개의 조합을 찾아라!라는 문제보다는 순열 혹은 조합을 적절히 사용해서 경우의 수를 찾는 문제들이 빈번히 출제되므로 대비해두는 것이 좋다.
1. 순열 (Permutation)
'서로 다른 n 개의 원소 중에서 r 개를 골라 순서를 구분하여 나열한 경우의 수'를 의미한다.
순열은 nPr 로 표현한다.
순열의 개수를 구하는 공식은 n! / (n-r)! 이다.
순열에서 중요한 점은 순서를 구분한다는 점이다.
예를 들어 [1, 2, 3, 4]의 배열에서 순서를 구분하여 3가지 원소를 경우의 수를 나열하면 아래와 같이 24개의 경우의 수가 나온다.
[1, 2, 3]
[1, 2, 4]
[1, 3, 2] //[1, 2, 3] 과 같은 값들이 들어갔지만 순서가 다르므로 다른 경우의 수로 본다.
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]
이를 구현하는 가장 간단한 방법은 for loop를 r번 중첩하여 경우의 수를 구하는 방법이다.
import Foundation
let numberArray: [Int] = [1, 2, 3, 4]
func permutationWithForLoop(array: [Int]) {
var permutaionArray: [[Int]] = []
for i in 0..<array.count {
for j in 0..<array.count {
for k in 0..<array.count {
if i==j || j == k || k == i { //중복 제거
continue
}
//순열 어레이에 i, j, k 번째의 값을 append 시킨다.
permutaionArray.append([array[i], array[j], array[k]])
}
}
}
print("4개의 값에서 3개를 고르는 순열의 수: \(permutaionArray.count)개") //24개
print(permutaionArray)
/*
[[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3],
[2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3],
[3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2],
[4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]
*/
}
permutationWithForLoop(array: numberArray)
for loop를 사용해서 순열을 구할 때 문제점은 무엇일까?
n개중 r 개를 선택할 때 r의 개수만큼 for loop를 중첩해야 한다는 점이다.
따라서 r이 변경될 때마다 for loop의 중첩을 변경해야 하므로 dynamic 하게 r개를 선택하는 용도로 사용하기 어렵다.
이런 경우, 재귀함수를 사용해서 r에 대응할 수 있게 순열을 구할 수 있다.
let stringArray: [String] = ["A", "B", "C", "D"]
var permutaionArray: [[String]] = [] //찾은 순열을 저장할 배열
var numberOfPick: Int = 2 //몇개로 구성된 순열을 찾을지
func permutaionWithRecursion(array: [String], pickCount: Int, permutationArray: inout [[String]], index: Int = 0) {
if index == pickCount {
permutationArray.append(Array(array[0..<index]))
return
}
var arr = array
for i in index..<arr.count {
arr.swapAt(index, i)
permutaionWithRecursion(array: arr, pickCount: pickCount, permutationArray: &permutationArray, index: index + 1)
arr.swapAt(index, i)
}
}
permutaionWithRecursion(array: stringArray, pickCount: numberOfPick, permutationArray: &permutaionArray)
print("4개의 값에서 2개를 고르는 순열의 수: \(permutaionArray.count)개") //12개
print(permutaionArray)
/*
[["A", "B"], ["A", "C"], ["A", "D"],
["B", "A"], ["B", "C"], ["B", "D"],
["C", "B"], ["C", "A"], ["C", "D"],
["D", "B"], ["D", "C"], ["D", "A"]]
*/위 알고리즘의 동작방식은 다음과 같다.
1. permutaionWithRecursive 함수에서는 순열을 수행할 배열, 선택할 개수, 찾은 순열을 저장할 배열, 인덱스(default = 0)를 파라미터로 받는다.
* 이때 찾은 순열을 저장할 배열은 파라미터로 전달되지만 값의 변화를 저장시키기 위해 inout을 사용해서 넘깁니다.
2. for loop를 돌며 i번째 원소와 index번째 원소를 swap 후 재귀 호출한다.
3. 호출 이후 기존 배열의 원소 배열이 달라졌으므로 다시 원상태로 되돌린다.
4. index == pickCount, 즉 선택할 개수만큼 재귀 호출되었을 경우 pickCount만큼 원소를 확정하였다는 의미이므로 permutaionArray에 값을 추가한 후 함수를 종료한다.
예를 들어 ["A", "B", "C", "D"] 배열이 넘어왔을 때
index 번째 원소인 A를 다른 i번째 원소와 스왑하고 재귀 호출한다.
index와 numberOfPick이 같아질 때까지 for loop를 돌며 index번째 원소와 i번째 원소를 바꾼 뒤 재귀 호출한다.
index와 numberOfPick이 같아지면 0번째부터 index번째까지의 원소를 찾은 순열을 저장할 배열에 append 시킨다.
2. 조합 (Combination)
'서로 다른 n 개의 원소 중에서 r 개를 골라 순서를 구분하지 않고 나열한 경우의 수'를 의미한다.
조합은 nCr 로 표현한다.
조합의 개수를 구하는 공식은 n! / r!(n-r)! 이다.
조합에서 중요한 점은 순서를 구분하지 않는다는 점이다.
예를 들어 [1, 2, 3, 4]의 배열에서 순서를 구분하지않고 3가지 원소를 경우의 수를 나열하면 아래와 같이 4개의 경우의 수가 나온다.
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
순열과 마찬가지로 for loop를 r번 중첩하여 구현한 조합의 개수를 찾는 알고리즘은 다음과 같다.
let numberArray: [Int] = [1, 2, 3, 4]
func combinationWithForLoop(array: [Int]) -> [[Int]] {
var combinationArray: [[Int]] = []
for i in 0..<array.count {
for j in (i+1)..<array.count {
for k in (j+1)..<array.count {
combinationArray.append([array[i], array[j], array[k]])
}
}
}
return combinationArray
}
print("4개의 값에서 3개를 고르는 조합의 수 : \(combinationWithForLoop(array: numberArray).count)")
print(combinationWithForLoop(array: numberArray))
/*
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
*/순열과 다른점은 for loop를 중첩시킬 때 반복문을 0에서 시작하는 것이 아닌 이전 for loop의 index + 1 에서 시작하는 점이다.
이미 이전 루프에서 뽑혀진 index는 더 이상 고려대상이 아니므로 index 이후의 경우만 생각하면 된다.
for loop를 사용할 경우 순열에서 for loop를 사용했을 때 문제점과 마찬가지로 dynamic하게 변하는 r에 대응할 수 없다는 문제점이 있다.
순열과 마찬가지로 재귀함수를 사용해서 r에 대응할 수 있게 조합을 구할 수 있다.
let intArray: [Int] = [1, 2, 3, 4]
var combinationArray: [[Int]] = []
let numberOfPick: Int = 2
func combinationWithRecursion(array: [Int], pickCount: Int, index: Int = 0, tempArray: [Int], combsArray: inout [[Int]]) -> [[Int]] {
if tempArray.count == pickCount {
combsArray.append(tempArray)
return []
}
for i in index..<array.count {
combinationWithRecursion(array: array, pickCount: pickCount, index: i + 1, tempArray: tempArray + [array[i]], combsArray: &combsArray)
}
return combsArray
}
combinationWithRecursion(array: intArray, pickCount: numberOfPick, tempArray: [], combsArray: &combinationArray)
print("4개의 값에서 2개를 고르는 조합의 수: \(combinationArray.count)개") //6개
print(combinationArray)
/*
[[1, 2], [1, 3], [1, 4],
[2, 3], [2, 4],
[3, 4]]
*/위 알고리즘의 동작방식은 다음과 같다.
1. combinationWithRecursion 함수에서는 조합을 수행할 배열, 선택할 개수, 인덱스(default = 0), 임시로 조합을 저장할 배열, 찾은 조합을 저장할 배열을 파라미터로 받는다.
* 이때 찾은 조합을 저장할 배열은 파라미터로 전달되지만 값의 변화를 저장시키기 위해 inout을 사용해서 넘깁니다.
2. index부터 for loop 를 돌며 조합을 탐색한다.
* 순열과 달리 순서를 구분하지 않기 때문에 한번 사용된 조합은 다시 사용되지 않으므로 다시 방문하지 않기 위해 재귀 호출 시 index +1 을 넣어준다.
3. tempArray.count == pickCount, 즉 선택할 개수만큼 재귀 호출되었을 경우 pickCount만큼 원소를 확정하였다는 의미이므로 체combinationArray에 값을 추가한 후 함수를 종료한다.
예를 들어, [1, 2, 3, 4] 배열이 넘어왔을 때
index 번째 부터 for loop를 돌며 재귀 호출한다.
루프를 돌며 루프마다 각 1, 2, 3, 4의 원소값이 tempArray에 append 된다.
index와 pickCount가 같아질 때까지 index에 i +1 을 넣어주면서 targetArray의 count (위의 경우에는 4) 번째 까지 for loop를 돌며 재귀호출하고, tempArray에 값을 append 한다.
tempArray의 count와 pickCount가 같아지면 tempArray 찾은 조합을 저장할 배열에 append 시킨다.
'iOS > 알고리즘' 카테고리의 다른 글
| [Swift : 알고리즘] 선택정렬(Selection Sort) (0) | 2020.09.03 |
|---|