순열과 조합

백준 문제를 풀면서 stl을 사용하지 않고, 재귀적 방법으로 순열과 조합을 구현해서 문제를 풀어야하는 경우가 많았기에 정리해서 올려본다.

순열

• 개념 : 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것 (nPr)
• 예시 : 

[1, 2, 3, 4, 5] 5개의 원소 중에서 3개를 고르시요.

답)

맨 앞자리가 1일 경우 : [1,2,3], [1,2,4], [1,2,5], [1,3,2], [1,3,4], [1,3,5], [1,4,2], [1,4,3], [1,4,5], [1,5,2], [1,5,3], [1,5,4]

맨 앞자리가 2일 경우 : [2,1,3], [2,1,4], [2,1,5], [2,3,1], [2,3,4], [2,3,5], [2,4,1], [2,4,3], [2,4,5], [2,5,1], [2,5,3], [2,5,4]

... 이런식으로 많은 경우의 수가 나올수 있다. 

• 소스 코드 구현

위에서 예시로 든 5개중에서 3개를 고르는 코드를 구현하자면

#include <stdio.h>
#include <vector>
using namespace std;
 
bool visited[6]; //이미 고른 숫자를 제외해주는 배열
vector <int> temp; //3개를 잘 골랐나 출력해주는 함수
 
//cnt - 몇개까지 골랐는지 알려주는 변수 = dfs함수의 depth
void dfs(int cnt) {
    if (cnt == 3) {
        for (int i = 0; i < 3; i++) {
            printf("%d ", temp[i]);
        }
        printf("\n");
        return; // return을 해줘야 3개를 이미 고른 상태에서 끝남
    }
    for (int i = 1; i <= 5; i++) { // 시작원소가 2라도 1을 봐야하므로 for문을 1부터 시작한다.
        if (visited[i] == true) continue; 
        
        //이전에 고르지 않았다면
        visited[i] = true; //골랐음을 표시
        temp.push_back(i);
        dfs(cnt + 1); //다른 원소를 뽑기 위해 다시 dfs호출
 
        //dfs갔다와서
        temp.pop_back();
        visited[i] = false;
    }
}
 
int main(void)
{
    dfs(0);
}

---

조합

• 개념 : 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것 (nCr)
• 예시 : 

[1, 2, 3, 4, 5] 5개의 원소 중에서 3개를 뽑으시오.

답) [1,2,3], [1,2,4], [1,2,5], [2,3,4], [2,3,5], [3,4,5] 

→ 규칙을 생각해보면, 시작원소가 1일때 모든원소를 보지만, 시작 원소가 2일때는 1을 제외하고 보고, 

   시작 원소가 3일때는 1, 2를 제외하고 본다.

• 소스 코드 구현

위에서 예시로 든 5개중에 3개를 뽑는 코드를 구현하자면

#include <stdio.h>
#include <vector>
using namespace std;
 
bool visited[6]; //이미 고른 숫자를 제외해주는 배열
vector <int> temp; //3개를 잘 골랐나 출력해주는 함수
 
//idx - 시작 원소를 알려주는 변수, cnt - 몇개까지 골랐는지 알려주는 변수 = dfs함수의 depth
void dfs(int idx, int cnt) {
    if (cnt == 3) {
        for (int i = 0; i < 3; i++) {
            printf("%d ", temp[i]);
        }
        printf("\n");
        return; // return을 해줘야 3개를 이미 고른 상태에서 끝남
    }
    for (int i = idx; i <= 5; i++) {
        if (visited[i] == true) continue; //이미 이전에 고른 원소라면, 넘어감
        
        //이전에 고르지 않았다면
        visited[i] = true; //골랐음을 표시
        temp.push_back(i);
        dfs(i, cnt + 1); //다른 원소를 뽑기 위해 다시 dfs호출
 
        //dfs갔다와서
        temp.pop_back();
        visited[i] = false;
    }
}
 
int main(void)
{
    dfs(1, 0);
}
 

결과값 -  으로 잘 나오는 것을 확인할 수 있다.

만일, 중복순열과 중복조합을 만들고 싶다면

이미 사용했던 원소도 다시 사용할 수 있으므로, visited[]함수를 제외하고 코드를 작성하면 된다.