학습용 공간

그래프 문제는 문제에 나와 있는 상황을 그래프로 모델링해서 푼다.

어떻게 문제의 상황을 그래프로 만드는지가 관건!

# 그래프는 G = (V, E)로 나타낸다.

V는 vertex(정점) E는 Edge(간선)의 약자

# 사이클 : 정점 A에서 다시 정점 A로 돌아오는 경오

# 단순 경로, 단순 사이클 (Simple Path, Simple Cycle)

- 경로, 사이클에서 같은 정점을 2번 이상 방문하지 않는 경로, 사이클이다

- 일반적으로 경로, 사이클로 적혀있을 경우, 이를 의미한다.

# 방향 있는 그래프, 방향 없는 그래프 (Directed/Undirected Graph)

- 간선들에 방향이 있으면 directed, 없으면 undirected이다.

# 가중치(Weight)

- 간선의 값이다.

- 주로 간선에 해당하는 거리, 시간, 비용을 나타내는데 사용된다.

- 별도로 설정되어 있지않으면 기본적으로 모든 간선의 가중치는 1이다.

# 차수(Degree)

- 정점과 연결되어 있는 간선정의 개수

- directed 그래프에서는 이를 in-degree, out-degree로 정점에 들어오는 간선인지, 정점에서 나가는 간선인지 구분하기도 한다.

# 그래프를 어떻게 저장하는가? -> 정점과 간선을 저장해야한다.

- 정점 : 정점의 개수를 통해 저장한다. 

   정점이 총 6개라면 각 정점 이름을 0, 1, 2, 3, 4, 5로 설정해서 저장

- 간선 : 정점과 같이 개수로 저장되면 만들 수 있는 그래프의 경우의 수가 다수 존재한다 -> 해당 방법 부적합

위와 같은 간선의 특징 때문에 간선을 저장하는 방법이 포인트가 된다.

그리고 한 정점 x와 연결된 간선을 효율적으로 찾는 구조로 그래프를 저장하는 것이 중요하다.

# 그래프 저장 방법

 1. 인접 행렬

 2. 인접 리스트

# 인접 행렬

정점의 개수를 V라고 했을 때 

V*V 크기의 2차원 배열을 사용하여 그래프를 저장한다.

간선이 있으면, A[i][j] = 1 (가충치가 있다면 가충치의 값)

간선이 없으면, A[i][j] = 0으로 값을 할당한다.

(i, j는 간선 1개를 잇는 2개의 정점을 나타낸다.)

인접 행렬을 사용하면 그래프를 저장하는데 V^2 만큼의 공간이 요구된다.

한 정점에 연결된 모든 정점을 구하는 시간복잡도는 O(V)이다.

# 인접 리스트

리스트를 이용해서 그래프를 저장한다.

A[i] = j 꼴로 각 정점에 연결되어 있는 정점들을 저장하는 방식으로 간선을 저장한다.

(i, j는 각 정점들을 의미한다.)

리스트 자료구조를 사용하는 이유는 각 정점에 몇 개의 정점이 연결되어 있는지 알 수 없기 때문에

개수 제한 없이 원소 추가가 가능한 리스트를 사용하는 것이다.)

일반적으로 LinkedList을 이용해서 구현하며

C++은 vector, JAVA는 Arraylist, Python은 List[] 자료구조를 사용해서 구현한다.

# 공간 복잡도

인접 행렬 : O(V^2)

인접 리스트 : O(E)

(V는 정점의 개수, E는 간선의 개수)

 - 인접 행렬은 존재하지 않는 간선에 대한 메모리도 할당되지만, 

   인접 리스트는 존재하는 간선에 대해서만 메모리가 할당되기 때문이다.

(인접 리스트의 경우, 한 정점에 연결된 모든 간선을 찾는 시간복잡도는 O(차수)이다.

인접 리스트가 인접 행렬보다 시간적, 공간적으로 효율적이기 때문에

인접 리스트가 더 빈번하게 사용된다.

cf) 임의의 두 정점 사이에 간선이 존재하는지 구하는 경우에만 인접 행렬이 더 유리하다.

    인접 행렬은 각 정점을 잇는 간선을 저장하는 메모리에 접근하여 값이 0이 아닌지 확인하면 되지만(O(1))

    인접 리스트는 해당 정점에 연결된 모든 정점들을 확인해야(O(E)) 이를 판별할 수 있기 때문이다. 

