제육's 휘발성 코딩
Published 2022. 2. 13. 15:48
[JAVA] - 순열과 조합 🔷 Java/Basic
반응형

완전 검색

image

순열(Permutation)

  • 서로 다른 n개 중 r개를 선택하는 과정에서 순서가 의미가 있는 경우 - nPr
  • 예 ) 5개의 도시 중 출발지와 도착지가 같은 최소 비용 거리

반복문

// {1, 2, 3}을 포함한 모든 순열 생성 : 3P3
// 동작 과정 1. 1~3 수 선택 시도, 2. 중복 수 필터링, 3. 다음 자릿수 선택 - 선택 이후 1,2,3 반복
for i from 1 to 3 // 처음 수 선택
  for j from 1 to 3 // 두번째 수 선택
    if j != i then // 첫번째와 두번째가 다르다면 
      for k from 1 to 3 // 세번 째 수 선택
        if k != i and k != j then // 세번째 수가 첫번째, 두번째와 다른 경우
          print i,j,k // 세 수 선택 
        end if
      end for
    end if
  end for
end for
  • 단점 : r중 반복문을 사용해야하므로 가변적인 순열에 대응할 수 없다.

재귀

//numbers[] : 순열 저장 배열 
//isSelected[] : 인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열
perm(cnt) // cnt : 현재까지 뽑은 순열 수의 개수 
    if cnt == 3 // 기저 조건 
    // 리턴
  else 
    for i from 1 to 3
      if isSelected[i] == true then continue // 기존 수 중복 체크
      numbers[cnt] <- i
      isSelected[i] <- true
      perm(cnt+1) // 다음 수 선택
      isSelected[i] <- false
    end for
  • 재귀를 사용하면 스택에 r개만큼 쌓아서 가변적 순열처리가 가능하다.
import java.util.Arrays;
import java.util.Scanner;

public class PermutationTest {
    static int N, R;
    static int[] input, numbers; // input : 입력수 배열, numbers : 선택수 배열
    static boolean[] isSelected;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();

        input = new int[N];
        numbers = new int[R];
        isSelected = new boolean[N];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        permutation(0);
    }

    // 현재 자리에 수 뽑기
    public static void permutation(int cnt) {
        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }
        // 입력받은 모든 수를 현재 자리에 넣어보기
        for (int i = 0; i < N; i++) {
            // 기존자리의 수들과 중복되는지 체크
            if (isSelected[i]) continue;
            numbers[cnt] = input[i];
            isSelected[i] = true;
            // 다음 수 뽑으러 가기
            permutation(cnt+1);
            isSelected[i] = false;
        }
    }
}

비트마스킹 - 순열

nPn -> N개의 원소로 만들 수 있는 모든 순열 생성 
input[] : 숫자 배열
numbers[] : 순열 저장 배열
perm(cnt, flag) // cnt : 현재까지 뽑은 순열 원소의 개수, flag : 선택된 원소에 대한 비트정보를 표현하는 정수
  if cnt == N 
    // 리턴
  else
    for i from 0 to N-1
      if (flag & 1 << i) != 0 then continue
      numbers[cnt] <- input[i]
      perm(cnt+1, flag | 1 << i)
    end for
end perm()
import java.util.Arrays;
import java.util.Scanner;

public class PermutationTest {
    static int N, R;
    static int[] input, numbers; // input : 입력수 배열, numbers : 선택수 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();

        input = new int[N];
        numbers = new int[R];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        permutation(0,0);
    }

    // cnt : 직전까지 뽑은 수 갯수, flag : 뽑힌 수들에 대한 플래그 비트열
    public static void permutation(int cnt, int flag) {
        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i = 0; i < N; i++) {
            if ((flag & 1 << i) != 0) continue;
            numbers[cnt] = input[i];
            permutation(cnt+1, flag | 1 << i);
        }
    }
}

NextPermutation

image

import java.util.Arrays;
import java.util.Scanner;

