[Algorithm] 순열, 조합

조합

모든 경우의 수를 표현하기 위해 자주 사용되는 또다른 전략 중 하나는 조합이다.

조합으로는 어떤 상황이 놓였을 때 선택에 대한 경우의 수를 표현할 수 있다.

예를 들어 다음과 같은 회사 목록이 있다고 가정해보자.

    vector<string> company = { "Apple", "Google", "Amazon", "Facebook" };

 

N개의 원소에서 K개를 고르는 조합

이 회사 목록에서 3개의 회사를 선택하는 모든 경우의 수를 생각해보자.

다음과 같은 선택지들이 있을 것이다. 

"Apple", "Google", "Amazon", 
"Apple", "Google", "Facebook"
"Apple", "Amazon", "Facebook"
"Google", "Amazon", "Facebook"

이처럼 어떤 N개의 원소들 중에서 K개의 선택을 한 선택지 리스트를 만들고,

각각의 선택지에 대해 문제에서 요구하는 조건을 만족하는 선택지들을 찾는 형태의 문제는 완전탐색 문제에서 굉장히 자주 등장한다.

 

N개의 원소에서 모든 K에 대한 조합 (모든 부분집합)

회사 목록에서 정해진 개수의 대한 조합이 아닌, 가능한 모든 K에 대한 조합도 생각해볼 수 있다.

이는 N개의 원소에 대한 모든 부분집합과 같은 의미이다.

다음과 같은 선택지들이 있을 것이다.

"Apple"
"Google"
"Amazon"
"Facebook"
"Apple", "Google"
"Apple", "Amazon"
"Apple", "Facebook"
"Google", "Amazon"
"Google", "Facebook"
"Amazon", "Facebook"
"Apple", "Google", "Amazon", 
"Apple", "Google", "Facebook"
"Apple", "Amazon", "Facebook"
"Google", "Amazon", "Facebook"
"Apple", "Google", "Amazon", "Facebook"

위에서 언급한 N개의 원소에서 K개를 고르는 조합을 C(N, K)라고 했을 때,

모든 부분집합은 다음과 같이 표현할 수 있다.

All = C(N, 0) + C(N, 1) + C(N, 2) +...+ C(N, N)

즉 아무것도 선택하지 않는 경우부터 (K = 0)

모든 원소를 다 선택하는 경우까지 (K = N)

모두 나열했다고 볼 수 있다.

이런 모든 부분집합을 표현하는 문제는 N개의 원소에서 K개의 원소를 고르는 조합보다 훨씬 더 빈번하게 문제에서 등장하기 때문에, 반드시 알고 가야 할 것이다.

 

참고로, 모든 부분집합에 대한 표현은 bitmask를 이용하면 조합보다 훨씬 더 간결하게 표현할 수 있다.

 

재귀를 이용한 조합 구현

1부터 4까지의 숫자들 중 2개를 선택하는 조합을 재귀함수를 이용하여 구현한다고 생각해보자.

 

 

4개 중 2개를 선택하는 문제는,

1을 선택하고 1보다 큰 숫자들 중에서 1개를 선택하는 경우,

2를 선택하고 2보다 큰 숫자들 중에서 1개를 선택하는 경우,

3을 선택하고 3보다 큰 숫자들 중에서 1개를 선택하는 경우,

4를 선택하고 4보다 큰 숫자들 중에서 1개를 선택하는 경우로 나눌 수 있다.

 

C(N, K): 
    1 선택 -> C(N, K - 1)
    2 선택 -> C(N, K - 1)
    ...
    N 선택 -> C(N, K - 1)

 

여기서 C라는 재귀함수가 이전 단계에서 마지막으로 선택한 값보다 큰 값부터 선택하도록 현재 선택된 조합을 배열로 넘겨준다면 다음과 같이 작성할 수 있을 것이다.

그리고 k가 0인 경우 더 이상 선택할 수 없으므로 기저조건으로 추가한다.

C(N, K, combs):
    if(k == 0):
        return
        
    start = combs에서 마지막으로 선택한 숫자 + 1

    for(i : start ~ N):
        i 선택
        C(N, K - 1, combs)
        i 선택 취소

 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BruteForce/2-Combination.cpp

