찰떡개발자 코딩

이전부터 궁금했던 조합 알고리즘.

조합이란 ...? nCr n개의 숫자중 r개를 뽑아서 만들수있는 조합을 구한다....

예를 들어 [1, 2, 3] 이란 숫자 배열에서 만들수있는 조합은 [1, 2] [1, 3] [2, 3] [1,2,3] 이된다.

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

일단 기본적으로 알고리즘을 먼저 보자...

public class combination {
	public static void main(String[] args) {

		//ABCD 4개를 받아서 조합을 만든다.
		String[] arr = {"A", "B", "C", "D"};

		//자리수별 체크 1개뽑을때부터 n개 다 뽑을때까지
		//n개중에 i개 뽑기
		//2개부터 뽑자
		boolean[] visited = new boolean[arr.length]; //조합의 방문 여부 체크 boolean
		for (int i = 2; i < arr.length+1; i++) {
			combinations(arr,visited,0,i);
		}
	}

	static void combinations(String[] arr, boolean[] visited, int start, int count) {

		if(count==0) {
			print(arr,visited);
			return;
		}

		for (int i = start; i < arr.length; i++) {
			//방문했던것으로 재귀돌리고
			visited[i] = true;
			combinations(arr,visited,i+1,count-1);
			//다시 다음 번에 사용할 수 있도록 방문 취소한다.
			visited[i] = false;
		}
	}

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

추가로... 살짝 변형...!

문제 : 2차원 배열을 받고, 각 배열에서 만들수있는 조합과 만들어진 횟수를 Map으로 나열하고, 그 중 2번이상 만들어진 조합을 출력하라~ 

-> 내가 만든문제...ㅎ

알고리즘을 공부하다가 알게된 백트래킹을 사용해 보았다.

<백트레킹>

start 인덱스 기준으로 start보다 크면 뽑을 후보이며, 작으면 뽑을 후보에서 제외시킨다.

추가로 뽑을 갯수를 -1 씩 하면서 다 뽑을때까지 반복한다.!

public class combination {
	static HashMap<String,Integer> resultMap = new HashMap<String,Integer>();

	public static void main(String[] args) {

		String[][] arr = {{"A", "B", "C", "D"} , {"C" ,"D"}};

		//자리수별 체크 1개뽑을때부터 n개 다 뽑을때까지
		//n개중에 i개 뽑기
		//2개부터 뽑자
		for (int i = 0; i < arr.length; i++) {
			boolean[][] visited = new boolean[arr.length][arr[i].length]; //조합의 방문 여부 체크 boolean
			for (int j = 2; j < arr[i].length+1; j++) {
				combination(arr[i],visited[i],0,j);
			}
		}

		Iterator<Entry<String,Integer>> keys = resultMap.entrySet().iterator();
		ArrayList<String> list = new ArrayList<String>();

		while(keys.hasNext()) {
			Map.Entry<String, Integer> entry = keys.next();
			if(entry.getValue()>=2) {
				list.add(entry.getKey());
			}
		}
		System.out.println(resultMap);
		System.out.println(list);
		
	}

	static void combination(String[] arr, boolean[] visited, int start, int count) {

		if(count==0) {
			makeResult(arr,visited);
			return;
		}

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

	static void makeResult(String[] arr, boolean[] visited) {
		String result = "";

		for (int i = 0; i < visited.length; i++) {
	    	if (visited[i]) {
	    		result = result+arr[i];
	        }
	    }

	    if( resultMap.get(result) != null && resultMap.get(result)!=0) {
	    	int a = resultMap.get(result);
	     	resultMap.put(result,a+1);
	    }else {
	    	resultMap.put(result,1);
	    }
	}
}

결과 :

{AB=1, BC=1, CD=2, AC=1, BD=1, ABC=1, ACD=1, BCD=1, AD=1, ABD=1, ABCD=1}
[CD]

차근차근 더 확실하게 알아봐야겠다...! 한번으론 부족하다!

사람들이 많이 푸는 조합알고리즘을 한번 봐야겠다...!