안녕하세요!
오늘은 알고리즘 문제에서 자주 볼 수 있는 순열과 조합을 구현하는 방법에 대해 간단히 소개시켜 드리고자 합니다🤗
순열(Permutation)
순열이란? n개의 숫자 중에서 r개의 숫자를 순서대로 뽑는 경우를 의미합니다.
예를 들어, [1, 2, 3] 배열 중 2개의 숫자를 순서대로 뽑은 결과는 아래와 같습니다.
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]위와 같은 순열은 각각 Swap과 백트래킹을 이용하여 구현할 수 있습니다!
Swap
// Swap
class Permutation {
private int n;
private int r;
private int[] now; // 현재 순열
private ArrayList<ArrayList<Integer>> result; // 모든 순열
public Permutation(int n, int r) {
this.n = n;
this.r = r;
}
public void permutation(int[] arr, int depth) {
// 현재 순열의 길이가 r일 때 결과 저장
if (depth == r) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(now[i]);
}
result.add(temp);
return;
}
for (int i = depth; i < n; i++) {
swap(arr, i, depth);
now[depth] = arr[depth];
permuation(arr, depth + 1);
swap(arr, i, depth);
}
}
public void swap(int[] arr, i, j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}배열에서 특정한 두 위치의 값을 바꾸는 swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법입니다.
배열의 첫 번째 값부터 순서대로 하나씩 바꾸면서 모든 값을 한번씩 swap 합니다.
depth를 기준 인덱스로 하여 depth보다 인덱스가 작은 값들은 그대로 고정하고
depth보다 인덱스가 큰 값들만 가지고 swap을 진행하면 됩니다.
백트래킹
// 백트래킹
class Permutation {
private int n;
private int r;
private int[] now; // 현재 순열
private ArrayList<ArrayList<Integer>> result; // 모든 순열
public Permutation(int n, int r) {
this.n = n;
this.r = r;
}
public void permutation(int[] arr, boolean[] visited, int depth) {
// 현재 순열의 길이가 r일 때 결과 저장
if (depth == r) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(now[i]);
}
result.add(temp);
return;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
now[depth] = arr[i];
permuation(arr, depth + 1);
visited[i] = false;
}
}
}
}백트래킹은 visited배열을 이용한 방문처리 방식을 이용하여 구현합니다.
배열을 차례대로 순회하면서 해당 인덱스의 원소를 순열의 값으로 집어넣고, 해당 인덱스를 방문처리합니다.
이후 depth의 값을 1만큼 증가시킨 뒤에 함수를 재귀 호출 합니다.
여기서 중요한점☝️
앞서 방문처리한 인덱스를 방문처리하지 않는 상태(false)로 다시 돌려놓은 뒤에 다음 인덱스로의 순회를 진행합니다.
방문처리를 다시 초기화 해줘야 방문처리 했던 인덱스의 원소를 새로운 순열에서 재사용할 수 있기 때문입니다!
조합(Combination)
조합이란? n개의 숫자 중에서 r개의 수를 순서와 상관없이 뽑는 경우를 의미합니다.
예를 들어 [1, 2, 3] 배열 중 2개의 숫자를 순서와 상관없이 뽑은 결과는 아래와 같습니다.
[1, 2]
[1, 3]
[2, 3]앞서 설명한 순열과 다르게 조합에서는 순서에 상관없이 뽑기 때문에 중복된 수는 모두 제외됩니다.
조합은 크게 백트래킹과 재귀를 이용하여 구현할 수 있습니다.
백트래킹
// 백트래킹
class Combination {
private int n;
private int r;
private int[] now; // 현재 조합
private ArrayList<ArrayList<Integer>> result; // 모든 조합
public Combination(int n, int r) {
this.n = n;
this.r = r;
this.now = new int[r];
result = new ArrayList<ArrayList<Integer>>();
}
public void combination(int[] arr, int[] visited, int start, int depth) {
if (depth == r) { // r개의 조합을 완성한 경우
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(now[i]);
}
result.add(temp);
return;
}
for (int i = start; i < n; i++) {
if (!visited[i]) { // 방문하지 않은 수에 대하여
now[depth] = arr[i];
visited[i] = true; // 방문 처리
combination(arr, visited, i + 1, depth + 1);
visited[i] = false; // 방문 처리 백트래킹
}
}
}
}백트래킹은 앞서 순열에서 사용한 백트래킹과 개념적으로 같습니다.
예를 들어 [1, 2, 3] 배열 중 2가지 원소를 뽑아 조합을 구성할 때를 살펴보겠습니다.
이때 start는 0부터 시작하게 됩니다.
위와 같이 for문에 진입하면 제일 먼저 배열의 0번째 원소 1을 뽑습니다.
이때 중복이 없는 조합의 성질에 따라 0번째 원소를 다시 뽑지않기 위해 visited배열에 해당 원소를 방문처리를 합니다.
이후 start와 depth 의 값을 1 증가시켜 주고, 함수를 재귀 호출합니다.
앞서 순열의 백트래킹 방식과 동일하게 꼭! 방문처리를 초기화 해줘야합니다.
그래야 start가 바뀐 다음의 for문을 수행할 때, 전에 뽑았던 조합과 상관없이 새로운 조합을 뽑을 수 있기 때문입니다.
말로는 다소 이해하기 어려울 수 있지만, 직접 코드를 작성하고, 출력을 해보면 쉽게 이해하실 수 있습니다💪
(사실 백트래킹은 재귀의 범주에 포함됩니다. 백트래킹 구현에 재귀적인 호출이 발생하기 때문인데, 이와 별개로 방문처리를 통해 구현하기 때문에 재귀와 분리하여 소개하였습니다🙇♂️)
재귀
// 재귀
class Combination {
private int n;
private int r;
private int[] now; // 현재 인덱스의 조합
private ArrayList<ArrayList<Integer>> result; // 모든 조합
public Combination(int n, int r) {
this.n = n;
this.r = r;
this.now = new int[r];
this.result = new ArrayList<ArrayList<Integer>>();
}
public void combination(int[] arr, int depth, int index, int target) {
if (depth == r) { // r개의 조합을 완성한 경우
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(arr[now[i]]);
}
result.add(temp);
return;
}
if (target == n) return;
now[index] = target;
combination(arr, depth + 1, index + 1, target + 1);
combination(arr, depth, index, target + 1);
}
}위 코드에서는 r개 중 몇 번째까지 조합을 구성했는지를 나타내는 depth
조합을 구성하는 현재 배열의 위치를 나타낸 index
n개 배열의 원소 중 조합으로 구성할 target을 변수로 사용합니다.
사실 depth와 index는 같은 역할을 하고 있지만, 좀 더 간단한 이해를 위해 분리 선언하였습니다.
실제 구현하실 때는 index 변수 선언 없이 구현하셔도 상관없습니다!
백트래킹 때와 마찬가지로 [1,2,3] 배열 중 2가지 원소를 뽑아 조합을 구성하는 경우를 살펴보겠습니다.
처음에 depth와 index를 0으로, 배열의 첫번째 원소 1을 target으로 정합니다.
첫 호출 시, 조합의 첫번째 원소로 target의 값 1이 들어가게 됩니다. 이후의 재귀 호출에서 depth, index, target의 값을 모두 1 씩 증가시켜 줍니다.
추가로 depth와 index는 그대로 두고 target의 값 만 1 증가시킨 값을 재귀 호출 해줍니다.
이는 첫번째 원소로 1을 뽑지않는 경우를 고려하기 위함입니다.
재귀 호출에서 가장 중요한 점은 재귀 호출을 종료하는 조건을 정하는 것입니다.
만약 재귀 종료 조건을 잘못 정한다면 무한루프에 빠질 수 있기 때문에, 항상 신중하게 종료 조건을 정해야합니다.
앞서 구현한 순열과 조합에서는 depth가 r이 되어 모든 순열 및 조합을 구성한 경우에 재귀를 종료했습니다.
또한 조합의 재귀 구현방법에서 target이 n이 될 때도 종료 조건으로 추가해줍니다.
추가) 조합의 경우의 수
지금까지 순열과 조합을 구현하는 방법에 대해 알아보았습니다.
추가로 조합의 경우의 수를 구하는 방법에 대해 소개하고 마치도록 하겠습니다🫡
조합의 경우의 수는 조합의 성질과 재귀를 이용하여 구현할 수 있습니다.
조합에는 다음과 같은 성질이 있습니다.
1. nCr = n-1Cr-1 + n-1Cr
2. nCn = 1
3. nC0 = 1
예를 들어 3개 중에서 2개를 뽑는 경우,
3C2 = 2C1 + 2C2 로 표현할 수 있으며, 2C1 = 1C0 + 1C1 = 2이고, 2C2 = 1이므로
결론적으로 3이라는 정답을 얻을 수 있습니다.
즉, nCn = 1 또는 nC0 = 1의 값이 나올 때까지 재귀적으로 구현하면 됩니다.
코드는 아래와 같습니다.
public int combination(int n, int r) {
if (n == r || r == 0) return 1;
return combination(n - 1, r - 1) + combination(n - 1, r);
}'알고리즘 > 개념' 카테고리의 다른 글
| [알고리즘 / Java] 벨만 포드 알고리즘 (0) | 2023.03.12 |
|---|---|
| [알고리즘 / Java] 완전탐색(DFS, BFS) (0) | 2021.09.25 |