가끔 알고리즘 문제를 풀다보면 2차원 배열을 90도 회전시켜야 하는 문제가 있습니다.

2차원 배열을 90도, 180도, 270도 회전시키는 방법을 알아봅니다.


N * N 배열에서의 90도 회전

가로, 세로가 같은 n * n 배열에서는 좀더 쉽게 회전시킬 수 있습니다.

심지어 별도의 배열을 선언하지 않고 해당 배열의 값을 직접 회전시킬 수 있습니다.

아래 그림처럼 기준 선을 잡고 맞은편의 숫자들을 한번씩 교환해주면 됩니다.


Java Code

public void rotate(int[][] matrix) {
    int n = matrix.length;

    // reverse up and down
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - i - 1][j];
            matrix[n - i - 1][j] = temp;

        }
    }

    // reverse diagonally
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}



90도 회전

회전시키려는 arr 2차원 배열이 있습니다.

이 배열을 직사각형처럼 생각하면 90도 회전시켰을 때 가로, 세로가 바뀌게 됩니다.

따라서 가장 먼저 할 일은 배열의 n, m 을 바꾼 rotate 배열을 선언합니다.

그 후에 이중 for 문을 돌면서 rotate[i][j] = arr[n-1-j][i] 식으로

rotate 배열을 전부 채워주면 됩니다.


Java Code

// 90 rotate
static int[][] rotate(int[][] arr) {
    int n = arr.length;
    int m = arr[0].length;
    int[][] rotate = new int[m][n];

    for (int i = 0; i < rotate.length; i++) {
        for (int j = 0; j < rotate[i].length; j++) {
            rotate[i][j] = arr[n-1-j][i];
        }
    }

    return rotate;
}



90도, 180도, 270 도 회전

사실 90도 회전만 알아도 2번, 3번 반복으로 180도, 270도를 할 수 있지만

내친김에 나머지도 구현해보았습니다.

rotate 함수에서 degree 파라미터로 90, 180, 270 을 받아

회전시키는 함수입니다.


Java Code

static int[][] rotate(int[][] arr, int degree) {
    int[][] rotate;
    int n = arr.length;
    int m = arr[0].length;

    switch (degree) {
        case 90:
        case 270:
            rotate = new int[m][n];
            break;
        case 180:
            rotate = new int[n][m];
            break;
        default:
            throw new IllegalArgumentException();
    }

    for (int i = 0; i < rotate.length; i++) {
        for (int j = 0; j < rotate[i].length; j++) {
            switch (degree) {
                case 90:
                    rotate[i][j] = arr[n-1-j][i];
                    break;
                case 180:
                    rotate[i][j] = arr[n-1-i][m-1-j];
                    break;
                case 270:
                    rotate[i][j] = arr[j][m-1-i];
                    break;
            }
        }
    }

    return rotate;
}



전체 소스코드

class Main {
    public static void main(String[] args) {
        int[][] arr = {
            {1, 0, 0},
            {1, 1, 1},
            {1, 0, 1},
            {1, 0, 1}
        };

        print(arr);

        int[][] rotateArr;

        System.out.println("\n90");

        // 90 rotate
        rotateArr = rotate(arr, 90);
        print(rotateArr);

        System.out.println("\n180");

        // 180 rotate
        rotateArr = rotate(arr, 180);
        print(rotateArr);

        System.out.println("\n270");

        // 270 rotate
        rotateArr = rotate(arr, 270);
        print(rotateArr);

        System.out.println("\n360 (90 rotate)");

        // 90 rotate
        rotateArr = rotate(rotateArr);
        print(rotateArr);
    }

    static int[][] rotate(int[][] arr, int degree) {
        int[][] rotate;
        int n = arr.length;
        int m = arr[0].length;

        switch (degree) {
            case 90:
            case 270:
                rotate = new int[m][n];
                break;
            case 180:
                rotate = new int[n][m];
                break;
            default:
                throw new IllegalArgumentException();
        }

        for (int i = 0; i < rotate.length; i++) {
            for (int j = 0; j < rotate[i].length; j++) {
                switch (degree) {
                    case 90:
                        rotate[i][j] = arr[n-1-j][i];
                        break;
                    case 180:
                        rotate[i][j] = arr[n-1-i][m-1-j];
                        break;
                    case 270:
                        rotate[i][j] = arr[j][m-1-i];
                        break;
                }
            }
        }

        return rotate;
    }

