완전 탐색 (순열, 조합)

순열? (Permutation)

n개 중에서 r개의 원소를 선택하여 나올 수 있는 경우를 모두 따진다. (순서를 고려한다.)

 

{1,2,3} 중 2개 원소를 순열 방식으로 선택

-> {1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}

 

구현 방법?

(curr은 List 자료구조를 사용하고 현재 선택한 원소를 담는다.)

(nums는 주어진 원소 배열이다.)

 

- BaseCase : curr.size() == nums.length; (또는 curr.size()  == 선택할 원소 개수 )

- before recursive call : curr 추가, visited[i] = true;

- recursive call

- after recursive call : 최근 추가한 curr 제거, visited[i] = false; 

재귀 사용 프로세스

요약

 

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

        // recursive call
        for(int i=0; i<nums.length; i++) {
            if(visited[i] == true) continue;
            // before recursive
            visited[i] = true;
            curr.add(nums[i]);
            // recursive call
            backtrack(nums, curr, result, visited);
            // after recursive
            visited[i] = false;
            curr.remove(curr.size()-1);
        }
    }

    public static void main(String[] args) {
        PermutationTemplate p = new PermutationTemplate();
        int[] nums = {1,2,3};
        List<Integer> curr = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];

        p.backtrack(nums, curr, result, visited);

        // 결과 출력
        for(List<Integer> list : result) {
            System.out.println(list);
        }

    }

 

조합? (Combination)

n개 중에서 r개의 원소를 선택하여 나올 수 있는 경우를 모두 따진다. (순서를 고려하지 않는다.)

 

{1,2,3} 중 2개 원소를 조합 방식으로 선택

-> {1,2}, {1,3}, {2,3}

 

구현 방법?

- BaseCase : curr.size() == nums.length; (또는 curr.size()  == 선택할 원소 개수 )

- before recursive : 선택한 것을 curr에 넣기 

- recursive call

- after recursive  : 최근 추가한 curr 제거

 

아래 그림처럼 0 인덱스 값을 골랐으면 1,2,3 번째 인덱스를 고를 수 있는 경우가 있고,

1 인덱스 값을 골랐으면 2,3 번째 인덱스를 고를 수 있는 경우가 있고,

2 인덱스 값을 골랐으면 3 번째 인덱스를 고를 수 있는 경우가 있다.

이런 경우, 고른 원소가 모두 다르도록 할 수 있다.

 

// {1,2,3} 중에서 조합으로 2개를 선택한다.
public void backtrack(int[] nums, List<Integer> curr, List<List<Integer>> result, int startIdx, int choose) {
        // basecase
        if(choose == curr.size()) {
            result.add(new ArrayList<>(curr));
            return;
        }
        // recursive call
        for(int i=startIdx; i<nums.length; i++) { // [0] -> [1], [2], [3] 선택 가능 | [1] -> [2], [3] 선택 가능 | [2] -> [3] 선택 가능
        	// before recursive
            curr.add(nums[i]);
            // recursive call
            backtrack(nums, curr, result, i+1, choose);
            // after recursive
            curr.remove(curr.size()-1);
        }
    }
    public static void main(String[] args) {
        CombinationTemplate c = new CombinationTemplate();
        int[] nums = {1,2,3};
        List<Integer> curr = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        c.backtrack(nums, curr, result, 0, 2);

        // 결과 출력
        for(List<Integer> list : result) {
            System.out.println(list);
        }

 

관련 문제

문제 이름	문제 태그	문제 사이트	해설
permutations (LeetCode)	#순열	https://leetcode.com/problems/permutations/description/
combinations (LeetCode)	#조합	https://leetcode.com/problems/combinations/description/
피로도 (프로그래머스)	#순열	https://school.programmers.co.kr/learn/courses/30/lessons/87946
소수 찾기(프로그래머스)	#순열, #소수 찾기, #해시	https://campus.programmers.co.kr/tryouts/140903/challenges
후보키(프로그래머스)	#조합	https://school.programmers.co.kr/learn/courses/30/lessons/42890	아직 미풀이