[Algorithm] 완전 탐색(Brute Force) 유형 모음 feat. Java

728x90

순열(Permutation)

여러 개의 요소 중에서 순서를 고려하여 특정 개수를 뽑는 문제로, 완전 탐색의 대표적인 유형이다.
보통 '백트랙킹'을 사용하여 구현한다

최적화 전

import java.util.*;

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        permutation(new ArrayList<>(), new boolean[N]);
        System.out.println(sb.toString());
    }

    private static void permutation(List<Integer> curr, boolean[] taken) {
        if (curr.size() == N) {
            for (int num : curr) {
                sb.append(num + " ");
            }
            sb.append("\n");
        }

        for (int i = 0; i < taken.length; i++) {
            if (taken[i]) continue;
            taken[i] = true;
            curr.add(i + 1);
            permutation(curr, taken);
            curr.remove(curr.size() - 1);
            taken[i] = false;
        }
    }
}

백트랙킹을 위해 현재까지 뽑힌 수열(curr)과 사용 여부 배열(taken)을 매개변수로 전달하며 재귀 호출하는 형태이다.
이때의 매개변수는 static 변수로 선언하여 매개변수 개수를 줄일 수 있다.
또한, List<Integer> 보다는 int[]를 사용하여 메모리 사용량도 줄일 수 있고, 인덱스 접근 속도도 향상 시킬 수 있다.

최적화 후

import java.util.*;

public class Main {
    static int N;
    static boolean[] taken;
    static int[] curr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        taken = new boolean[N];
        curr = new int[N];

        permutation(0);
        System.out.println(sb.toString());
    }

    private static void permutation(int depth) {
        if (depth == N) {
            for (int num : curr) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < taken.length; i++) {
            if (taken[i]) continue;
            taken[i] = true;
            curr[depth] = i + 1;
            permutation(depth + 1);
            taken[i] = false;
        }
    }
}

기존의 List<Integer>과 boolean[] 매개변수를 static 변수로 옮겨주었다.
- List는 메모리 사용량 절감 및 속도 향상을 위해 int[]로 변경하였다
기존의 curr을 통해 현재 순열의 길이를 확인했다면, 이제는 depth라는 매개변수를 통해 현재 순열의 길이를 관리한다.
- depth = 몇 개의 숫자를 뽑았는지

N과 M(1)

백준 - N과 M(1)

위 문제 역시 조금만 수정하여 거의 동일한 코드로 해결할 수 있다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] result;
    static boolean[] taken;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        result = new int[M];
        taken = new boolean[N];

        permutation(0);
        System.out.println(sb.toString());
    }

    private static void permutation(int depth) {
        if (depth == M) {
            for(int i : result) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if(taken[i]) continue;

            taken[i] = true;
            result[depth] = i + 1;
            permutation(depth + 1);
            taken[i] = false;
        }
    }
}

응용: 중복순열 - N과 M(3)

중복 체크를 위한 taken[] 관련 코드를 삭제하면 중복 순열 문제를 해결할 수 있다.

백준 - N과 M(3)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] result;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        result = new int[M];

        permutation(0);
        System.out.println(sb.toString());
    }

    private static void permutation(int depth) {
        if (depth == M) {
            for(int i : result) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            result[depth] = i + 1;
            permutation(depth + 1);
        }
    }
}

N개의 수 중에서 1 ~ M개의 수를 뽑는 수열 모두 구하기

이제까지는 항상 depth가 M이 되었을 경우, 즉 M개를 다 뽑았을 경우에만 수열을 확인했다.
하지만, 꼭 M개를 다 뽑지 않더라도 nP1, nP2, ... nPm을 모두 구하고 싶은 경우가 있을 수 있다.
이 경우, 다음과 같이 기존 기저 사례 확인 부분에서의 조건을 변경하고, return 문을 없애주면 된다!

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static List<Integer> result;
    static boolean[] taken;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        result = new ArrayList<>();
        taken = new boolean[N];

        permutation(0);
        System.out.println(sb.toString());
    }

    private static void permutation(int depth) {
        if (!result.isEmpty()) {
            for (int i : result) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
        }

        for (int i = 0; i < N; i++) {
            if (taken[i]) continue;

            taken[i] = true;
            result.add(i + 1);
            permutation(depth + 1);
            result.remove(result.size() - 1);
            taken[i] = false;
        }
    }
}