    // 90 rotate
    static int[][] rotate(int[][] arr) {
        int n = arr.length;
        int m = arr[0].length;
        int[][] rotate = new int[m][n];

        for (int i = 0; i < rotate.length; i++) {
            for (int j = 0; j < rotate[i].length; j++) {
                rotate[i][j] = arr[n-1-j][i];
            }
        }

        return rotate;
    }

    static void print(int[][] arr) {
        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

출력

1 0 0 
1 1 1 
1 0 1 
1 0 1 

90
1 1 1 1 
0 0 1 0
1 1 1 0

180
1 0 1
1 0 1
1 1 1
0 0 1

270
0 1 1 1
0 1 0 0
1 1 1 1

360 (90 rotate)
1 0 0
1 1 1
1 0 1
1 0 1

'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 Collections 시간복잡도 (Big-O)  (0) 2019.04.02
자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27

출처 : https://gist.github.com/psayre23/c30a821239f4818b0709

 

Runtime Complexity of Java Collections

Runtime Complexity of Java Collections. GitHub Gist: instantly share code, notes, and snippets.

gist.github.com

 

'알고리즘 문제 > 공부' 카테고리의 다른 글

2차원 배열 회전 Rotate (Java)  (1) 2020.03.21
자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27

연습 문제 : https://bcp0109.tistory.com/39

 

입력과 마찬가지로 출력에도 여러가지 방법이 있습니다.

 

가장 간단한 방법으로는 System.out.print가 있지만 굉장히 느립니다.

 

보통 알고리즘 답은 많은 출력을 필요로 하지 않지만 여러 개의 테스트케이스에 대해서 출력을 할 때는 시간 초과가 발생할 수 있습니다.

 

따라서 많은 출력이 필요할 땐 BufferedWriter나 StringBuilder를 사용하는 것을 권장합니다.

 

이 둘의 특징은 데이터를 모아두었다가 한번에 출력합니다.

 

BufferedWriter의 경우네는 flush()를 사용하고

 

StringBuilder의 경우에는 자체적으로 String들을 이어붙인 것이기 때문에 StringBuilder를 출력하면 됩니다.

 

BufferedWriter를 사용하는 경우에는 입력할 때와 마찬가지로 throws Exception 을 붙여주거나 try 내에서 사용하시면 됩니다.

 

** 간단한 비교를 위해 10만개의 데이터를 출력해보았습니다.

 

소요시간은 StringBuilder가 가장 빨랐지만 사실 큰 차이는 없으므로 편한 것을 사용하시면 됩니다.

 

출력하는 데이터가 적다면 System.out을 사용하여도 괜찮습니다.

 

'알고리즘 문제 > 공부' 카테고리의 다른 글

2차원 배열 회전 Rotate (Java)  (1) 2020.03.21
자바 Collections 시간복잡도 (Big-O)  (0) 2019.04.02
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27

연습 문제 : https://bcp0109.tistory.com/39

 

자바 입력 방법은 Scanner과 BufferedReader가 있습니다.

 

Scanner가 쉽고 간단하여 저도 처음 문제를 풀 때는 사용하였지만, 사실 알고리즘 문제풀이에는 적절하지 않습니다.

 

많은 입력을 받아야 하는 경우에는 시간초과가 날 수 있기 때문입니다.

 

따라서 BufferedReader를 사용하는 것에 익숙해지는 것을 추천합니다.

 

** BufferedReader를 사용하기 위해서는 try문 내에서 사용하거나 메소드 끝에 throws Exception 구문을 붙여주셔야 합니다!

 

한 줄에 여러 개의 입력을 받는 경우에는 StringTokenizer 를 사용하면 됩니다.

 

'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 Collections 시간복잡도 (Big-O)  (0) 2019.04.02
자바 출력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27
조합 Combination (Java)  (7) 2018.12.27

위상정렬


위상 정렬은 그래프 정렬을 말합니다.


그래프의 순서를 정렬하기 때문에 조건이 있습니다.


위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 합니다.


  1. 말 그래도 두 노드 A, B 사이에 A -> B 같은 관계가 성립되어야 하며
  2. A -> B, B <- A 처럼 그래프들 사이에 사이클이 없어야 합니다.


위상정렬은 DFS를 사용하여 구현하거나 indegree 배열을 사용하여 구현 할 수 있습니다.


가장 주로 쓰이고 간단한 indegree 구현에 대해서 알아보겠습니다.



변수설명
List<List<Integer>> array그래프의 관계를 표현하기 위한 2차원 인접 리스트
int[] indegree해당 노드를 가리키는 간선 갯수를 담기 위한 배열
Queue<Integer> qindegree 값이 0 이 된 노드들을 담기 위한 Queue
Queue<Integer> resultQueue 에서 꺼내져 결과로 출력하기 위해 담는 결과 Queue



간단하게 그래프를 만들어보았습니다.


동그라미 안에 있는 숫자는 노드의 번호이며, 조그만 네모 안에 있는 숫자들은 자신을 가리키는 간선들의 갯수인 indegree 값입니다.



  1. 맨 처음 indegree 가 0 인 값들을 Queue 에 담고 시작합니다.

1



  1. Queue 에서 1을 빼주며 노드 1 에게 가리켜지는 다른 노드들의 indegree 값을 1 씩 감소시킵니다.


    사용한 노드와 간선은 지운다고 생각하면 이해하기 쉽습니다.


    아래 그림에서 화살표를 지우고 생각해보면 노드 2 와 노드 3은 자신을 가리키는 간선이 0 인 것을 알 수 있습니다.

2



  1. 그다음은 Queue 에서 순서대로 노드 2를 꺼냅니다.


    역시 노드 2와 연결된 간선들을 지우며 연결되어있는 노드들의 indegree 값을 감소시킵니다.


    노드 5 의 indegree 값이 0 이 되었으므로 Queue 에 넣어줍니다.

    Queue 가 전부 비워질 때까지 같은 과정을 반복하면 됩니다.

3



  1. Queue.pop(3) && Result.add(3)

4



  1. Queue.pop(5) && Result.add(5)

5



  1. Queue.pop(7) && Result.add(7)

6



  1. Queue.pop(4) && Result.add(4)

7



  1. Queue.pop(6) && Result.add(6)

8



이렇게 Queue가 비워지고 Result에 들어있는 값이 위상 정렬된 결과값입니다.


순서가 저렇게 나왔지만 사실 위상 정렬은 정해진 결과값이 없습니다.


2와 3의 위치가 바뀌어도 성립합니다.


중요한 점은 화살표가 가리키는 순서는 꼭 지켜져야 한다는 겁니다.


1 - 2 - 5 - 4 - 6
1 - 2 - 4 - 6
1 - 3 - 4 - 6
1 - 3 - 7


이 순서는 어떤 정렬 결과가 나오더라도 변하지 않을겁니다.



Java Code

import java.util.*;

public class TopologicalSort {
    static int n;
    static int e;

    public static void main(String[] args) {
        n = 7; // 정점 갯수
        e = 9; // 간선 갯수
        int[] indegree = new int[n + 1];
        List<List<Integer>> array = new ArrayList<List<Integer>>();

        for (int i = 0; i < n + 1; i++)
            array.add(new ArrayList<Integer>());

        // 간선 목록 v1 -> v2
        int[] v1 = {1, 1, 2, 4, 3, 3, 5, 2, 5};
        int[] v2 = {2, 3, 5, 6, 4, 7, 6, 4, 4};

        /**
         * 1. v1 -> v2 인접리스트 생성
         * 2. v2 를 가리키는 노드 갯수 indegree 증가
         */
        for (int i = 0; i < e; i++) {
            int c1 = v1[i];
            int c2 = v2[i];

            array.get(c1).add(c2);
            indegree[c2]++;
        }

        topologicalSort(indegree, array);
    }

    static void topologicalSort(int[] indegree, List<List<Integer>> array) {
        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> result = new LinkedList<Integer>();

        // 큐에 indegree 가 0 인 노드 담기
        for (int i = 1; i < n + 1; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        /**
         * 1. 큐에서 값을 꺼내며 해당 노드가 가리키는 노드의 indegree 를 1 감소
         * 2. 만약 indegree가 0 이 된다면 큐에 넣기
         * 3. 큐가 빌때까지 반복
         */
        while (!q.isEmpty()) {
            int node = q.poll();
            result.offer(node);

            for (Integer i : array.get(node)) {
                indegree[i]--;

                if (indegree[i] == 0) {
                    q.offer(i);
                }
            }
        }

        System.out.println(result);
    }
}


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
부분집합 PowerSet (Java)  (2) 2018.12.27
조합 Combination (Java)  (7) 2018.12.27
순열 Permutation (Java)  (11) 2018.12.27

부분집합


배열의 모든 부분집합을 구합니다.


배열 [1, 2, 3] 이 있다면 부분집합은


[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

입니다.


뭔가 떠오르지 않나요?


바로 조합이 떠오릅니다.


저번에 포스팅했던 n 개 중에서 r 개를 순서 없이 뽑는 조합에서 r 에 대한 for 문을 돌리면 구할 수 있습니다.


하지만 단순히 부분집합을 확인하기 위한 용도라면 훨씬 빠르고 효율적인 코드가 있습니다.


부분집합 역시 구하는 방법이 여러가지 있습니다.




조합을 이용한 구현

조합  포스팅을 확인하시면 됩니다.




재귀를 이용한 구현

조합을 구할 때와 비슷하게 구현을 하면 됩니다.


조합에서는 길이가 r 일 때를 구하기 위해 여러가지 조건을 걸었지만 부분집합에서는 필요없습니다.

  1. 현재 인덱스를 포함하는 경우
  2. 현재 인덱스를 포함하지 않는 경우

두 가지로 경우에 대해서 모두 확인한 후에 현재 인덱스가 n 이 되면 출력합니다.



Java Code

static void powerSet(int[] arr, boolean[] visited, int n, int idx) {
    if(idx == n) {
        print(arr, visited, n);
        return;
    }
 
    visited[idx] = false;
    powerSet(arr, visited, n, idx + 1);
 
    visited[idx] = true;
    powerSet(arr, visited, n, idx + 1);
}


Result

3
2
2 3
1
1 3
1 2
1 2 3




비트를 이용한 구현

비트연산에 대한 이해가 있다면 구현할 수 있습니다.


n 이 3이라고 할 때 1 << n 은 1000(2) 입니다.


첫번째 for 문에서 i 는 1 << n 전까지 증가하니까 111(2) 까지 증가합니다.


즉 i 


000
001
010
011
100
101
110
111

이렇게 증가합니다.


한번 쓱 보니 비트 자체만으로도 부분 집합이 형성되었습니다.


j 를 통해서

001
010
100

위 숫자들과 AND 연산을 통해서 1 인 비트들을 인덱스처럼 사용할 수 있습니다.



Java Code

static void bit(int[] arr, int n) {
    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();
    }
}


Result

1
2
1 2
3
1 3
2 3
1 2 3




전체 소스코드

public class PowerSet {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int n = 3;
        boolean[] visited = new boolean[n];

        powerSet(arr, visited, n, 0);
        bit(arr, n);
    }

    static void powerSet(int[] arr, boolean[] visited, int n, int idx) {
        if (idx == n) {
            print(arr, visited, n);
            return;
        }

        visited[idx] = false;
        powerSet(arr, visited, n, idx + 1);

        visited[idx] = true;
        powerSet(arr, visited, n, idx + 1);
    }

    static void bit(int[] arr, int n) {
        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();
        }
    }

    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i] == true)
                System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