다음 코드는 백준 13023번 문제를 해결하기 위해

인접 행렬, 인접 리스트, 간선 리스트를 사용한 코드이다.

import java.util.*;
class Edge { // 간접 리스트를 위한 클래스
    int from, to;
    Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 사람 수
        int m = sc.nextInt(); // 관계 수

        boolean[][] a = new boolean[n][n]; // 인접 행렬 구현
        ArrayList<Integer>[] g = (ArrayList<Integer>[]) new ArrayList[n]; // 인접 리스트 구현
        ArrayList<Edge> edges = new ArrayList<Edge>(); // 간접 리스트 구현
        for (int i=0;i<n;i++) { // 인접 리스트는 각 정점마다 연결된 간선을 저장하므로
            g[i] = new ArrayList<>(); // 각 정점에 대해 리스트를 할당
        }
        for (int i=0; i<m; i++) {
            // 친구 관계는 양방향 관계이므로 양 방향으로 간선을 배정해야 한다.
            // 간선 리스트에 관계 저장
            int from = sc.nextInt();
            int to = sc.nextInt();
            edges.add(new Edge(from, to));
            edges.add(new Edge(to, from));
            // 인접 행렬에 관계 저장
            a[from][to] = a[to][from] = true;
            // 인접 리스트에 관계 저장
            g[from].add(to);
            g[to].add(from);
        }
        // 관계는 양방향이므로 입력된 관계*2를 해주어야 간선들의 총 개수가 된다.
        m *= 2;
        // 아래는 2개의 간선들에 대한 관계 파악해줌
        for (int i=0;i<m;i++) {
            for (int j=0;j<m;j++) {
                // 간선리스트 사용
                int A = edges.get(i).from;
                int B = edges.get(i).to;
                int C = edges.get(j).from;
                int D = edges.get(j).to;
                // B-C 친구 관계 여부를 간선 리스트로 확인
                // 서로 다른 두 간선이 연결되어 있는지 확인
                // A-B, C-D가 친구일 때 B-C가 친구인지 확인하는 것
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    // A==B이면 edges i는 간선이 아님
                    // A==C 또는 A==D는 간선 i와 j가 정점 1개를 공유하는 간선이라는 것이다.
                    // (서로 다른 정점 4개를 연결하는 간선이 아닌 것임)
                    continue; // 위 조건에 해당하면 A-B, C-D가 친구일 때 B-C가 친구인지 확인할 수 없으므로 continue (정점 4개에 대한 관계가 아니게 되기 때문)
                }
                // 인접 행렬 사용
                if (!a[B][C]) continue; // A-B, C-D 에서 B-C 관계도 성립하지 않는다면 continue
                // 인접 리스트 사용
                for (int E : g[D]) { // D 정점과 연결된 정점들이 E로 들어온다.
                    if (A == E || B == E || C == E || D == E) continue;
                    // 연결된 정점이 A, B, C, D와 같다면 이는 중복되는 간선이 들어온 것이므로 continue
                    // (D-E 관계에 해당하지 않는다는 것)
                    // 위 조건들을 모두 통과하면 A-B-C-D-E 관계가 존재한다는 것이다.
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        // 위 모든 쌍의 간선들을 확인했음에도 불구하고 모두 조건문에 걸려 continue 처리되어
        // 해당 코드에 다다르면 A-B-C-D-E 관계가 성립하지 않는다는 것이다.
        System.out.println(0);
    }
}

문제 출처 : https://www.acmicpc.net/problem/13023

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] num = new int[n][m];
        for (int i=0; i<n; i++) {
            String s = sc.next();
            for (int j=0; j<m; j++) {
                num[i][j] = s.charAt(j) - '0'; // char형을 int 형으로 바꾸는 방법
            }
        }
        // 비트마스크 - 브루트포스
        // 각 칸을 가로로 놓을지 세로로 놓을지 모든 경우의 수를 확인
        int ans = 0;
        for (int i=0;i<(1<<(n*m));i++) {
            int sum = 0;
            // 가로로 놓는 경우
            for (int j=0;j<n;j++) {
                int cur = 0; // 현재 이어진 가로칸들로 구성된 수
                for (int k=0;k<m;k++) {
                    int index = j*m+k; // 2차원 배열을 1차원 배열로 보았을 때, i행 j열은 앞에 i*m+(j-1)개의 원소들이 있기 때문
                    if ((i&(1<<index)) == 0) { // 가로이면
                        cur = cur*10 + num[j][k];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum+=cur;
            }
            // 세로로 놓는 경우
            for (int j=0;j<m;j++) {
                int cur = 0;
                for (int k=0;k<n;k++) {
                    int index = k*m+j;
                    if ((i&(1<<index)) != 0) { // 세로이면
                        cur = cur*10 + num[k][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            ans = Math.max(ans, sum);
        }
        System.out.println(ans);
    }
}

문제 출처 : https://www.acmicpc.net/problem/14391

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] num = new int[n];
        for (int i=0;i<n;i++) {
            num[i] = sc.nextInt();
        }
        // 비트마스크 - 브루트포스
        // 만들 수 있는 부분 집합들의 경우의 수들을 정수로 표현했음 (공집합 제외)
        // 1부터 2^n까지
        int cnt = 0; // 부분 수열의 합이 같은 경우의 수를 세기 위한 변수

        for (int i=1;i<(1<<n);i++) { // 만들 수 있는 모든 부분 집합들에 대해 반복
            int sum = 0;
            for (int j=0;j<n;j++) {
                if((i&(1<<j)) != 0) { // 정수로 표현한 부분 집합 i에 j가 들어있다면
                    sum += num[j];
                }
            }
            if (sum == s) { // 해당 부분집합 i에 들어있는 모든 정수들을 더한 값이 s와 같으면
                cnt+=1;
            }
        }

        System.out.println(cnt);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1182

다음 순열을 구하는 알고리즘을 사용하여 구현했다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = i+1;
        do {
            for (int i=0;i<n;i++) {
                sb.append(seq[i] + " ");
            }
            sb.append("\n");
            seq = next_permutation(seq);
        } while (seq != null);
        System.out.print(sb);
    }

    // 다음 순열(permutation) 구하는 알고리즘(메소드)
    // 1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 내림차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j>=i이면서 A[j]>A[i-1]을 만족하는 가장 작은 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 큰 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 오름차순으로 만들어줌 -> 해당 자리 기준 첫 순열로 만듬)
    static int[] next_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] < seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int minJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (indexI < 1) break;
            if (seq[indexI-1] < seq[j]) {
                if (minJ == -1 || seq[j] < minJ) {
                    minJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        Arrays.sort(tempArr);
        for (int i=indexI;i<seq.length;i++) seq[i] = tempArr[i-indexI];

        return seq;
    }
}

문제 출처 : https://www.acmicpc.net/problem/10974

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = sc.nextInt();
        int[] ans = prev_permutation(seq);
        if (ans == null) System.out.println(-1);
        else {
            for (int i=0;i<ans.length;i++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }

    // 이전 순열(permutation) 구하는 알고리즘(메소드)
    // 다음 순열을 구하는 알고리즘에서 부들호들만 반대로 바꾸어서 구현해주면 된다.
    // 1. A[i-1] > A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 오른차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j<=i이면서 A[j]<A[i-1]을 만족하는 가장 큰 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 작은 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 내림차순으로 만들어줌 -> 해당 자리 기준 마지막 순열로 만듬)
    static int[] prev_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] > seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int maxJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (seq[indexI-1] > seq[j]) {
                if (maxJ == -1 || seq[j] > maxJ) {
                    maxJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        int k = seq.length-indexI-1;
        for (int i=indexI;i<seq.length;i++) {
            seq[i] = tempArr[k];
            k-=1;
        }
        return seq;
    }
}

문제 출처 : https://www.acmicpc.net/problem/10973

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = sc.nextInt();
        int[] ans = next_permutation(seq);
        if (ans == null) System.out.println(-1);
        else {
            for (int i=0;i<ans.length;i++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }

    // 다음 순열(permutation) 구하는 알고리즘(메소드)
    // 1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 내림차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j>=i이면서 A[j]>A[i-1]을 만족하는 가장 작은 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 큰 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 오름차순으로 만들어줌 -> 해당 자리 기준 첫 순열로 만듬)
    static int[] next_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] < seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int minJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (indexI < 1) break;
            if (seq[indexI-1] < seq[j]) {
                if (minJ == -1 || seq[j] < minJ) {
                    minJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        Arrays.sort(tempArr);
        for (int i=indexI;i<seq.length;i++) seq[i] = tempArr[i-indexI];

        return seq;
    }
}

문제 출처 : https://www.acmicpc.net/problem/10972

# 브루트 포스 : 모든 경우의 수를 고려하는 방식이다.

# 순열 : 임의의 수열을 각자 다른 순서로 섞어 세우는 경우의 수들을 의미

 - 순서를 고려하는 문제에 사용되기 좋다.
 - 크기가 n인 수열에서 서로 다른 순열은 총 n!개가 있다.
ex) A = [1, 2, 3]
순열들 : 123, 132, 213, 231, 312, 321 (사전순으로 나열함)
모든 순서를 다 고려해야하는 문제에서 순열이 사용된다. 

