순열과 조합

안녕하세요 KataRN입니다.

 

묻지도 따지지도 않고 순열과 조합이 필요한 경우가 있습니다.

그래서 오늘은 순열과 조합에 대해 알아보려고 합니다.

 

맴찢...ㅠ.gif

들리는 소문에 의하면 파이썬은 기본제공이 있다던데...

swift는? 네네 없습니다...

또 서론이 길다구요? 네 코드보시죠

 

우선 순열입니다.

func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()
    var visited = [Bool](repeating: false, count: nums.count)
    
    func permutation(_ nowPermute: [Int]) {
        if nowPermute.count == targetNum {
            result.append(nowPermute)
            return
        }
        for i in 0..<nums.count {
            if visited[i] == true {
                continue
            }
            else {
                visited[i] = true
                permutation(nowPermute + [nums[i]])
                visited[i] = false
            }
        }
    }
    permutation([])
    
    return result
}

그리고 조합입니다.

func combi(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
    var result = [[Int]]()

    func combination(_ index: Int, _ nowCombi: [Int]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi)
            return
        }
        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }

    combination(0, [])

    return result
}

번외로 조합의 개수만 구하는 방법입니다.

func combination(_ total: Int, _ shouldSelect: Int) -> Int {
    if total == shouldSelect || shouldSelect == 0 {
        return 1
    } else {
        return combination(total-1, shouldSelect) + combination(total-1, shouldSelect-1)
    }
}

 

 

사실 제가 직접 만들면서 설명을 하려고 했으나...

저는 순열과 조합에 대한 이야기보다 재귀함수에 대한 이야기가 더 하고싶었습니다.

위의 함수들을 만들기 위해서는 재귀함수에 대한 이해가 필요합니다.

조만간 재귀함수, 꼬리함수 dfs, bfs 등을 소개하는 글을 올리도록 하겠습니다.

 

감사합니다.

 

<추가 내용> : 문제를 풀때 조합을 썼을때 시간초과가 나는 분들 계신가요?(TMI)

만약 조합이 문제였다면 그럴때는 조합자체가 적게 나오도록 해야합니다.

 

예를들어 보겠습니다.

질문 : ["abcd", "ab", "abd", "abc", "ae", "af", "aef", "adb"] 7개의 문자로 각각 2개의 글자를 만들었을때 가장 많이 나오는 2글자는?(먼말이지...)

질문설명 : abcd-> 에서 나오는 2글자 문자들, ab -> ...  을 각각 구한 다음 각각의 글자들 중 가장 많이 나온 2글자가 뭐니? 라는 질문입니다...

 (문제에 따라 다를 수 있습니다.)

 

func combi(_ nums: [String], _ targetNum: Int) -> [[String]] {
    var result = [[String]]()

    func combination(_ index: Int, _ nowCombi: [String]) {
        if nowCombi.count == targetNum {
            result.append(nowCombi.sorted())
            return
        }
        for i in index..<nums.count {
            combination(i + 1, nowCombi + [nums[i]])
        }
    }

    combination(0, [])

    return result
}

(숫자말고 문자 넣을 경우로 바꿔봄, 위랑 같은 함수임)

 

위의 함수를 이용하면 쉽게 구할 수 있습니다.

다만 위의 함수에 넣는 배열을 넣다보면 보통 2가지로 나뉩니다.

첫번째는 위의 문자들을 전부 합쳐서 중복을 제거 한 1개의 배열을 조합함수에 넣는법.

두번째는 각각의 문자들을 조합함수로 구하고 묶어서 중복을 제거하는 방법

 

순서의 차이인데 저는 첫번째가 더 쉬워서? 익숙해서? 첫번째를 쓰게 되더라구요...

(문제를 간단하게 썼는데 보통 더 복잡해서... 암튼 그래요...)

 

무튼!

 

첫번째의 경우의 수는 15개

["bf", "cf", "ef", "ce", "de", "af", "cd", "ac", "ae", "bd", "ad", "ab", "bc", "be", "df"]

두번째 경우의 수는 9개

["bd", "ae", "ef", "af", "ab", "ac", "ad", "cd", "bc"]

 

첫번째의 경우는 비교할 필요 없는 2글자들이 포함되어 버려서 비효율적이게 됩니다.

지금 6개 차이가는데 문제가 복잡해질수록 차이가 더 나겠죠?

 

이런 경우를 조심합시다.

이상 TMI였습니다.

 

 

 

 

출처 : https://woongsios.tistory.com/179

출처 : https://developer-p.tistory.com/145