조합과 순열 구현해보기

순열

순열은 영어로 Permutation 이라고 한다.

nPr : n개 중에서 r개를 뽑아서 나열하는 경우의 수 이다.

{1, 2, 3}을 순열로 나타낼 때, 2 1 3 과 1 2 3 은 다른 표현이다. 

 

조합 

조합은 영어로 Combitation 이라고 한다.

nCr : n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수이다.

즉 { 1 ,2 , 3} 에서 2개를 뽑을 때, {1, 2} 와 {2, 1}은 하나라고 친다. 

그러므로 경우의 수는 {1, 2 }, {1, 3}, {2, 3} 3개 이다.

---

순열과 조합 구현해보기

순열 구현해보기

순열은 재귀를 사용해 간단하게 구현할 수 있다. 

• visited 배열을 사용하여 방문한것은 true로 한다.
• output 배열을 하나 만들어 depth에 따라 현재 방문한 숫자를 집어 넣는다.
• depth가 선택해야 하는 수 r 과 같아지면 print한다.

static void perm(int depth, int r){
    if(depth == r){
        for (int i = 0; i < r; i++) {
            System.out.print(output[i] + " ");
        }
        System.out.println();
    }
    for (int i = 0; i < arr.length; i++) {
        if(visited[i] != true){
            visited[i]=true;
            output[depth] = arr[i];
            perm(depth+1,r);
            visited[i]=false;
        }
    }
}

이러면 r 에 몇개를 뽑으라는 것에 맞춰 순열이 출력 된다. 

 

조합 구현해보기

1. 백트래킹을 이용하여 구현하기

• visited 배열을 사용한다.
• 방문한 곳은 true로 하고 뽑아야하는 수를 하나씩 줄인다.
• 출력을 한 수는 visited를 false로 둔다.

static void comb1(int start, int r){
    if(r == 0){
        for (int i = 0; i < visited.length ; i++) {
            if(visited[i]) temp.add(i+1);
        }
        //여기서 다른 메소드를 실행 temp에 있는 것이 선택 된 것
        for (int i = 0; i < temp.size() ; i++) {
            System.out.print(temp.get(i) + " ");
        }
        System.out.println();
        temp.clear();
        return;
    } else{
        for (int i = start; i < arr.length; i++) {
            visited[i] = true;
            comb1(i+1,r-1);
            visited[i] = false;
        }
    }
}

temp라는 ArrayList를 만든 이유는 백준에서 조합을 이용해 푼 문제들은 조합 자체가 필요한 것 이 아니라 지금 1번 2번을 선택했다는 것을 알기 위해 사용하는 경우가 많았다. 그래서 그 경우일 때 다른 메소드를 돌려야 하므로 ArrayList를 만들었다.

 

2. 재귀를 이용하여 구현

• 재귀는 depth를 이용하여 구현한다.
• depth를 하나 씩 증가하고 뽑는 것은 하나씩 감소 시키면서 진행한다.

static void comb2(int depth, int r){
    if(r == 0){
        for (int i = 0; i < visited.length ; i++) {
            if(visited[i]) temp.add(i+1);
        }
        for (int i = 0; i < temp.size() ; i++) {
            System.out.print(temp.get(i) + " ");
        }
        System.out.println();
        temp.clear();
        return;
    }
    if(depth == arr.length) return;
    else{
        visited[depth] = true;
        comb2(depth+1, r-1);

        visited[depth] = false;
        comb2(depth+1, r);
    }
}

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/59f470ab4874bef82e27a1f8767631a149adc422?diff=unified 

조합_순열 · Heron-Woong/CodingTest_Practice@59f470a