(그러므로 순열을 사용하는 것은 브루트 포스의 일종이라고 할 수 있다.)

순열을 문제에 응용하기 위해서는 특정 순열에서 다음 순열을 구하는 알고리즘이 필요하다.
C++과 파이썬의 경우에는 다음 순열을 구하는 알고리즘이 자체적으로 구현되어 있지만,  자바에는 없다.

(자바에서는 직접 구현해주어야 한다.)

ex) N=4이고 A = [1, 2, 3, 4]이면 
순열은 총 4!(24)개
1234 2134 ...
1243 2143
1324 2314
1342 2341
1423 2413
1432 2431

순열들은 앞자리수부터 사전순으로 나열됨.
앞이 1인 모든 경우 -> 앞이 2인 모든 경우 -> 앞이 3인 모든 경우 -> ...

# 첫번째 순열과 마지막 순열의 특성
첫 순열 : 1234 - 오름차순임
마지막 순열 : 4321 - 내림차순임

ex )  7236541의 다음 순열 구하기 
723 / 6541 - 6541은 내림차순임 (내림차순이라는 것은 해당 자리에서 시작 기준 마지막 순열이라는 뜻)
그러므로 해당 순열의 다음 순열은 72?????다 된다.
다음 순열은 3 뒤에 위치한 수 중 3과 가장 적은 차이로 큰 수가 ? 중 첫자리에 오게 된다.
3 뒤의 6541 중 위 조건에 해당하는 수는 4이다.
(이를 찾는 시간복잡도 = O(N))
마지막 순열 다음은 첫 순열이 오게 되므로
72 / 4 / 1356 (1356은 오름차순으로 해당 자리 기준의 첫 순열이다.)
(첫 순열 만드는 것도 시간복잡도가 O(N)이다.)