public class NextPermutationTest {
    static int N, input[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        input = new int[N];

        for (int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }

        Arrays.sort(input);

        do {
            System.out.println(Arrays.toString(input));
        }while (np());
    }

    private static boolean np() {

        // 1. 교환위치 찾기
        int i = N-1;
        while(i>0 && input[i-1] >= input[i]) --i;

        if (i==0) return false;

        // 2. 교환위치에 교환할 값 찾기
        int j = N-1;
        while(input[i-1] >= input[j]) --j;

        // 3. 교환위치와 교환할 값 교환하기
        swap(i-1,j);

        // 4. 교환위치 뒤(꼭대기)부터 맨 뒤까지 만들 수 있는 가장 작은 순열 생성 (오름차순 정렬)
        int k = N-1;
        while (i < k) {
            swap(i++, k--);
        }

        return true;
    }

    public static void swap(int i, int j) {
        int tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;
    }
}

조합

  • 서로 다른 n개 중 r개를 선택하는 과정에서 순서가 의미없는 경우
  • 5개의 도시 중 3개를 선택할 때 가장 숙박비가 비싼 3개의 도시

반복문

// 4C3 조합 - 순서가 의미가 없으므로 다음 수는 전수 +1 
for i from 1 to 4
  for j from i+1 to 4
    for k from j+1 to 4
      print i,j,k
    end for
  end for
end for

재귀

comb(cnt, start)
  if cnt == r
    // 리턴
  else
    for i from start to n-1
      numbers[cnt] <- input[i];
            comb(cnt+1,i+1)
    end for
end comb()
  • 다음 수는 전수+1부터 시작하게 하며, 순서가 의미가 없으므로 중복체크를 하지 않아도 된다.
import java.util.Arrays;
import java.util.Scanner;

public class CombinationTest {
    static int N,R;
    static int[] input, numbers;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();

        input = new int[N];
        numbers = new int[R];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        combination(0, 0);
    }

    public static void combination(int cnt, int start) {

        if (cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = start; i < N; i++) {
            numbers[cnt] = input[i];
            combination(cnt+1, i); // 다음 자리는 현재 뽑은 i의 다음수부터 시작하도록 전달
        }
    }
}

NextPermutation

image

import java.util.Scanner;

public class CombinationNPTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int[] input = new int[N];

        for (int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }

        int[] p = new int[N];
        // p배열에 0보다 큰 값으로 R개를 맨뒤부터 채운다.
        // 4C2 0011
        int cnt = 0;
        while(++cnt <= R) p[N-cnt] = 1;

        do {
            for (int i = 0; i < N; i++) {
                if (p[i] == 1) {
                    System.out.print(input[i] +" ");
                }
            }
            System.out.println();
        } while(np(p));
    }

    private static boolean np(int[] p) {
        int N = p.length;
        // 1. 교환위치 찾기
        int i = N-1;
        while(i>0 && p[i-1] >= p[i]) --i;

        if (i==0) return false;

        // 2. 교환위치에 교환할 값 찾기
        int j = N-1;
        while(p[i-1] >= p[j]) --j;

        // 3. 교환위치와 교환할 값 교환하기
        swap(p,i-1,j);

        // 4. 교환위치 뒤(꼭대기)부터 맨 뒤까지 만들 수 있는 가장 작은 순열 생성 (오름차순 정렬)
        int k = N-1;
        while (i < k) {
            swap(p,i++, k--);
        }

        return true;
    }

    public static void swap(int[] p ,int i, int j) {
        int tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
    }
}

중복 순열, 중복 조합 예제

import java.util.Arrays;
import java.util.Scanner;