조합 Combination (Java)  (7) 2018.12.27
순열 Permutation (Java)  (11) 2018.12.27

조합


조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말합니다.

예를 들어 [1, 2, 3] 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면

[1, 2]
[1, 3]
[2, 3]

이렇게 3 개가 나옵니다.

순열을 뽑았을 때 나오는 [2, 1] [3, 1] [3, 2] 등은 중복이라서 제거됩니다.

부분 집합처럼 이해하시면 됩니다.

여러 가지 방법이 있지만 핵심은 하나입니다.

배열을 처음부터 마지막까지 돌며

  1. 현재 인덱스를 선택하는 경우
  2. 현재 인덱스를 선택하지 않는 경우

이렇게 두가지로 모든 경우를 완전탐색 해주시면 됩니다.


변수설명
arr조합을 뽑아낼 배열
output조합에 뽑혔는지 체크하는 배열
n배열의 길이
r조합의 길이


순열과 달리 조합은 r 을 유지할 필요가 없으므로 숫자를 하나 뽑을때마다 r 을 하나씩 줄여줍니다.

r == 0 일 때가 r 개의 숫자를 뽑은 경우입니다.


백트래킹 이용하여 구현

start 변수는 기준입니다.

start 인덱스를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start 보다 크면 뽑을 후보가 됩니다.

