[알고리즘] 03. 순열과 조합, 그리고 재귀 with Swift

알고리즘 스터디하면서 재귀에 대해 잘 이해하고 쓰지 못했던 경험이 있다. 

피보나치나 팩토리얼 문제 정도는 괜찮은데, 이해도가 조금 부족했어서 그 이상은 체화되지 않아, 쉽게 재귀를 떠올려 사용하지 못했었다.

 

이번에 코테를 준비하면서, 여러 문제를 풀기보단 부족했던 기본 개념에 대해 다시 이해하고 넘어가보자!라는 마음으로 순열과 조합을 들여다보았고, 순열과 조합을 알아가면서 재귀에 대해서도 자연스레 체화할 수 있었다-!!!

 

---

순열 (permutation)

순열이란 서로 다른 n개의 원소에서 r개를 중복 없이 순서를 고려하여 선택하거나 나열하는 것을 의미합니다.(단, 0<r≤n일 때)

 

고등학교 수학시간에 배웠던 순열은 수학적으로 보면 다음과 같습니다.

(여기서 n!은 n의 계승(factorial)을 의미하며, 1부터 n까지의 자연수를 모두 곱한 값입니다.)

• nPr : 서로 다른 n개의 원소에서 r개를 선택하는 순열의 수
• nPr = n! / (n-r)!

예를 들어, 5개의 숫자 1, 2, 3, 4, 5에서 3개의 숫자를 선택하여 순서대로 나열하는 경우의 수는 5P3 = 5! / (5-3)! = 120입니다.

 

 

조합 (combination)

조합이란 서로 다른 n개의 원소에서 r개를 선택할 때, 순서를 고려하지 않는 것을 의미합니다.(단, 0<r≤n일 때)

• nCr : 서로 다른 n개의 원소에서 r개를 선택하는 조합의 수
• nCr = n! / (r! * (n-r)!)

예를 들어 5개의 숫자 1, 2, 3, 4, 5에서 3개의 숫자를 선택하는 경우의 수는 5C3 = 5! / (3! * 2!) = 10입니다.

 

 

순열과 조합의 차이

가장 큰 차이는 순서라고 기억하면 될 것 같습니다 💨

 

---

순열의 뼈대

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열  > 순열 - 백준 N과 M(1)

func 순열(_ depth: Int) {
    if 뎁스가 원하는 길이인 M까지 도달했다면
        출력
    else { 아직 마지막까지 도달하지 않았다면
        for 인덱스 0부터 N-1까지 돈다 {
       	    if 만약 방문하지 않았다면 {
                방문처리
                현재순열[뎁스] = 현재 인덱스 + 1 
                순열(뎁스 + 1)
                방문처리 해제
            }
        }
    }
}

 

Swift로는 다음과 같다.

var res = Array(repeating: 0, count: M)

func solution(_ lev: Int) {
    if lev == M {
        print(res.map {String($0)}.joined(separator: " "))
    } else {
        for i in 0..<N {
            if visited[i] == false {
                visited[i] = true
                res[lev] = i+1
                solution(lev + 1)
                visited[i] = false
            }
        }
    }
}

solution(0)

 

 

조합의 뼈대

• 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 - 백준 N과 M(2)
• 고른 수열은 오름차순이어야 한다 > 앞에서 뽑은 수는 뒤에서 뽑지 않는다 > 조합

func 조합(_ depth: Int, _ start: Int) {
    if 뎁스가 M까지 도달했다면 {
        결과배열 출력
    } else {
        인덱스를 start 부터 N-1까지 반복 {
            결과 배열[뎁스] = 인덱스 + 1
            조합(뎁스 + 1, 인덱스 + 1)
        }
    }
}

var res = Array(repeating: 0, count: M)

func solution(_ depth: Int, _ begin: Int) {
    if depth == M {
        print(res.map {String($0)}.joined(separator: " "))
    } else {
        for i in begin..<N {
            res[depth] = i + 1
            solution(depth + 1, i + 1)
        }
    }
}

solution(0, 0)

 

 

 

-

고등학생때 열심히 확률과 통계 공부했던 기억이 나서, 더 쉽게 이해할 수 있었던 거 같다..!

이전까지는 순열 조합 Swift 코드만 생각하고 마주하기 약간 망설여졌는데, 이제는 수학문제 푸는 것처럼 뿌시는 재미가 있다 🌝

지나고 보면 무엇이든 다 이유있는 학습인 것 같다 💪🏼