자바로 알고리즘 시작하기 5 - 완전탐색 (순열, 조합, 부분집합)
이번에는 자바를 이용한 완전탐색의 기본인 순열, 조합, 그리고 부분집합을 구현하는 기본 알고리즘에 대하여 알아보겠습니다. 이를 사용하여 기본 완전탐색을 수행할 수 있습니다.
순열
순열은 서로 다른 것 중 순서를 고려하여 나열하는 것입니다. 우리가 알고리즘에서 순열을 사용하는 경우로는, 순서를 고려하여 경우의 수를 완전 탐색할 때 사용합니다.
이는 서로 다른 것 중 선택을 할 때 중복을 허용하냐 안하냐를 먼저 확인해야 하는데, 이는 중복 검사의 유무만 체크하여 구분해주면 되니 지금은 중복이 없는 경우를 기준으로 하나하나 차근차근 코드와 함께 보겠습니다.
public class Permutation {
static int[] data;
static int N; // 총 개수
static int R; // 구하고자 하는 개수
static int[] numbers; // 순서를 고려하여 선택한 경우
public static void main(String[] args) {
/**
* given
*/
data = new int[]{1,2,3,4,5,6,7,8,9,10};
N = data.length; // 10
R = 5;
numbers = new int[R];
/**
* then
*/
permutation(0);
}
}
위 코드를 기준으로 permutation 함수를 구현해 봅시다. permutation은 재귀를 이용한 구현이 가장 일반적입니다. (반복문이 아닌 재귀를 사용하는 이유는, 반복 횟수를 다이나믹하게 가져가면서 모든 경우를 항상 온전하게 탐색하는 걸 보장하기 위해서입니다.)
public static void permutation(int idx) {
if (idx == R) {
// 필요한 로직 수행
return;
}
top:
for (int i = 0; i < N; i++) {
// 중복 검사
for (int j = 0; j < N; j++) {
if (numbers[j] == data[i]) {
continue top; // 레이블을 사용하여 탈출
}
numbers[idx] = data[i];
permutation(idx + 1);
}
}
}
위처럼 탐색하면 가장 기본적으로 순열 완전탐색이 가능합니다. 하지만 위 로직에선 중복 검사 로직이 반복문으로 되어 있어서 매번 n번의 연산을 수행하는 것이 부담스럽습니다. 따라서 이를 visited라는 배열을 활용하여 입력하려는 값에 대하여 중복 여부를 사전에 연산할 때 저장해두고 이를 조회하는 형식으로 하면 시간을 줄일 수 있을 겁니다. 한번 해 봅시다.
public static void permutation(int idx) {
if (idx == R) {
return;
}
for (int i = 0; i < N; i++) {
// 중복 검사
if (visited[i]) {
continue;
}
numbers[idx] = data[i];
visited[i] = true;
permutation(idx + 1);
visited[i] = false;
}
}
위 방식은 가장 일반적으로 사용되는 순열 로직이며, 대부분의 경우 위처럼 순열 로직을 구성했을 때 문제 없이 풀 수 있습니다. "배열"이라는 공간을 활용하여 수행 시간을 줄인 거고, 위에서 중복 검사를 위해 매번 모든 숫자를 돌아보는 O(N)의 수행 로직을 사용한 것보다 효율적입니다. 다만, 이 로직에서는 visited[] 배열을 관리해줘야 하며, 이는 data의 i번째 숫자에 대하여 있고 없는 경우를 모두 탐색해야 하므로 visited[i]를 true 해줬다가 재귀 이후에 false해주어 모든 경우를 탐색할 수 있게끔 해줘야 합니다.
잠깐 참고로 보자면, visited배열은 비트마스킹을 이용하면 메모리를 효율적으로 활용하면서 더욱 빠르게 수행할 수 있습니다. 이는 비트 단위 연산이 기존 원시타입을 그대로 연산하는 것 보다 더욱 빠르기 때문입니다. 메모리 활용도 또한 boolean이 1byte * N인 것에 비해 int 하나 쓰면 32bit를 각각 visited로 사용할 수 있으니 일반적인 경우에 메모리 활용도가 더 뛰어나다는 것에선 더 설명할 것도 없죠. 한번 봅시다.
public static void permutation(int idx, int visited) {
if (idx == R) {
return;
}
for (int i = 0; i < N; i++) {
if ((visited & 1 << i) != 0) {
continue;
}
numbers[idx] = data[i];
permutation(idx + 1, visited | 1 << i);
}
}
처음에는 방문한 data가 없으니 main 함수에서 permutation(0, 0); 으로 호출해서 사용하면 됩니다.
그러면 이제 swap을 이용한 방법을 알아봅시다. 이는 nPn인 경우를 탐색할 때 가장 유용하며, 자신이 문자열 파싱만 잘 해주면 nPr도 충분히 가능합니다. 지금까지의 방식 중에서는 가장 빠른 알고리즘입니다.
public static void permutation(int depth) {
if (depth = R) {
return;
}
for (int i = depth; i < N; i++) {
swap(depth, i, arr);
permutation(depth+1);
swap(depth, i, arr);
}
}
public static void swap(int i, int j, int[] arr) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
대체로 nPn인 경우에 사용하는 스킬인데, 이는 순서를 보장하지 않아서 순열 경우의 수를 순서 관계 없이 모두 훑는 경우에 편하게 사용 가능합니다.
그럼 딱 하나만 더 나아가서, swap을 이용한 로직 중에 next permutation이라는 알고리즘이 있습니다. 이는 nPn의 경우에 다음 순서의 순열을 알아내는 알고리즘인데, 이를 활용하여 모든 순열을 탐색할 수 있습니다. 코드로 봅시다.
public void main(int[] arr) {
Arrays.sort(arr); // 오름차순 정렬
// 정렬 이후 가장 최초의 순열 출력
System.out.println(Arrays.toString(arr));
while(!np(arr)) {
break;
}
}
public static void np(int[] arr) { // next permutation
// 배열은 반드시 오름차순으로 정렬된 상태여야 하고,
// 오름차순으로 처음 정렬했을 때의 순열은 np 사용 전에 알아서 써야 함
final int LAST_INDEX = arr.length - 1;
// 맨 뒤에서부터 배열을 거꾸로 순회하면서 내림차순이 되는 순간의 인덱스 확인
int i = LAST_INDEX;
while (i > 0 && arr[i-1] >= arr[i]) {
--i;
}
// 만약 i 인덱스가 끝까지 같으면 다음 순열 없음
if (i == 0) {
return false;
}
// 다시 뒤에서부터 배열을 거꾸로 순회하면서 내림차순 인덱스보다 큰 첫번째 수 확인
int j = LAST_INDEX;
while (arr[i-1] >= arr[j]) {
--j;
}
// 숫자 바꿔주고
swap(arr, i, j);
// 스왑한 인덱스 이후 요소들을 역정렬
int k = LAST_INDEX;
while(i <= k) {
swap(arr, i++, k--);
}
// 필요시 여기서 순열이 완성되어 있으니 로직 수행
System.out.println(Arrays.toString(arr));
return true;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
위 알고리즘은 조금 코드가 길어보이긴 하지만, 원리를 이해하면 그다지 구성하는 게 어렵지 않고, 단순히 swap을 사용하는 것 보다 함수를 수행하는 반복수가 적어서 더 빠른 알고리즘입니다. 알고 있어서 나쁠 건 없어 보입니다.
조합
조합은 위 순열에서 순서를 고려하지 않는 경우의 수를 탐색하는 방법입니다. 그럼 바로 코드로 봐 보겠습니다.
public class Permutation {
static int[] data;
static int N; // 총 개수
static int R; // 구하고자 하는 개수
static int[] numbers; // 조합
public static void main(String[] args) {
/**
* given
*/
data = new int[]{1,2,3,4,5,6,7,8,9,10};
N = data.length; // 10
R = 5;
numbers = new int[R];
/**
* then
*/
combination(0, 0);
}
}위 코드를 기준으로 combination() 메서드를 짜 봅시다.
public static void combination(int start, int cnt) {
if (cnt == R) {
return;
}
for (int i = start; i < N; i++) {
numbers[cnt] = data[i];
combination(i + 1, cnt + 1);
}
}고르기 시작하는 숫자의 인덱스를 start, 그리고 현재 몇 개나 골랐는지를 cnt라는 변수로 관리하여 중복 없이 숫자를 모두 담아낼 수 있습니다. 조합도 여러 방법이 있겠지만 이게 범용적으로, 그리고 효율적으로 사용되는 알고리즘이니 이 로직 하나만 잘 기억해두면 됩니다.
부분집합
부분집합은 일종의 조합을 단순화한 로직입니다. 조합을 이용한 숫자를 그대로 활용하는 게 아니라 포함 여부만 체크할 경우에는 데이터 조합을 구성해둘 필요가 없습니다. 따라서 포함 여부만 체크해둔 뒤 활용할 거라면 조합을 저장해두기보단 부분집합인지를 체크해두고 사용할 수 있습니다. 이를 구현하면 아래와 같습니다.
public static void powerSet(int cnt) {
if (cnt == N) {
// 필요 작업 수행 (예시 : 출력)
for (int i = 0; i < n; i++) {
if (visited[i] == true)
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
visited[cnt] = true;
powerSet(cnt + 1);
visited[cnt] = false;
powerSet(cnt + 1);
}
이는 비트로 구성하면 아래와 같이 더 단순화할 수 있습니다.
public static void bit(int n) {
int end = 1 << n;
for (int i = 0; i < end; i++) {
for (int j = 0; j < n; j++) {
if ((i & 1 << j) != 0) {
// 필요 작업 수행 (예시 : 출력)
System.out.print(arr[j] + " ");
}
}
System.out.println();
}
}
이렇게 자바를 이용한 순열, 조합, 부분집합을 이용한 완전탐색에 사용되는 알고리즘의 기본을 이해해 봤습니다. 관련된 추천 문제를 몇개 남기면서 글을 마무리 하겠습니다.
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
15652번: N과 M (4)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문
www.acmicpc.net