[Java] 순열, 조합, 부분집합을 구하는 알고리즘(for문, 비트마스크, 백트래킹)

코딩테스트에서 가장 일반적인 유형 중 하나가, 순열, 조합, 부분집합을 구하는 문제이다. 문제마다 최적화 방안이 다르기 때문에, 조건에 가장 잘 맞는 알고리즘을 사용해 최적화해야 한다.

N개 중 M개를 뽑는 경우의 수에서, M의 가짓수가 3 이하일 경우 for문을 쓰는 것이 문제를 효율적이고 빠르게 푸는 방법이 된다.

다만 M의 숫자가 고정되어있지 않을 경우 for문으로 구할 수 없으며, 모든 경우의 수를 전부 탐색하기 때문에 M이 클 경우 비효율적인 방식이 된다.

다음은 중복 없이 N개 중 3개의 조합을 구하는 3중 for문의 예시이다.

for (int i = 1 ;  i <= N-2 ; i++) {
			for (int j = i+1; j <= N-1 ; j++) {
				if(i == j) continue;
				for( int k = j+1; k <= N; k++) {
					if(j == k) continue;
					System.out.println( i+ " " + j + " " + k );
				}
			}
		}

비트 마스크는 비트 연산을 응용하는 기법을 의미한다. N이 20 이하고 메모리 사용을 최소화할 때는 비트 마스크를 사용하는 것이 유리하다.

비트 연산은 매우 빠르기 때문에, 속도에 유리하지만, 모든 경우의 수를 구하는 브루트 포스 방식이기 때문에, 2^n 개의 경우를 모두 고려한다. 따라서 절대적인 가짓수가 많을 경우 비효율적인 방식이 된다.

다음은 비트 마스크를 사용해 부분 집합을 생성하는 예시 코드이다.

public class SubsetBitmask {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int n = arr.length;
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    System.out.print(arr[j] + " ");
                }
            }
            System.out.println();
        }
    }
}

백 트래킹은 가장 일반적인 방식으로서, 기본적으로 모든 가능한 조합을 탐색하면서 불필요한 경로를 가지치기를 한다. 재귀 호출을 통해 상태를 탐색하므로, 백 트래킹은 재귀의 하위 집합에 속한다. 백트래킹은 효율적이고 명확하며 유연한 장점이 있다.

백 트래킹은 3가지 과정으로 동작한다.

• 상태 공간 탐색 : 가능한 모든 해결책을 포함하는 트리 탐색
• 유망성 검사 : 현재 경로가 문제의 해결책으로 유망한지 검사하고, 유망하지 않다면 더 이상 탐색하지 않고 돌아감(백 트랙)
• 해 해결책 결정 : 유망한 경로를 따라 탐색을 진행하고, 문제의 해결책을 찾으면 이를 기록함

다음은 백 트래킹을 사용하여 N개의 원소 중 M개의 조합을 뽑는 예시 코드이다.

import java.util.*;

public class Combinations {
    public static void main(String[] args) {
        int[] nums = new int[100];
        for (int i = 0; i < 100; i++) {
            nums[i] = i + 1;
        }
        int m = 10;
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, m, 0, new ArrayList<>(), result);
        System.out.println(result.size());
        
        for (int i = 0; i < result.size()); i++) {
            System.out.println(result.get(i));
        }
    }

    public static void backtrack(int[] nums, int m, int start, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == m) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(nums, m,, i + 1, current, result);
            current.remove(current.size() - 1); 
        }
    }
}

boolean[] visited 배열을 사용할 경우, 동일한 원소가 여러 번 선택되는 것을 방지하고, 이미 방문한 원소를 건너뛰어서 탐색을 효율적으로 만들며, 상태를 명확하게 관리할 수 있어 순열 문제에서 유용하게 쓰인다.

다음은 백 트래킹에서 boolean[] visited 배열을 사용해 N개 중 M개의 순열을 고르는 예시이다.

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int m = 10;
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(nums, k, new ArrayList<>(), result, visited);
        System.out.println(result.size());
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }

    public static void backtrack(int[] nums, int m, List<Integer> current, List<List<Integer>> result, boolean[] visited) {
        if (current.size() == m) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                current.add(nums[i]);
                backtrack(nums, m, current, result, visited);
                current.remove(current.size() - 1);
                visited[i] = false;
            }
        }
    }
}