예를 들어 [1, 2, 3] 배열이 있고 start 가 0 부터 시작합니다.

함수에 들어오면 먼저 i 가 start 부터 시작하는 for 문에 들어갑니다.

만약 0 인덱스인 1을 뽑는다면 visited[i] 는 true 가 되고 뽑지 않는다면 visited[i] 는 false 입니다.

1을 선택한 경우와 선택하지 않은 경우 둘 다 봐야합니다.

하지만 더이상 1은 고려 대상이 아니기 때문에 다음 for 문은 무조건 i+1 부터 시작해주어야 합니다.


Java Code

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
        visited[i] = true;
        combination(arr, visited, i + 1, n, r - 1);
        visited[i] = false;
    }
}


Result

[4 개 중에서 1 개 뽑기]
1
2
3
4

[4 개 중에서 2 개 뽑기]
1 2
1 3
1 4
2 3
2 4
3 4

[4 개 중에서 3 개 뽑기]
1 2 3
1 2 4
1 3 4
2 3 4

[4 개 중에서 4 개 뽑기]
1 2 3 4



재귀 이용하여 구현

depth 변수를 사용합니다.

depth 변수는 현재 인덱스라고 생각하면 됩니다.

현재 인덱스를 뽑는다면 visited[depth] = true

뽑지 않는다면 visited[depth] = false