기존 if(depth == M)에 해당하는 기저사례 체크 부분을 if(!result.isEmpty())로 변경하였다.
- 이는, 하나라도 수가 뽑힌 경우 모두 체크하기 위함이다.
또한, 해당 기저 사례에서 return을 통해 함수를 종료하지 않고 계속 이어나간다.

결과는 다음과 같다.

조합(Combination)

조합 문제는 순열과 매우 유사한 문제로, 여러 개의 요소 중에서 '순서를 고려하지 않고' 특정 개수를 뽑는 문제이다
마찬가지롤 백트랙킹을 통해 쉽게 구현할 수 있다

백준 - N과 M(2)를 예제로 코드를 살펴보자

최적화 전

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] result;
    static boolean[] taken;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        result = new int[M];
        taken = new boolean[N];

        combination(0, 0);
        System.out.println(sb.toString());
    }

    private static void combination(int start, int depth) {
        if (depth == M) {
            for(int i : result) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i < N; i++) {
            if(taken[i]) continue;

            taken[i] = true;
            result[depth] = i + 1;
            combination(i + 1, depth + 1);
            taken[i] = false;
        }
    }
}

순열에서의 코드와 다른 점은 start라는 매개변수가 추가되었다는 점이다.
조합은 순서를 고려하지 않으므로, 이전에 확인한(?) 숫자는 다시 보지 않아도 되기 때문에, combination 메서드 내부 for 루프에서 i가 0이 아닌 start부터 시작한다

최적화 후

한가지 간과한 점은, 조합이 한 번 뽑은 숫자를 다시 선택하지 않는다는 점이다. 이를 이해한다면 중복 체크용 taken[]을 제거할 수 있다.

start 변수를 활용하여 이미 선택한 숫자 이후의 숫자만 탐색하도록 변경하자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[] result;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        result = new int[M];

        combination(0, 0);
        System.out.println(sb.toString());
    }

    private static void combination(int start, int depth) {
        if (depth == M) {
            for(int i : result) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i < N; i++) {
            result[depth] = i + 1;
            combination(i + 1, depth + 1);
        }
    }
}

taken과 관련된 코드를 모두 삭제하였다. 훨씬 간결해졌다!

부분집합(Subset)

주어진 집합에서 가능한 모든 부분집합을 고려하는 문제
예를 들면,
- N개의 숫자 중 일부를 골라 그 합이 특정 값이 되는 경우 찾기
- 가능한 모든 조합을 고려하여 조건을 만족하는 최적 해 찾기
보통 DFS나 백트랙킹 등을 이용해서 품

[백준 - 부분수열의 합(S2, 1182)] 문제를 풀어보자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, S, ret;
    static int[] nums;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        nums = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        solve(0, 0);
        if(S == 0) --ret; // S가 0이면, 아무것도 선택하지 않은 경우(공집합) 처리해주어야 함

        System.out.println(ret);
    }

    private static void solve(int depth, int sum) {
        if (depth == N) {
            if (sum == S) ++ret;
            return;
        }

        solve(depth + 1, sum);
        solve(depth + 1, sum + nums[depth]);
    }
}

케이스를 직접 그림으로 그려보면 규칙을 쉽게 찾을 수 있다.
depth는 현재 보고 있는 요소의 인덱스이고, sum은 현재까지의 수열의 합이다.
마지막 요소까지 보았을 때(선택을 했든 안 했든..), 그때의 합(sum)이 S와 같다면 ret를 1 증가시킨다.
이렇게 계산된 ret를 출력하는데, S == 0 이고 모든 요소를 선택하지 않는 경우는 예외 처리해주어야 한다.

728x90

'Algorithm' 카테고리의 다른 글

[Algorithm] 이분 탐색 유형 모음 (0)	2025.03.04
[Algorithm] 동적 프로그래밍(Dynamic Programming) 기초 유형 모음 (0)	2025.02.26
[Algorithm] 정수론 (0)	2025.01.03
[Algorithm] 최소 스패닝 트리(MST) 문제 (2)	2024.12.13
[Algorithm] 최단 경로 알고리즘 3가지 (2)	2024.12.11

순열(Permutation)

최적화 전

최적화 후

N과 M(1)

응용: 중복순열 - N과 M(3)

N개의 수 중에서 1 ~ M개의 수를 뽑는 수열 모두 구하기

조합(Combination)

최적화 전

최적화 후

부분집합(Subset)

코드

'Algorithm' 카테고리의 다른 글

티스토리툴바