그러므로 7236541의 다음 순열은 7241356이다.

위 과정을 4개의 단계들로 정리하면 (i는 내림차순 부분의 첫 자리 인덱스라고 할 때)

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다. 

   (뒤에 내림차순의 수만 남는 첫번째 자리를 구하기)

2. j>=i이면서 A[j]>A[i-1]을 만족하는 가장 작은 j를 찾는다. 

   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 큰 값을 찾기)

3. A[i-1]과 A[j]를 swap한다.

4. A[i]부터 순열을 뒤집는다. 

   (i자리부터 오름차순으로 만들어줌 -> 해당 자리 기준 첫 순열로 만듬)

1과 2는 O(n), 3은 O(1), 4는 O(n)
그러므로 총 시간 복잡도는  O(n) + O(n) + O(n) + O(n) = O(n)이다.

모든 순열을 구하기 위해서는 첫 순열부터 마지막 순열에 다다를 때까지(n!-1번) 위 알고리즘(O(n))을 반복해주어야 한다.
그러므로 모든 순열을 구하는 총 시간복잡도는 O(n*n!)이 된다.

팩토리얼 값은

3! = 6,

... ,

10! = 3,628,800 (3천만~)

11! = 39,916,800 (약 4억)

이므로 

순열은 수열의 크기의 입력이 11보다 작은 경우에 주로 사용된다.

(이보다 크면 모든 순열을 고려하는데 이미 적어도 4초 이상이 걸리므로 좋지 않음)