이렇게 진행하면 됩니다.

역시 마찬가지로 뽑은 경우와 뽑지 않은 경우 모두 봐야하고, 그 때 이전에 본 값들은 더이상 고려 대상이 아니기 때문에 depth 은 무조건 1 씩 증가합니다.

depth == n 이 되면 모든 인덱스를 다 보았으므로 재귀를 종료합니다.


Java Code

// 재귀 사용
// 사용 예시 : comb(arr, visited, 0, n, r)
static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
    if (r == 0) {
        print(arr, visited, n);
        return;
    }

    if (depth == n) {
        return;
    }

    visited[depth] = true;
    comb(arr, visited, depth + 1, n, r - 1);

    visited[depth] = false;
    comb(arr, visited, depth + 1, n, r);
}


Result

[4 개 중에서 1 개 뽑기]
1
2
3
4

[4 개 중에서 2 개 뽑기]
1 2
1 3
1 4
2 3
2 4
3 4

[4 개 중에서 3 개 뽑기]
1 2 3
1 2 4
1 3 4
2 3 4

[4 개 중에서 4 개 뽑기]
1 2 3 4


저는 개인적으로 재귀를 별로 좋아하지 않아서 백트래킹 방법을 주로 사용하는 편입니다.

어느 쪽이든 성능차이가 거의 없으니 편하고 익숙한 방법을 사용하시면 됩니다.



전체 소스코드

/**
 * 조합 : n 개 중에서 r 개 선택
 */
public class Combination {
    public static void main(String[] args) {
        int n = 4;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];

        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            comb(arr, visited, 0, n, i);
        }

        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            combination(arr, visited, 0, n, i);
        }
    }

    // 백트래킹 사용
    // 사용 예시 : combination(arr, visited, 0, n, r)
    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    // 재귀 사용
    // 사용 예시 : comb(arr, visited, 0, n, r)
    static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }
        
        if (depth == n) {
            return;
        }

        visited[depth] = true;
        comb(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        comb(arr, visited, depth + 1, n, r);
    }

    // 배열 출력
    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}




2차원 배열에서 조합

2차원 배열에서 조합을 뽑아야 할 때가 있어서 만들어보았습니다.


Java Code

/**
 * 2차원 배열에서 조합을 구할때 사용하는 방법
 * 완전 탐색 할때 사용
 */

public class Combination2 {
    static int n = 3;
    static int m = 3;

    public static void main(String[] args) {
        int[][] map = new int[n][m];

        print(map);
        comb(map, 0, 0);
    }