insooneelife/AlgorithmTutorial

 

순열

모든 경우의 수를 표현하기 위해 자주 사용되는 또다른 전략 중 하나는 순열이다.

순열로는 어떤 상황이 놓였을 때 순서에 대한 모든 경우의 수를 표현할 수 있다. 

예를 들어 다음과 같은 행동 집합이 있다고 가정해보자.

vector<string> action = { "Attack", "Move", "Jump" };

공격, 왼쪽이동, 오른쪽이동 세 가지 선택지가 있다.

각 행동들을 서로 다른 순서로 선택하게 되었을 때의 결과는 서로 다를 것이다.

그러므로 이러한 데이터는 순서에 대해 의존적인 데이터라고 생각할 수 있고,

완전탐색으로서 순열을 활용하기에 적합한 상황이라고 볼 수 있다.

 

 

N개의 원소에 대한 팩토리얼 순열 (nPn)

세 가지 행동들을 순서대로 나열하는 경우의 수를 나열해보면 다음과 같다.

"Attack", "Move", "Jump"
"Attack", "Jump", "Move"
"Move", "Attack", "Jump"
"Move", "Jump", "Attack"
"Jump", "Attack", "Move"
"Jump", "Move", "Attack"

 

N개의 원소에 대한 K개의 순열 (nPk)

세 가지 행동들에 대해 두 가지를 순서대로 고르는 경우의 소를 나열해보면 다음과 같다.

"Attack", "Move"
"Attack", "Jump"
"Move", "Attack"
"Move", "Jump"
"Jump", "Attack"
"Jump", "Move"

 

N개의 원소에 대한 K개의 순열 중 중복 데이터가 있는 순열

"Attack", "Attack", "Move", "Jump"
"Attack", "Attack", "Jump", "Move"
"Attack", "Move", "Attack", "Jump"
"Attack", "Move", "Jump", "Attack"
"Attack", "Jump", "Attack", "Move"
"Attack", "Jump", "Move", "Attack"
"Move", "Attack", "Attack", "Jump"
"Move", "Attack", "Jump", "Attack"
"Move", "Jump", "Attack", "Attack"
"Jump", "Attack", "Attack", "Move"
"Jump", "Attack", "Move", "Attack"
"Jump", "Move", "Attack", "Attack"

 

조합과 마찬가지로 순열 또한 알고리즘 문제에서 약방의 감초처럼 등장하는 개념이다.

그 중에서도, 조합과 달리 순열의 경우는 순서에 의존성이 있는 데이터를 활용하는 상황에 많이 이용된다.

일반적으로 어떤 행동 집합이 있고, 그 행동들의 순서가 바뀌게 될 수 있는 상황에 자주 사용된다.

물론 행동이 아니어도 데이터 간, 순서가 의미가 있다면 충분히 순열이 활용될 수 있다.

 

재귀를 이용한 순열 구현

1부터 3까지의 숫자들을 순서대로 나열하는 모든 경우를 재귀로 구현해보자.

3개의 숫자를 순서대로 나열하는 것은,

1을 나열하고 나머지 2개의 숫자를 순서대로 나열하는 경우,

2를 나열하고 나머지 2개의 숫자를 순서대로 나열하는 경우,

3을 나열하고 나머지 2개의 숫자를 순서대로 나열하는 경우로 나누어진다.

P(N): 
    1 선택 -> P(N)
    2 선택 -> P(N)
    ...
    N 선택 -> P(N)

 

여기서 다음 P(N)으로 넘어갈 때 현재 어떤 숫자들을 나열하였는지도 추가로 넘겨줘야 할 것이다.

그리고 이미 나열한 숫자들의 개수가 N개가 된다면 더 이상 나열할 숫자가 없으므로 이 조건을 기저조건으로 준다.

P(N, perms, selected):
    if(perms.size == 0):
        return

    for(i : 1 ~ N):
        selected에 방문 기록
        perms에 i 추가
        P(N, perms, combs)
        selected에 방문 기록 제거
        perms에서 i 제거

 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BruteForce/3-Permutation.cpp

insooneelife/AlgorithmTutorial