# 다음 순열을 구하는 알고리즘 (마지막 순열이 입력으로 들어오면 -1 출력)

 - next_permutation 메소드가 해당 알고리즘을 구현한 메소드이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = sc.nextInt();
        int[] ans = next_permutation(seq);
        if (ans == null) System.out.println(-1);
        else {
            for (int i=0;i<ans.length;i++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }

    // 다음 순열(permutation) 구하는 알고리즘(메소드)
    // 1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 내림차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j>=i이면서 A[j]>A[i-1]을 만족하는 가장 작은 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 큰 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 오름차순으로 만들어줌 -> 해당 자리 기준 첫 순열로 만듬)
    static int[] next_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] < seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int minJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (indexI < 1) break;
            if (seq[indexI-1] < seq[j]) {
                if (minJ == -1 || seq[j] < minJ) {
                    minJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        Arrays.sort(tempArr);
        for (int i=indexI;i<seq.length;i++) seq[i] = tempArr[i-indexI];

        return seq;
    }
}

# 이전 순열을 구하는 알고리즘 (다음 순열을 구하는 알고리즘에서 부등호들을 모두 반대로 바꾸어주면 됨)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] seq = new int[n];
        for (int i=0;i<n;i++) seq[i] = sc.nextInt();
        int[] ans = prev_permutation(seq);
        if (ans == null) System.out.println(-1);
        else {
            for (int i=0;i<ans.length;i++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }

    // 이전 순열(permutation) 구하는 알고리즘(메소드)
    // 다음 순열을 구하는 알고리즘에서 부들호들만 반대로 바꾸어서 구현해주면 된다.
    // 1. A[i-1] > A[i]를 만족하는 가장 큰 i를 찾는다.
    //   (뒤에 오른차순의 수만 남는 첫번째 자리를 구하기)
    // 2. j<=i이면서 A[j]<A[i-1]을 만족하는 가장 큰 j를 찾는다.
    //   (i 뒤에 있는 수들 중 i자리 값과 차이가 가장 적게 작은 값을 찾기)
    // 3. A[i-1]과 A[j]를 swap한다.
    // 4. A[i]부터 순열을 뒤집는다.
    //   (i자리부터 내림차순으로 만들어줌 -> 해당 자리 기준 마지막 순열로 만듬)
    static int[] prev_permutation(int[] seq) {
        int indexI = 0;
        // 1단계 (i 찾기)
        for (int i=seq.length-1;i>0;i--) {
            if (seq[i-1] > seq[i]) {
                indexI = i;
                break;
            }
        }
        if (indexI == 0) {
            return null;
        }
        // 2단계 (j 찾기)
        int maxJ = -1;
        int indexJ = indexI;
        for (int j=indexI;j<seq.length;j++) {
            if (seq[indexI-1] > seq[j]) {
                if (maxJ == -1 || seq[j] > maxJ) {
                    maxJ = seq[j];
                    indexJ = j;
                }
            }
        }
        // 3단계 (swap)
        int temp = seq[indexI-1];
        seq[indexI-1] = seq[indexJ];
        seq[indexJ] = temp;

        // 4단계 (순열 뒤집기)
        int[] tempArr = new int[seq.length-indexI];
        for (int i=indexI;i<seq.length;i++) tempArr[i-indexI] = seq[i];
        int k = seq.length-indexI-1;
        for (int i=indexI;i<seq.length;i++) {
            seq[i] = tempArr[k];
            k-=1;
        }
        return seq;
    }
}

import java.util.*;

