[Algorithm] 순열&조합 JAVA로 구현

코딩 테스트 준비를 하다 순열, 조합 문제가 꽤 나와서
헷갈리지 않게 정리해보려고 한다.

조합

조합은 말 그대로 n개 중 r개의 조합을 말한다. 따라서 순서가 있어선 안 된다.

조합은 순열과 다르게 순서가 있어서는 안 되기 때문에 이를 위한 장치가 중요하다.

먼저 코드를 보자.

package AlgorithmNote.NumberTheory;
import java.util.*;

public class Combination {
    public static void combination(int[] arr,int[]output,boolean[] visited, int start,int n,int r){
        if(r==0){
            System.out.println(Arrays.toString(output));
            return;
        }
        for(int i=start;i<n;i++){
            visited[i]=true;
            output[r-1]=arr[i];
            combination(arr,output,visited,i+1,n,r-1);
            visited[i]=false;
        }
    }
    public static void main(String[] args){
        int[] nums=new int[]{1,2,3};
        int r=3;
        combination(nums,new int[r],new boolean[nums.length],0,nums.length,r);
    }
}

//실행 결과
[2, 1]
[3, 1]
[3, 2]

• arr : n개의 수를 담은 배열이다.
• output : 없어도 되지만 조합의 결과를 담을 output 함수이다.
  • 길이는 r과 같아야 한다.
• visited : 중복을 막기 위한 boolean 배열이다.
  • 길이는 n과 같아야 한다.
• start : 이것이 바로 순서를 없애주는 장치이다.
• n : arr 배열의 크기이다.
• r : n개 중 선택할 조합 원소의 개수이다.

이 과정을 보여줄 그림은 아래와 같다.

start라는 정수는 배열 중 방문한 원소의 인덱스를 말하며,

for 문 내부에서 r의 크기를 감소시키며 combination() 메소드를 재귀적으로 호출할 때, 

start+1을 해줌으로써 다음 for 문에서 start+1부터 시작하게 한다.

 

결과적으로 start는 방문한 원소를 다시 방문하지 못하게 함으로써 순서를 없애주는 역할을 하는 것이다.

순열

순열은 조합과는 다르게 n개 중 r개의 순열을 뽑는다. 따라서 순서가 있어야 한다.

순열은 순서가 있어야 하기 때문에 위의 start같은 장치가 없어도 된다.

코드를 먼저 보자.

package AlgorithmNote.NumberTheory;
import java.util.*;
public class Permutation {
    public static void permutation(int[] arr,int[] out,boolean[] visited, int depth, int r){
        if(depth==r){
            System.out.println(Arrays.toString(out));
            return;
        }
        for(int i=0;i<arr.length;i++){
            if(!visited[i]){
                visited[i]=true;
                out[depth]=arr[i];
                permutation(arr,out,visited,depth+1,r);
                visited[i]=false;
            }
        }
    }

    public static void main(String[] args){
        int[] arr={1,2,3};
        int r=2;
        permutation(arr,new int[r],new boolean[arr.length],0,r);
    }
}

//실행 결과
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

위 조합과 다른 depth만 살펴보자.

• depth : 깊이를 말하며 순열 결과 배열(out)에 몇 번째 원소까지 담았는지 알려준다.

그림처럼 순열은 start를 따로 지정해주지 않았기 때문에

방문했던 1과 2가 out 배열에 담길 수 있는 것을 볼 수 있다.

마무리

정리하면서 백트래킹과 재귀에 대해서도 자세하게 공부해야 함을 느꼈다.

 

잘못된 정보에 대한 피드백은 환영입니다. 감사합니다.