    static void comb(int[][] map, int start, int depth) {
        if (depth == 3) {
            print(map);
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (map[x][y] == 0) {
                map[x][y] = 1;
                comb(map, i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }

    static void print(int[][] map) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27
순열 Permutation (Java)  (11) 2018.12.27

순열


순열이란 n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말합니다.


예를 들어 [1, 2, 3] 이라는 3 개의 배열에서 2 개의 숫자를 뽑는 경우는


[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

이렇게 6 개가 됩니다.




1. Swap 을 이용한 순열

첫번째는 swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법입니다.


배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 합니다.


depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고


depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행합니다.



example1



간단하고 코드도 깔끔하게 나오지만 순열들의 순서가 보장되지 않습니다.


예를 들어 3개의 숫자 중 3개의 값을 뽑는 순열을 만들 때


[3, 1, 2]
[3, 2, 1]

위 순서대로 나와야 하는데


[3, 2, 1]
[3, 1, 2]

이렇게 나옵니다.



Java Code

// 순서 없이 n 개중에서 r 개를 뽑는 경우
// 사용 예시: permutation(arr, 0, n, 4);
static void permutation(int[] arr, int depth, int n, int r) {
    if (depth == r) {
        print(arr, r);
        return;
    }
 
    for (int i=depth; i<n; i++) {
        swap(arr, depth, i);
        permutation(arr, depth + 1, n, r);
        swap(arr, depth, i);
    }
}
 
static void swap(int[] arr, int depth, int i) {
    int temp = arr[depth];
    arr[depth] = arr[i];
    arr[i] = temp;
}


Result

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2




2. Visited 배열을 이용한 순열

두번째로는 visited 배열을 이용하는 방법입니다.


1번과 달리 사전식으로 순열을 구현할 수 있습니다.


변수설명
arrr 개를 뽑기 위한 n 개의 값
output뽑힌 r 개의 값
visited중복해서 뽑지 않기 위해 체크하는 값


위 3개의 값이 포인트입니다.


DFS를 돌면서 모든 인덱스를 방문하여 output 에 값을 넣습니다.


이미 들어간 값은 visited 값을 true 로 바꾸어 중복하여 넣지 않도록 합니다.


depth 값은 output 에 들어간 숫자의 길이라고 생각하시면 됩니다.


depth 의 값이 r 만큼 되면 output 에 들어있는 값을 출력하면 됩니다.



example2



Java Code

// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// 사용 예시: perm(arr, output, visited, 0, n, 3);
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
    if (depth == r) {
        print(output, r);
        return;
    }
 
    for (int i=0; i<n; i++) {
        if (visited[i] != true) {
            visited[i] = true;
            output[depth] = arr[i];
            perm(arr, output, visited, depth + 1, n, r);       
            output[depth] = 0; // 이 줄은 없어도 됨
            visited[i] = false;;
        }
    }
}


Result

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1




전체 소스코드

/** * 순열 : n 개 중에서 r 개를 순서있게 뽑기 * 시간복잡도: O(n!) */ public class Permutation { public static void main(String[] args) { int n = 3; int[] arr = {1, 2, 3}; int[] output = new int[n]; boolean[] visited = new boolean[n]; perm(arr, output, visited, 0, n, 3); System.out.println(); permutation(arr, 0, n, 3); } // 사전순으로 순열 구하기 // 사용 예시: perm(arr, output, visited, 0, n, 3); static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) { if (depth == r) { print(output, r); return; } for (int i = 0; i < n; i++) { if (visited[i] != true) { visited[i] = true; output[depth] = arr[i]; perm(arr, output, visited, depth + 1, n, r); visited[i] = false; } } } // 순열 구하기 // 사용 예시: permutation(arr, 0, n, 4); static void permutation(int[] arr, int depth, int n, int r) { if (depth == r) { print(arr, r); return; } for (int i = depth; i < n; i++) { swap(arr, depth, i); permutation(arr, depth + 1, n, r); swap(arr, depth, i); } } static void swap(int[] arr, int depth, int i) { int temp = arr[depth]; arr[depth] = arr[i]; arr[i] = temp; } // 배열 출력 static void print(int[] arr, int r) { for (int i = 0; i < r; i++) System.out.print(arr[i] + " "); System.out.println(); } }


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27
조합 Combination (Java)  (7) 2018.12.27

+ Recent posts