[JAVA] 순열, 중복순열, 조합, 중복조합 알고리즘
🌱 들어가기 전
Python으로 코딩테스트를 풀 때에는 itertools 라이브러리를 사용해서 순열, 조합을 쉽게 사용할 수 있었는데,
Java에서는 순열, 조합 라이브러리가 없어서 다 구현해야 한다.
Java로 코테를 옮기면서 가장 불편한 점 중 하나이다.. 그래서 Java로 순열, 조합을 구하는 방법을 모두 정리해보려고 한다.
1️⃣ 순열
순서를 고려하여 n개의 값 중에서 r개의 숫자를 뽑는 경우를 말한다.
예를 들어 [1,2,3] 이라는 크기3의 배열에서 순서를 고려해서 2개의 숫자를 뽑는 경우는
3!/1! = 6가지
[1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2]
방법1. SWAP을 이용한 순열(재귀)
swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법이다.
배열의 첫 값부터 순서대로 하나씩 바꾸어 모든 값을 한번씩 swap한다.
`depth`를 기준 인덱스로 하여 `depth`보다 인덱스가 작은 값들은 그대로 고정하고,
`depth`보다 인덱스가 큰 값들만 가지고 다시 swap을 진행한다.
// 순서 없이 n 개중에서 r 개를 뽑는 경우
// 사용 예시: permutation(arr, 0, n, 4);
static void permutation(int[] arr, int depth, int n, int r) {
if (depth == r) {
print(arr, r);
return;
}
for (int i=depth; i<n; i++) {
swap(arr, depth, i);
permutation(arr, depth + 1, n, r);
swap(arr, depth, i);
}
}
static void swap(int[] arr, int depth, int i) {
int temp = arr[depth];
arr[depth] = arr[i];
arr[i] = temp;
}
Result
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
이 방식은 코드는 깔끔하게 나오지만, 순열들의 순서가 보장되지 않는다는 단점이 있다.
예를 들어 3개의 숫자 중 3개의 값을 뽑는 순열을 만들 때
[3, 1, 2]
[3, 2, 1]
위 순서대로 나와야 하는데
[3, 2, 1]
[3, 1, 2]
이렇게 나온다.
⏰ 시간복잡도 : 최악의 경우 O(n!), 평균적으로는 O(nPr)
방법2) DFS알고리즘으로 Visited 배열을 이용한 순열(재귀)
이 방법은 swap을 이용한 방법과 달리 사전식으로 순열을 구현할 수 있다.
| 변수 | 설명 |
| arr | r 개를 뽑기 위한 n 개의 값 |
| output | 뽑힌 r 개의 값 |
| visited | 중복해서 뽑지 않기 위해 체크하는 값 |
위 3개의 변수가 핵심적이다.
DFS를 돌면서 모든 인덱스를 방문하여 `output` 에 값을 넣는다.
이미 들어간 값은 `visited` 값을 `true` 로 바꾸어 중복하여 넣지 않도록 한다.
`depth` 값은 `output` 에 들어간 숫자의 깊이이다.
`depth` 의 값이 `r` 만큼 되면 `output` 에 들어있는 값을 출력한다.
import java.util.Arrays;
public class Permutation {
static int[] arr;
static int[] output;
static boolean[] visited;
static int n, r;
public static void main(String[] args) {
n = 3;
r = 2;
arr = new int[]{1, 2, 3};
output = new int[r];
visited = new boolean[n];
perm(0, n, r);
}
static void perm(int depth, int n, int r) {
if(depth==r) {
System.out.println(Arrays.toString(output));
return;
}
for(int i=0; i<n ;i++) {
if(visited[i]) continue;
visited[i] = true;
output[depth] = arr[i];
perm(depth+1, n, r);
visited[i] = false;
}
}
}
Result
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
⏰ 시간복잡도 : 최악의 경우 O(n!), 평균적으로 O(nPr)
2️⃣ 중복순열
순서를 고려하여 n개의 값 중에서 중복을 허용하여 r개의 숫자를 뽑는 경우를 말한다.
예를 들어 [1,2,3] 이라는 크기3의 배열에서
순서를 고려해서 중복 허용하여 2개의 숫자를 뽑는 경우는 3^2 = 9가지
[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]
방법) 방문처리 필요없이 재귀 이용한 중복순열
import java.util.Arrays;
public class DuplicatedPermutaion {
static int[] arr;
static int[] output;
static int n, r;
public static void main(String[] args) {
n = 3;
r = 2;
arr = new int[]{1, 2, 3};
output = new int[r];
dupPerm(0, n, r);
}
private static void dupPerm(int depth, int n, int r) {
if(depth==r) {
System.out.println(Arrays.toString(output));
return;
}
for(int i=0; i<n; i++) {
output[depth] = arr[i];
dupPerm(depth+1, n, r);
}
}
}
Result
[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]
⏰ 시간복잡도 : O(n^r)
r이 커질 수록 지수적으로 증가하여, 조합이나 순열보다 빠르게 시간복잡도가 증가한다.
3️⃣ 조합
순서를 고려하지 않고 n개의 값 중에서 r개의 숫자를 뽑는 경우를 말한다.
예를 들어 [1,2,3] 이라는 크기3의 배열에서
순서 고려하지 않고 2개의 숫자를 뽑는 경우는 3!/2! = 3가지
[1, 2]
[1, 3]
[2, 3]
방법1) 방문배열X, 반복문과 시작인덱스 start 이용하기
- `combi(0, 0, n, r)` 호출을 시작으로, for 루프를 돌며 `output[depth]`에 원소를 하나씩 채움
- `depth == r`이 되면 조합이 완성되어 출력
- 이후 백트래킹 방식으로 이전 선택을 지우고 새로운 조합을 시도
import java.util.Arrays;
public class Combination {
static int[] arr;
static int[] output;
static int n, r;
public static void main(String[] args) {
n = 3;
r = 2;
arr = new int[]{1, 2, 3};
output = new int[r];
combi(0, 0, n, r);
}
static void combi(int start, int depth, int n, int r) {
if(depth == r) {
System.out.println(Arrays.toString(output));
return;
}
for(int i=start; i<n; i++){
output[depth] = arr[i];
combi(i+1, depth+1, n, r);
}
}
}
Result
[1, 2]
[1, 3]
[2, 3]
방법2) 백트래킹 방식
(사실상 방법1과 동일하지만 필요에 따라 방문배열을 사용하는 코드)
여기서는 재귀를 들어갈수록 뽑아야 하는 개수인 r을 하나씩 줄이고, r이 0이 되면 끝냄
`visited` 배열을 활용해야하는 경우가 있다면 방문배열을 만들어서 사용할 수 있음
import java.util.Arrays;
public class Combination {
static int[] arr;
static int[] output;
static boolean[] visited;
static int n, r;
public static void main(String[] args) {
n = 3;
r = 2;
arr = new int[]{1, 2, 3};
output = new int[r];
visited = new boolean[n];
combi_with_bt(0, 0, n, r);
}
// 사실상 첫번째랑 크게 다르지는 않음
private static void combi_with_bt(int start, int depth, int n, int r) {
if(r==0) {
System.out.println(Arrays.toString(output));
System.out.println(Arrays.toString(visited));
// -> visited를 활용해서 결과 출력
return;
}
for(int i=start; i<n; i++) {
visited[i] = true;
output[depth] = arr[i];
combi_with_bt(i+1, depth+1, n, r-1);
visited[i] = false;
}
}
}
방법3) 방문배열과 재귀를 이용
이전 조합 코드들과는 다르게, 각 원소를 선택할지 여부를 결정하는 방식으로 동작한다.
차이점 및 특징
- 일반적인 조합 코드에서는 for 루프를 사용하여 선택할 원소를 순차적으로 탐색하지만,
이 코드는 각 원소를 “선택할지” 또는 “선택하지 않을지”를 두 가지 경우로 나누어 재귀를 호출한다.
- `count`는 현재까지 선택한 원소의 개수를 의미하며, `depth`는 배열에서 탐색한 인덱스를 나타냅니다.
- 트리 구조의 백트래킹 방식으로 동작하며, 부분 집합을 구하는 방식과 유사
import java.util.Arrays;
public class Combination {
static int[] arr;
static int[] output;
static boolean[] visited;
static int n, r;
public static void main(String[] args) {
n = 3;
r = 2;
arr = new int[]{1, 2, 3};
output = new int[r];
visited = new boolean[n];
combi_with_recursion(0, 0, n, r);
}
// count는 몇 개를 선택했는지를 나타냄
private static void combi_with_recursion(int count, int depth, int n, int r) {
// r개만큼 모두 선택했을 경우 return
if (count == r) {
for(int i=0; i<n; i++) if(visited[i]) System.out.print(arr[i]+" ");
System.out.println();
return;
}
// 배열의 마지막까지 도달했을 경우 return
if (depth == n) return;
// 현재 요소를 선택할 경우
visited[depth] = true;
combi_with_recursion(count+1, depth+1, n, r);
// 현재 요소를 선택하지 않은 경우
visited[depth] = false;
combi_with_recursion(count, depth+1, n, r);
}
}⏰ 시간복잡도 : 최악의 경우 O(2^n), 평균적으로 O(nCr)
방법4) [조합응용 → DP] 시간복잡도를 줄이는 파스칼 삼각형
파스칼의 삼각형(Pascal’s Triangle)과 동적 프로그래밍(DP)을 활용한 조합 계산 방식이다.
즉, DP를 이용해 미리 조합 값을 계산해두고, 빠르게 nCr을 구하는 방식
📌 파스칼의 삼각형
- 모든 행은 1로 시작하고, 1로 끝남
- 각 숫자는 위 양쪽의 숫자를 더한 값이다
- n번째 행의 숫자들의 합은 2^n이다
- 각 행의 숫자들은 해당 행 번호의 조합 = nCr 을 나타낸다
public class PascalTriangleDP {
static int[][] dp;
static int n;
public static void main(String[] args) {
n = 5;
// init
dp = new int[n][n];
for(int i=0; i<n; i++) {
// 각 행의 첫번째와 마지막 값은 항상 1
dp[i][0] = 1;
dp[i][i] = 1;
for(int j=1; j<i; j++)
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}
// 4C2 = 4행 2열 = 6
nCr(4, 2);
}
static void nCr(int n, int r) {
System.out.println(dp[n][r]);
}
}⏰ 시간복잡도
DP 테이블을 채우는 과정 : O(n^2)
조합 연산 : O(1)
장점
∙ nCr(4,2)와 같은 조합 연산이 O(1) 에 수행됨 → 빠른 조회 가능
∙ 재귀 호출 없이 메모이제이션 방식으로 계산하여 중복 연산을 제거
단점
∙ `dp[n][n]` 크기의 이차원 배열을 사용하므로 메모리 사용량이 증가
조합을 빠르게 구하기 위해 DP를 활용하는 최적화된 방법이며, 여러 개의 조합 연산이 필요할 경우 매우 효율적
4️⃣ 중복조합
순서를 고려하지 않고 n개의 값 중에서 중복을 허용해서 r개의 값을 선택하는 경우
예를 들어 [1,2,3] 이라는 크기3의 배열에서
순서 고려하지 않고 중복을 허용해서 2개의 숫자를 뽑는 경우는 3H2 = 4C2 = 6가지
[1, 1]
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 3]
방법) 반복문과 시작 인덱스 start 이용, 다음 재귀 넘어갈 때 인덱스 그대로
조합 코드(반복만 시작인덱스 이용)에서
다음 재귀로 넘어갈때 `시작 인덱스` +1을 하지 않고 그대로 넘긴다.
이렇게 함으로써 다음 재귀동작에서 이미 선택한 요소더라도 해당 요소부터 다시 훑는다!
하지만 순서를 고려하지 않기 때문에 넘겨온 인덱스보다 이전 요소들을 방문하면 안되기 때문에
for 루프에서 `i = start`부터 진행하여, 이전 선택한 원소를 계속 선택할 수 있도록 함 (`i+1`이 아니라 `i`를 재귀 호출)
⇒ 포인트는 시작인덱스 start, 재귀 넘길때 반복문 인덱스 그대로 넘기기!
import java.util.Arrays;
public class DuplicateCombination {
static int[] arr;
static int[] output;
public static void main(String[] args) {
int n = 3;
int r = 2;
arr = new int[]{1, 2, 3};
output = new int[r];
dupCombi(0, 0, n, r);
}
static void dupCombi(int start, int depth, int n, int r) {
if (depth == r) {
System.out.println(Arrays.toString(output));
return;
}
for(int i=start; i<n; i++) {
output[depth] = arr[i];
dupCombi(i, depth+1, n, r);
}
}
}
⏰ 시간복잡도 : O(n^r)
✅ 최종 비교
순열에서는 뽑을 것들을 매번 처음부터 살펴보기 때문에
다시 뽑히지 않게 방문배열이 필요하고 조합에서는 필요 없는 것이다.
중복순열에서는 뽑을 것들을 매번 처음부터 살펴보지만,
순열과 달리 이미 뽑은 것들을 다시 뽑아도 되기 때문에 방문배열이 필요 없다.
조합에서는 순서를 고려하지 않기 때문에 각 요소가 뽑히는지 뽑히지 않는지 2가지 선택지만 있다.
또한 순열과 달리 뽑을 것들을 매번 처음부터 살피지 않고, 이전에 뽑힌 결과에 대해서는 신경쓰지 않는다.
따라서 이전에 무엇이 뽑혔던 현재 어디서부터 요소들을 살필 지에 대한 정보가 필요하다. (또는 몇개의 요소를 더 뽑으면 되는지 정보)
재귀를 넘길 때 현재 선택한 요소는 다음 재귀에서 탐색대상이 되면 안되기 때문에 현재 요소의 인덱스+1 한뒤에 넘긴다.
중복조합에서는 조합과 마찬가지로
각 요소가 뽑히는지 뽑히지 않는지 2가지 선택지만 있는 것과 이전에 뽑힌 결과를 신경쓰지 않는 것은 동일하다.
하지만 조합과는 달리 뽑았던 요소를 다시 뽑을 수 있기 때문에 이전에 뽑았던 요소의 인덱스를 받아서 해당 요소부터 다시 탐색한다.
따라서 조합과 가장 다른 차이점은 현재 선택한 요소가 다음 재귀에서도 탐색대상이 될 수 있기 때문에 현재 요소의 인덱스를 그대로 넘긴다.
| 방문배열 visited | 반복문 시작 인덱스 | 시간복잡도 | |
| 순열 | 필요 O | 0으로 고정 | 평균 : O(nPr) 최악 : |
| 중복순열 | 필요 X | 0으로 고정 | O(2^n) |
| 조합 | 필수는 아님 (사용하는 방법도 있음) |
반복문 시작 인덱스 + 1 하고 재귀 넘기기 | 평균 : O(nCr) 최악 : O(2^n) DP 사용시 , |
| 중복조합 | 필요 X | 반복문 시작 인덱스 그대로 재귀 넘기기 | O(n^r) |