순열 과 중복 순열 만들기 (with swift)

안녕하세요. 

오늘은 조금 이론적인 이야기를 해볼까 합니다. 

2023.08.18 - [iOS개발/프로그래머스 연습] - 프로그래머스 이모티콘 할인행사 (Lv.2) 문제 풀이

프로그래머스 이모티콘 할인행사 (Lv.2) 문제 풀이

이전에 풀었던 문제에 나왔던 부분인 

순열에 관해 이야기 할까 합니다. 

 

* 순열

- 서로 다른 원소들(n개) 중에서 몇개(r개)를 중복없이 순서에 상관있게 나열하는 것을 의미합니다.

- 나열 가능한 경우의 수는 n​Pr 로 나타냅니다. (수학 시간에 보신 분들도 계실껍니다.)

- ex) 서로 다른 숫자카드 5개 중 3개를 골라​ 순서대로 나열할때 가능한 경우의 수를 모두 구하시오.

 

* 중복 순열

- 기존 순열과 달리 중복을 허용한 순열 (순서는 상관있습니다.)

 

* 근데 갑자기 순열은 왜 구하나요? 

- 사실 경우의 수를 구하는 알고리즘에서는 심심하면 등장하시는 개념이기 때문에 알아두면 편해요

- 처음 하시는 분들이 보면 복잡해보이지만 원리만 알면 쉽게 할 수 있어요.

 

이번 포스트에는 기본 순열과 중복 순열 두가지를 다루겠습니다. 

 

기본 순열을 알면 중복 순열은 쉬우니까

기본 순열부터 해볼께요. 

 

천천히 생각해봅시다. 

A,B,C,D라는 카드가 있을때 1개를 뽑아 나열하려면 어떻게 해야할까요? 

이런식으로요

이걸 코드로 작성한다고 합시다. 아래처럼 카드들을 미리 만들어 둡시다. 

let cards = ["A","B","C","D"]

만약 한개라면 그냥 저 상태 그대로 출력하는게 맞겠죠? 

예를 들면 아래처럼요 (함수 전체는 나중에 보여드릴께요)

if(level == 1){ // 1개 뽑기라면
    var results : [[String]] = []
    for i in cards{
        results.append([i])
    }
    return results // 결과 [["A"], ["B"], ["C"], ["D"]]
}

그럼 이제 2개를 뽑을때로 넘어가 봅시다. 

중복되는거는 사용하면 안된다고 했죠? 

그럼 어떻게 나열해야 할까요? 

 

그림으로 보면 아래 처럼 표현 할 수 있어요

2개 뽑기 모든 경우의 수

그럼 기존에 만든 배열 앞에 카드를 하나 넣어준다고 생각하면 

이미 사용한 카드이면 패스하고 없는 카드이면 넣어서 배열을 만들면 되지 않을까요? 

아래처럼요

var results : [[String]] = []
for i in cards {
    for lastArr in [["A"], ["B"], ["C"], ["D"]] {// 1개짜리 배열(이전 단계 결과값)
        if(!lastArr.contains(i)){ // 이전에 사용된 카드는 사용X
            var newElement = lastArr
            newElement.append(i)
            results.append(newElement)
        }
    }
}
print(results)
// 실제 출력 값 
// [["B", "A"], ["C", "A"], ["D", "A"], ["A", "B"], ["C", "B"], ["D", "B"], ["A", "C"], ["B", "C"], ["D", "C"], ["A", "D"], ["B", "D"], ["C", "D"]]

근데 저희가 항상 이걸 매번 수동으로 r개 뽑을때마다 계속 함수를 새로 만드는건 힘들겠죠?

r 개를 뽑으면 비슷한 구조의 함수를 r번 반복 => 이럴때는 재귀함수 만큼 좋은게 없죠 

 

* 재귀함수 

- 함수 안에 자기자신을 재참조하는 식으로 재정의한 함수

- 쉽게 말하면 함수안에 함수(그것도 본인)가 있는 구조라 생각하시면 됩니다.

 

단 r = 1 인 1개 뽑기일 때 바로 저희가 아는 값이 나오는 편이 좋겠죠? 

또 재귀인 만큼 지금 만든 배열이 몇자리(level)이고 저희의 목표 자릿수(r)를 알아야겠죠?

(level 은 쉽게 생각하면 진행 상황을 의미한다고 생각하면 됩니다.)

 

즉 저희가 함수를 처음 이용할때는 level 과 r을 동일한 값을 넣어주지만

실제 반복를 돌리기 위해 둘로 나누어 넣는다고 생각하시면 됩니다. 

(r은 count 로 바꾸어서 넣겠습니다 - 헷갈림 방지)

# 순열 코드 (swift)

let cards = ["A","B","C","D"]

func permutation(count : Int, level : Int) -> [[String]] {
    if(level == 1){
        var results : [[String]] = []
        for i in cards{
            results.append([i])
        }
        return results
    }else{
        var results : [[String]] = []
        for i in cards {
            for lastArr in permutation(count: count, level: level-1) { // 이전 값 가져오기
                if(!lastArr.contains(i)){
                    var newElement = lastArr
                    newElement.append(i)
                    results.append(newElement)
                }
            }
        }
        return results
    }
}

이러면 정상적으로 배열이 나오는걸 확인할 수 있습니다.

 

* 그럼 중복 순열은 어떻게 하나요? 

- 저기 중복을 방지하기위해 넣은 조건문만 제거하면 바로 가능합니다.  

 

# 중복 순열 코드 (swift)

func permutation(count : Int, level : Int) -> [[String]] {
        if(level == 1){
            var results : [[String]] = []
            for i in cards{
                results.append([i])
            }
            return results
        }else{
            var results : [[String]] = []
            for i in cards {
                for lastArr in permutation(count: count, level: level-1) {
                    //if(!lastArr.contains(i)){ 비교문 제거
                        var newElement = lastArr
                        newElement.append(i)
                        results.append(newElement)
                    //}
                }
            }
            return results
        }
    }

간단하죠? 

 

재귀함수의 경우 처음부터 너무 어렵게 생각하는 것보다는

단순하게 생각하는 편이 확실히 편한 것 같네요.

 

공부하시는 분들에게 조금이나마 도움이 되었으면 좋겠네요. 

오늘도 파이팅입니다.