public class Main {
    static int[] nums;
    static int[] ans;
    static int[] cnt;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        nums = new int[n]; // 중복되는 수를 1개로 정리한 수열
        ans = new int[m]; // 결과 저장할 배열
        cnt = new int[n]; // 각 수열의 수의 중복이 몇 개가 있는지 저장한 배열
        int[] temp = new int[n];
        for (int i=0;i<n;i++) {
            temp[i] = sc.nextInt();
        }
        Arrays.sort(temp);
        int x = temp[0];
        int index = 0;
        int c = 1;
        for (int i=1;i<n;i++) {
            if (x == temp[i]) {
                c+=1; // 중복되는 수 있음
            } else { // 중복되는 수가 더 이상 없고, 새로운 수가 들어오면
                nums[index] = x; // 해당 수를 배열에 저장하고
                cnt[index] = c; // 같은 수가 총 몇개가 있었는지 저장
                c = 1; // 다음 수의 검사를 위해 1로 초기화
                index+=1; // 다음 수로 접근 할 수 있게 인덱스로 사용하는 변수 +1
                x = temp[i]; // 다음 수를 검사하기 위해 x에 자장
            }
        }
        // 마지막 수는 배열에 저장 처리가 안되므로 반복문 밖에서 따로 처리
        nums[index] = x;
        cnt[index] = c;
        n = index+1; // 인덱스+1을 해주어야 중복을 제거한 수들의 총 개수가 된다.
        makeSeq(n, m, 0);
        System.out.print(sb);
    }
    // 브루트 포스
    static void makeSeq(int n, int m, int index) {
        if (index == m) {
            for (int x : ans) {
                sb.append(x + " ");
            }
            sb.append("\n");
            return;
        }
        for (int i=0;i<n;i++) {
            if (cnt[i] > 0) {
                ans[index] = nums[i];
                cnt[i]-=1;
                makeSeq(n, m, index+1);
                cnt[i]+=1;
            }
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/15663

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

public class Main {
    static int[] ans;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        ans = new int[M];
        printSequence(0, N, M);
        bw.flush();
        bw.close();
    }

    // 브루트 포스
    static void printSequence(int index, int n, int m) throws IOException {
        if (m == index) { // 재귀함수의 기저조건 : 마지막 자리 인덱스의 수까지 구하면 수열 1개 완성
            for (int x : ans) {
                bw.write(x + " ");
            }
            bw.write("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            ans[index] = i; // 해당 차례의 인덱스에 수를 널기
            printSequence(index + 1, n, m); // 다음 인덱스 자리에 올 숫자들을 확인
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/15651

import java.util.*;

public class Main {
    static boolean[] used;
    static int[] ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        used = new boolean[N+1];
        ans = new int[M];
        printSequence(0, 1, N, M);
    }

    // 브루트 포스
    static void printSequence(int index, int start, int n, int m) {
        if (m == index) { // 재귀함수의 기저조건 : 마지막 자리 인덱스의 수까지 구하면 수열 1개 완성
            for (int x : ans) {
                System.out.print(x + " ");
            }
            System.out.println();
            return;
        }
        for (int i=start;i<=n;i++) {
            if (used[i] == false) { // 수를 사용하지 않은 경우에만 확인
                ans[index] = i; // 해당 차례의 인덱스에 수를 널기
                used[i] = true; // 중복 확인용
                printSequence(index+1, i+1, n, m); // 다음 인덱스 자리에 올 숫자들을 확인
                used[i] = false; // 위 재귀가 끝나면 해당 수가 들어가는 경우들은 모두 고려한 것임
            }
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/15650

import java.util.*;

public class Main {
    static boolean[] used;
    static int[] ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        used = new boolean[N+1];
        ans = new int[M];
        printSequence(0, N, M);
    }

    // 브루트 포스
    static void printSequence(int index, int n, int m) {
        if (m == index) { // 재귀함수의 기저조건 : 마지막 자리 인덱스의 수까지 구하면 수열 1개 완성
            for (int x : ans) {
                System.out.print(x + " ");
            }
            System.out.println();
            return;
        }
        for (int i=1;i<=n;i++) {
            if (used[i] == false) { // 수를 사용하지 않은 경우에만 확인
                ans[index] = i; // 해당 차례의 인덱스에 수를 널기
                used[i] = true; // 중복 확인용 
                printSequence(index+1, n, m); // 다음 인덱스 자리에 올 숫자들을 확인
                used[i] = false; // 위 재귀가 끝나면 해당 수가 들어가는 경우들은 모두 고려한 것임
            }
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/15649

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        // 브루트 포스
        // n의 최대값은 1억인데 그러면 수가 너무 많다.
        // 모든 경우를 고려하지 않고, 1의자리는 자리수를 1증가, 10의 자리는 2증가, 100의 자리는 3증가, ...
        // 하는 특성을 이용한다.
        int digits = (int)(Math.log10(num)+1); // 몇자리수인지 구하기
        int len = 0;
        if (digits < 2) { // 한자리수가 들어왔을 때
            len+=num;
        } else { // 두자리수 이상일 때
            len += (num - Math.pow(10, digits-1) + 1)*digits;
            digits-=1;
            for (int i=0;i<digits;i++) {
                len+=9*Math.pow(10, i)*(i+1);
            }
        }
        System.out.println(len);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1748