문제 링크 : https://www.acmicpc.net/problem/2252


위상 정렬 문제입니다.


위상 정렬에 대한 포스팅 https://bcp0109.tistory.com/21


노드 갯수 N, 간선 갯수 M 을 받은 다음에 간선의 가중치를 입력받아서 위상 정렬하면 간단하게 해결됩니다.


result 큐를 사용해서 결과값을 저장했지만 q 에 대한 while 문이 도는 동안 그대로 출력해도 상관없습니다.


위상정렬


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


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


위상 정렬이 가능하려면 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

Problem


종이 위에 테트로미노 블록을 하나 놓아서 각 칸에 놓인 숫자 합의 최대값을 구하는 문제입니다.



Solution

테트로미노 블록에 들어있는 모든 숫자를 더한 값 중 최대값을 찾는 문제입니다.


DFS 로 깊이 4 까지 탐색하면 간단하게 풀 수 있습니다.


대신 블록 중에 ㅗ 모양은 DFS 돌려도 나오지 않으므로 따로 예외처리를 해주시면 됩니다.


  1. 맵의 꼭지점일 때
  2. 맵의 테두리일때
  3. 일반적일 때


이렇게 세 가지 경우로 나누어서 각각 하드코딩 해주었습니다.



Java Code

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

class Main {
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static int max = 0;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = stoi(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = true;
                dfs(i, j, 0, 0);
                visited[i][j] = false;
                another(i, j);
            }
        }

        System.out.println(max);
    }

    // dfs로 깊이가 최대 4인 경우가 테트로미노, 단 ㅗ 모양은 없음
    static void dfs(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (visited[nx][ny] != true) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, depth + 1, sum + map[nx][ny]);
                    visited[nx][ny] = false;
                }
            }
        }
    }

    // ㅗ 모양을 찾는다. 가운데 있는 좌표를 기준으로 세 방향을 탐색한다.
    static void another(int x, int y) {
        // 1. 맵의 꼭지점일때는 ㅗ 모양 불가능
        if ((x == 0 || x == n - 1) && (y == 0 || y == m - 1)) return;

        int sum = map[x][y];

        // 2. 맵의 테두리일때는 모양이 하나
        if (x == 0)
            sum += map[x][y - 1] + map[x][y + 1] + map[x + 1][y];
        else if (x == n - 1)
            sum += map[x][y - 1] + map[x][y + 1] + map[x - 1][y];
        else if (y == 0)
            sum += map[x - 1][y] + map[x + 1][y] + map[x][y + 1];
        else if (y == m - 1)
            sum += map[x - 1][y] + map[x + 1][y] + map[x][y - 1];
        else {
        // 3. 맵의 테두리가 아닐 때는 4 개의 모양을 비교
            sum = Math.max(sum, map[x][y] + map[x + 1][y] + map[x][y - 1] + map[x][y + 1]);
            sum = Math.max(sum, map[x][y] + map[x - 1][y] + map[x][y - 1] + map[x][y + 1]);
            sum = Math.max(sum, map[x][y] + map[x][y + 1] + map[x - 1][y] + map[x + 1][y]);
            sum = Math.max(sum, map[x][y] + map[x][y - 1] + map[x - 1][y] + map[x + 1][y]);
        }

        max = Math.max(max, sum);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
 
n = m = 0
arr = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
maxVal = 0
 
## 최대 4개짜리 dfs로 전부 탐색하면됨
def dfs(x, y, visited, count, sumVal):
    global maxVal
 
    if count == 4:
        if maxVal < sumVal:
            maxVal = sumVal
        return
 
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
 
        if 0 <= nx and nx < n and 0 <= ny and ny < m:
            if visited[nx][ny] == False:
                visited[nx][ny] = True
                dfs(nx, ny, visited, count + 1, sumVal + arr[nx][ny])
                visited[nx][ny] = False
        
## ㅗ 모양은 dfs로 탐색이 안돼서 따로 처리해줌
## 가운데일 때를 기준으로 네방향 탐색
def fuck(x, y):
    global maxVal
    sumVal = arr[x][y]
    
    ## x, y가 모서리면 ㅗ 모양은 아예 불가능
    if x == 0:
        if y == 0 or y == m-1:
            return
    elif x == n-1:
        if y == 0 or y == m-1:
            return
 
    ## x나 y가 가장자리에 있으면 ㅗ 모양은 하나밖에 안나옴
    if x == 0:
        sumVal += arr[x+1][y] + arr[x][y-1] + arr[x][y+1]
    elif x == n-1: 
        sumVal += arr[x-1][y] + arr[x][y-1] + arr[x][y+1]    
    elif y == 0:
        sumVal += arr[x][y+1] + arr[x-1][y] + arr[x+1][y]    
    elif y == m-1:
        sumVal += arr[x][y-1] + arr[x-1][y] + arr[x+1][y]
    else:  
        sumlist = []
        sumlist.append(sumVal + arr[x+1][y] + arr[x][y-1] + arr[x][y+1])
        sumlist.append(sumVal + arr[x-1][y] + arr[x][y-1] + arr[x][y+1])
        sumlist.append(sumVal + arr[x][y+1] + arr[x-1][y] + arr[x+1][y])
        sumlist.append(sumVal + arr[x][y-1] + arr[x-1][y] + arr[x+1][y])
        sumVal = max(sumlist)
    
    if maxVal < sumVal:
        maxVal = sumVal
 
def solve():
    visited = [[False]*m for i in range(n)]
 
    for i in range(n):
        for j in range(m):
            fuck(i, j)
            visited[i][j] = True
            dfs(i, j, visited, 1, arr[i][j])
            visited[i][j] = False
 
 
if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
 
    for i in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))
        
    solve()
    print(maxVal)