public class DiceTest {
    static int N, numbers[], totalCount;
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 던진 주사위 횟수
        numbers = new int[N]; // 차례대로 던져진 주사위 눈의 수
        int M = sc.nextInt();
        switch (M) {
            case 1 : // 주사위 던지기1 : 중복순열
                dice1(0);
                break;
            case 2 : // 주사위 던지기2 : 순열
                dice2(0, new boolean[7]);
                break;
            case 3 :
                dice3(0,1);
                break;
            case 4 : // 주사위 던지기4 : 조합
                dice4(0,1);
                break;
            default:
                break;
        }
        System.out.println("총 경우의 수 : " + totalCount);
    }

    // 주사위 던지기 1 : 중복 순열
    public static void dice1(int cnt) {

        if(cnt == N) {
            totalCount++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = 1; i <= 6; i++) {
            numbers[cnt] = i;
            dice1(cnt+1);
        }
    }

    // 순열 : nPr
    public static void dice2(int cnt, boolean[] isSelected) {

        if(cnt == N) {
            totalCount++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = 1; i <= 6; i++) {
            if(isSelected[i]) continue;
            numbers[cnt] = i;
            isSelected[i] = true;

            dice2(cnt + 1, isSelected);

            isSelected[i] = false;
        }
    }

    // 중복조합 : nHr -> n+r-1Cr
    public static void dice3(int cnt, int start) {
        if (cnt == N) {
            totalCount++;
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i = start; i <= 6; i++) {
            numbers[cnt] = i;
            dice4(cnt+1, i);
        }
    }

    // 조합 : nCr
    public static void dice4(int cnt, int start) {

        if(cnt == N) {
            totalCount++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for (int i = start; i <= 6; i++) {
            numbers[cnt] = i;
            dice4(cnt+1, i+1);
        }
    }
}

부분 집합

  • 조합의 모든 경우의 수 (5C1, 5C2, ... , 5C5)에서 5C0 까지 포함된 경우
  • 냅백 알고리즘과 같은 다수의 중요 알고리즘이 최적의 부분 집합을 찾는 것
  • 원소의 개수가 n개일 때 공집합을 포함한 부분 집합의 개수는 2^n 개

반복문

// 1~3 집합의 모든 부분 집합 
FOR i 1 -> 0
  selected[i] <- i
  FOR j in 1 -> 0
      selected[2] <- j
      FOR k in 1 -> 0
          selected[3] <- k
          FOR m in 1 -> 3
              if selected[i] == 1 then
          print i
  • 부분 집합의 원소가 몇개가 될지 모르므로 반복문으로 미리 코드를 짤 수가 없다.

재귀

input[] : 숫자 배열
isSelected[] : 부분집합에 포함 / 비포함 여부를 저장한 배열
generateSubSet(cnt) // cnt : 현재까지 처리한 원소 개수 
  if (cnt == N) 
    // 리턴
  else 
    isSelected[cnt] <- true 
    generateSubSet(cnt+1) // 해당 원소를 선택한 경우
    isSelected[cnt] <- false
    generateSubSet(cnt+1) // 해당 원소를 선택하지 않은 경우 
end generateSubSet()
  • 간단하게 선택, 비선택으로 나누어 재귀를 호출한다.
import java.util.Scanner;

public class SubSetTest {
    static int N, input[];
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        input = new int[N];
        isSelected = new boolean[N];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        generateSubset(0);
    }

    public static void generateSubset(int cnt) { // 부분집합에 고려해야 하는 원소의 개

        if (cnt == N) {
            for (int i = 0; i < N; i++) {
                System.out.print((isSelected[i]?input[i]:"X")+" ");
            }
            System.out.println();
            return;
        }

        // 현재 원소를 선택
        isSelected[cnt] = true;
        generateSubset(cnt+1);
        // 현재 원소를 비선택
        isSelected[cnt] = false;
        generateSubset(cnt+1);
    }
}
반응형
저작자표시
profile

제육's 휘발성 코딩

@sasca37

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요! 맞구독은 언제나 환영입니다^^

검색 태그

이펙티브자바
자료구조
jpql
자바
JPA
자바스크립트
AOP
javascript
스프링
프로그래머스

티스토리툴바