[SW Expert Academy][Computational Thinking] 조합론 / 기초 알고리즘 프로그래밍 과제

링크

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPCwCKAAPw5UW6&subjectId=AV1lHB66AAwCFAb_

조합론 프로그래밍 과제

과제 1

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

class Main {
    public static List<int[]> makeCombinations(int[] arr,int n, int r){
        List<int[]> combinations=new ArrayList<int[]>();
        int[] combination=new int[r];
        makeCombination(arr,combination,0,0,r,combinations);
        
        return combinations;
    }
    public static void makeCombination(int[] arr,int[] combination,int start,int index,int r,List<int[]> combinations){
        if(index==r){
            combinations.add(combination.clone());
            return;
        }
        for(int i=start;i<=arr.length-r+index;i++){
            combination[index]=arr[i];
            makeCombination(arr,combination,i+1,index+1,r,combinations);
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int r=sc.nextInt();
        int[] arr=new int[n];
        for(int i=1;i<=n;i++){
            arr[i-1]=i;
        }
        List<int[]> answer=new ArrayList<>(); 
        answer=makeCombinations(arr,n,r);
        for(int i=0;i<answer.size();i++){
            int[] combination=answer.get(i);
            System.out.printf("(");
            for(int j=0;j<r;j++){
                System.out.printf(" %d ",combination[j]);
            }
            System.out.printf(")\n");
        }
    }
}

• 파이썬만 하다가 자바로 조합을 다루려니... 복잡하였다. 라이브러리에 파이썬은 그냥 있다는 사실이 새삼...
  52장의 카드에서 만들 수 있는 페어가 정확히 하나만 있는 5장의 조합을 모두 출력해야 하므로 즉 겹치지 않게 52장 중의 5개를 뽑는 조합을 구하라는 것과 일치한다. 그렇기에 조합의 모든 경우를 출력하기 위해서는 재귀를 이용하여 구할 수 있다. 각 케이스(즉 조합중 하나)를 구할 때 배열 arr에서 r개를 선택하기 때문에 index를 현재 우리가 채우는 케이스의 index로 두는 것이다. 즉 index가 1이면 5개중 3개를 뽑는 경우 중 첫번째를 뽑는 것이고 2이면 두번째 3이면 3번째를 뽑는 것이다. 이렇게 하나씩 뽑아가는 것을 표현한 것이 index이다. start는 현재 뽑는 카드의 범위의 시작점인 것이다. 그렇기 때문에 for문을 통해 시작을 i=start로 해두고 처음에는 start에 0이 들어간다. 그리고 끝점이 i<=arr.length-r+index가 되는데 전체범위에서 r개를 뽑기 때문에 r개를 뺀 이후로 시작점이 잡히면 뒤에서 뽑을 수 없을 정도로 좁아지므로 전체 갯수에서 빼는 것이다. 여기서 index를 한번 더 더하는데 그 이유는 이미 진행되는 정도를 더해주어야 이를 고려해서 r을 빼주는 것과 다르게 뒤에서의 범위를 앞에서 이미 뽑은 장만큼 늘려야 하기 때문이다.
  그렇게 뽑은 후, 다음 카드는 시작점이 현재 뽑은 카드보다 뒤이므로 i+1이 되고 채워넣는 카드의 번째의 수도 다음 번째로 넘어가기 때문에 index+1을 해준 후 다음 것을 뽑아주면 된다. 이렇게 재귀를 통한 반복문이 돌아가면 모든 경우가 들어가게 되고 이 때, 번째 수 즉 index가 r과 같아지면 하나의 조합의 케이스가 완성되므로 복사해서 전체 정답에 포함시키는 것이다.

과제 2