Problem


수열과 연산자가 주어졌을 때 조합하여 만들수 있는 최소값과 최대값을 구하는 문제입니다.



Solution

연산자가 배치될 수 있는 모든 경우의 수를 구한 후에 MAXMIN 값을 구하는 문제입니다.


단순하게 재귀로 풀수도 있지만 순열을 이용하여 풀었습니다.


모든 경우의 수를 봐야 하고 순서는 중요하지 않기 때문에 간단하게 swap 으로 순열을 구현하였습니다.


  1. operator 배열을 만들어서 각 연산자 갯수에 대해 1, 2, 3, 4로 넣기
  2. operator 배열에 대해서 순열 돌리기
  3. 순열로 인한 경우의 수 마다 연산값을 계산하여 maxmin 값 구하기
  4. 출력


위와 같은 순서로 진행하였습니다.


파이썬은 좀더 예전에 풀었던 거라 연산자를 아예 +, -, *, / 로 배열에 저장했는데 순열을 구한 뒤 계산한다는 전체적인 로직은 같습니다.



Java Code

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

class Main {
    static int n;
    static int[] a;
    static int[] operator;
    static int max = -987654321;
    static int min = 987654321;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        n = stoi(br.readLine());
        a = new int[n];
        operator = new int[n - 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = stoi(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int idx = 0;
        for (int i = 0; i < 4; i++) {
            int temp = stoi(st.nextToken());

            // 1:덧셈, 2:뺄셈, 3:곱셈, 4:나눗셈
            for (int j = 0; j < temp; j++) {
                if (i == 0) operator[idx++] = 1;
                else if (i == 1) operator[idx++] = 2;
                else if (i == 2) operator[idx++] = 3;
                else operator[idx++] = 4;
            }
        }

        // 계산 시작
        permutation(0);
        System.out.println(max);
        System.out.println(min);
    }

    // 순열 구하기
    static void permutation(int depth) {
        if (depth == n - 1) {
            calculate();
            return;
        }

        for (int i = depth; i < n - 1; i++) {
            swap(depth, i);
            permutation(depth + 1);
            swap(depth, i);
        }
    }

    static void swap(int i, int j) {
        int temp = operator[i];
        operator[i] = operator[j];
        operator[j] = temp;
    }

    // 각 순열에 대해서 연산 후 max, min 값 찾기
    static void calculate() {
        int result = a[0];

        for (int i = 0; i < n - 1; i++) {
            if (operator[i] == 1) result += a[i + 1];
            else if (operator[i] == 2) result -= a[i + 1];
            else if (operator[i] == 3) result *= a[i + 1];
            else result /= a[i + 1];
        }

        min = Math.min(min, result);
        max = Math.max(max, result);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
def setOperatorList(N, add, sub, mul, div):
    operator = []
 
    for i in range(N-1):
        if add > 0:
            operator.append("+")
            add -= 1
        elif sub > 0:
            operator.append("-")
            sub -= 1
        elif mul > 0:
            operator.append("*")
            mul -= 1
        elif div > 0:
            operator.append("/")
            div -= 1
 
    return operator
 
 
def solve(N, A, operator):
    result = A[0]
 
    for i in range(N-1):
        if operator[i] == "+":
            result = result + A[i+1]
        elif operator[i] == "-":
            result = result - A[i+1]
        elif operator[i] == "*":
            result = result * A[i+1]
        elif operator[i] == "/":
            result = int(result / A[i+1])
 
    return result
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    A = [i for i in list(map(int, sys.stdin.readline().split()))]
    add, sub, mul, div = map(int, sys.stdin.readline().split())
    
    operatorList = setOperatorList(N, add, sub, mul, div)
 
    operators = itertools.permutations(operatorList)
 
    maxVal = -sys.maxsize
    minVal = sys.maxsize
 
    for operator in operators:
        result = solve(N, A, operator)
 
        if result < minVal:
            minVal = result
        
        if result > maxVal:
            maxVal = result
 
    print(maxVal)
    print(minVal)


문제 링크 : https://www.acmicpc.net/problem/1182


부분집합을 이용하는 문제입니다.


부분집합에 대한 이전 포스팅 https://bcp0109.tistory.com/17


원소를 일일히 기억할 필요가 없어서 코드가 훨씬 간단해집니다.


배열 인덱스의 처음부터 끝까지 진행하며


1) arr[idx] 값을 더한 경우

2) arr[idx] 값을 더하지 않은 경우


두 가지 경우로 나누어서 탐색합니다.


인덱스의 끝에 도달하면 지금까지 더한 값과 S 를 비교하여 일치할 경우 count++ 해주시면 됩니다.



** 주의사항 **


부분집합을 구하다보면 공집합이 생깁니다.


만약 S 가 0 이라면 공집합때문에 아무 값도 더하지 않아서 0 인 경우도 카운트 하게 됩니다.


이 부분에 대해서만 예외처리를 해주시면 됩니다.


파이썬에서는 조합에 대한 라이브러리를 제공해주기 때문에 그냥 n번만큼 조합을 돌렸습니다.


부분집합


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


배열 [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

Problem


일곱 난쟁이의 키가 주어졌을 때 합이 100 이 되도록 하는 일곱 난쟁이의 키를 출력하는 문제입니다.



Solution

문제를 살펴보면 일곱명의 합을 전부 다 구해봐야 할 것 같지만 사실은 두명만 구하면 됩니다.


주어진 난쟁이는 9명, 실제 난쟁이는 7명입니다.


9명 중에서 2명의 키를 뺀 값이 100이기 때문에


2명의 합 = 9명의 합 - 100


위 식을 이루는 2명을 구하면 됩니다.


2명의 합을 O(n) 에 구하는 방법은 정렬 후에 양 끝 인덱스부터 차례로 합을 구해서 비교하면 됩니다.


두 값의 합이 target 보다 작다면 왼쪽 인덱스를 하나 증가시키고, target 보다 크다면 오른쪽 인덱스를 하나 감소시킵니다.



Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] height = new int[9];
        int sum = 0;

        for (int i=0; i<9; i++) {
            int input = Integer.parseInt(br.readLine());
            height[i] = input;
            sum += input;
        }

        Arrays.sort(height);

        eraseTwoHeight(height, sum - 100);

        for (int i=0; i<9; i++) {
            if (height[i] != 0) {
                bw.write(height[i] + "\n");
            }
        }
        bw.flush();
    }

    static void eraseTwoHeight(int[] arr, int target) {
        int left = 0;
        int right = 8;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                arr[left] = 0;
                arr[right] = 0;
                return;
            }
            
            if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
    }
}


조합


조합이란 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

+ Recent posts