순열
순열은 "서로 다른 n개의 원소에서 r개를 중복 없이, 순서에 상관 있게 선택하는 경우의 수"다.
예를 들어 {1, 2, 3}라는 원소들이 있다고 한다면, 이 중 2개를 중복 없이 순서에 상관 있게 선택하는 경우의 수는 다음과 같다.
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
각 경우의 수에서 각각의 원소들은 1개만 포함되어 있다.
이것이 "중복 없이" 뽑는다는 의미다.
또한 (a, b)와 (b, c)이 다른 경우의 수로 취급되고 있다.
이것이 "순서에 상관있게"의 의미다.
조합
조합은 "서로 다른 n개의 원소에서 r개를 중복 없이, 순서에 상관 없게 선택하는 경우의 수"다.
예를 들어 {1, 2, 3}라는 원소들이 있다고 한다면, 이 중 2개를 중복 없이 순서에 상관 없게 선택하는 경우의 수는 다음과 같다.
(1, 2)
(1, 3)
(2, 3)
(3, 2)
앞서 본 순열과 같이 각 경우의 수에서 각각의 원소들은 1개만 포함되어 있다.
이것이 "중복 없이" 뽑는다는 의미다.
그리고 순열과 다르게 (a, b)와 (b, c)이 같은 경우의 수로 취급되고 있다.
순열에서는 (1, 2)와 (2, 1)이 서로 다른 경우의 수로 취급되지만, 조합에서는 같게 취급된다.
즉, a와 b를 선택할 때 a가 앞에 오든, b가 앞에 오든 같은 경우의 수로 취급하고 있는 것이다.
이것이 "순서에 상관 없게"의 의미다.
순열과 조합 코드(List)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Solution {
static LinkedList<Integer> list = new LinkedList<>();
static int N;
static int R;
static int[] arr;
public static void comb(int depth, int start) {
if (list.size() == R) {
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
return;
}
for (int i = start; i < arr.length; i++) {
if (!list.contains(arr[i])) {
list.addLast(arr[i]);
comb(depth + 1, i + 1);
list.removeLast();
}
}
}
public static void perm(int depth){
if (list.size() == R) {
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
return;
}
for (int i = 0; i < arr.length; i++) {
if (!list.contains(arr[i])) {
list.addLast(arr[i]);
perm(depth + 1);
list.removeLast();
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
R = Integer.parseInt(br.readLine());
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = i + 1;
}
System.out.println("Permutation");
perm(0);
list = new LinkedList<>();
System.out.println("\nCombination");
comb(0, 0);
}
}
순열과 조합 구현(배열)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Solution {
static LinkedList<Integer> list = new LinkedList<>();
static int N;
static int R;
static int[] arr;
static int[] num;
static boolean[] isUsed;
public static void comb(int depth, int start) {
if (depth == R) {
for (int i = 0; i < R; i++) {
System.out.print(num[i] + " ");
}
System.out.println();
return;
}
for (int i = start; i <= arr.length; i++) {
if (!isUsed[i]) {
num[depth] = i;
isUsed[i] = true;
comb(depth + 1, i + 1);
isUsed[i] = false;
}
}
}
public static void perm(int depth){
if (depth == R) {
for (int i = 0; i < R; i++) {
System.out.print(num[i] + " ");
}
System.out.println();
return;
}
for (int i = 1; i <= arr.length; i++) {
if (!isUsed[i]) {
num[depth] = i;
isUsed[i] = true;
perm(depth + 1);
isUsed[i] = false;
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
R = Integer.parseInt(br.readLine());
arr = new int[N];
isUsed = new boolean[N + 1];
num = new int[R];
for (int i = 0; i < N; i++) {
arr[i] = i + 1;
}
System.out.println("Permutation");
perm(0);
isUsed = new boolean[N + 1];
num = new int[R];
System.out.println("\nCombination");
comb(0, 1);
}
}
main에서는 n과 r에 해당하는 값을 입력받는다.
만약 n이 5라면, 원소는 {1, 2, 3, 4, 5}로 구성되며, 이 중 r개 만큼의 원소를 선택하는 경우의 수를 구하게 된다.
백트래킹 알고리즘을 이용해 순열과 조합을 구할 수 있다.
순열과 조합의 차이는 순서의 차이기 때문에 전체적인 로직은 비슷하다.
둘 다 재귀 호출로 구현하였으며, r의 길이에 도달하게 되면 리스트에 있는 모든 원소를 출력한다.
재귀 호출 시에는 다음 자리에 올 수를 선택하기 위해 depth + 1을 패러미터로 준다.
또한 모든 경우의 수를 구하기 위해 list의 인덱스(depth)를 하나 채우고(addLast) 재귀 호출 후에 다시 그 인덱스를 비우는 식(removeLast)으로 진행된다.
순열과 조합의 차이점은 바로 패러미터에 start라는 변수가 들어가는지의 여부다.
start 변수는 순서에 상관 없게 출력하기 위한 변수다.
예를 들어 1, 2와 2, 1은 조합에서 같은 경우의 수로 취급되는데, 이를 위해서 현재 선택된 값보다 더 작은 값이 선택되지 않도록 한다.
만약 전체 원소가 {1, 2, 3, 4}이고 현재 선택된 수가 2라면, 2보다 작은 값인 1이 선택되지 않게 하기 위해서 i + 1부터 다음 자리에 대한 for문을 돌리는 것이다.
즉, for 문은 2보다 큰 값인 3 -> 4 순으로 돌게 되어 순서만 다른 경우의 수를 제거한다.
배열로 구현하게 되면 isUsed와 같은 변수를 두어 중복을 제거해주어야 한다.
하지만 List와 같은 자료구조를 사용하면 contains()과 같은 메소드로 원소가 사용되었는지 간편하게 체크할 수 있다.
그러나 이에 따른 오버헤드가 발생할 것이다.
isUsed를 배열로 만들고, 이를 통해 체크하게 되면 O(1)의 시간에 체크할 수 있다.
하지만 contains() 메소드를 사용하면 리스트의 크기가 N이라고 할 때 O(N)의 시간 복잡도를 가지게 될 것이다.
또한 리스트 자료구조에서 노드를 추가하고 제거하는 것을 반복하는 것에서도 오버헤드가 있을 것이다.
그럼에도 불구하고 본인은 해당 방법이 가지는 구현의 편리함이 크다고 판단한다.
아무래도 숫자를 저장할 num 배열과 사용 여부를 저장할 isUsed 배열 두 개를 사용하는 것보단, 하나의 리스트를 쓰는 것이 간편하기 때문이다.
또한 List를 이용한 구현에서 perm과 comb 메소드에 패러미터 depth를 넣어주고 있지만, 해당 패러미터가 없어도 작동한다.
왜냐하면 list.size()를 이용하여 현재 숫자의 길이(depth)를 구할 수 있기 때문이다.
물론 메모리나 속도 제한이 엄격한 조건에서는 배열을 사용하는 것이 좋다고 생각한다.
BOJ 10974(모든 순열) 문제에서 리스트와 배열을 사용한 메모리와 시간은 각각 아래와 같다.
리스트로 구현: 메모리 82604 KB, 시간 2692 ms
배열로 구현: 메모리 55752 KB, 시간 1956 ms
'Problem Solve' 카테고리의 다른 글
| [백준 / BOJ] 2178 : 미로 탐색 (JAVA) (0) | 2023.02.02 |
|---|---|
| [백준 / BOJ] 1926 : 그림 (JAVA) (0) | 2023.01.12 |
| [백준 / BOJ] 15649 : N과 M (1) (JAVA) (0) | 2023.01.10 |
| [백준 / BOJ] 1021 : 회전하는 큐 (JAVA) (0) | 2023.01.07 |
| [백준 / BOJ] 2748번 : 피보나치 수2 (Java) (0) | 2023.01.03 |
