Algorithm 3일차

알고리즘에서 중복 순열을 활용할 수 있다.

중복 순열은 요소 중복이 허가되는 순열이다. 중복 순열을 재귀로 구현하면 아래와 같다.

public class Dice1 {
	static int N = 3;
	static int[] chase;
	static int total = 0;
	
	static void dupPermutate(int count) {
		if (count == N) {
			System.out.println(Arrays.toString(chase));
			total++;
			return;
		}
		
		for (int i = 1; i <= 6; i++) {
			chase[count] = i;
			dupPermutate(count + 1);
		}
		
	}
	
	
	public static void main(String[] args) {
		chase = new int[N];
		
		dupPermutate(0);
		System.out.println("총 횟수는 " + total + "입니다.");
	}
}

순열 코드에서 check를 안해도 되기 때문에 코드는 더 간단해진다.

알고리즘에서 조합을 활용할 수 있다.

조합은 서로 다른 것들 중 몇 개를 뽑는 것(순서가 없음)을 의미한다.
조합을 재귀로 구현하면 아래와 같다.

import java.util.Arrays;

public class Dice4 {
	static int N = 3;
	static int[] chase;
	static int total = 0;
	
	static void combination(int start, int count) {
		if (count == N) {
			System.out.println(Arrays.toString(chase));
			total++;
			return;
		}
		
		for (int i = start; i <= 6; i++) {
			chase[count] = i;
			combination(i+1, count+1); // 주의!!
		}
	}
	
	public static void main(String[] args) {
		chase = new int[N];
		
		combination(1, 0);
		System.out.println("총 횟수는 " + total + "입니다.");
	}
}

알고리즘에서 중복 조합을 활용할 수 있다.

중복 조합은 요소 중복이 허가되는 조합이다. 중복 조합을 재귀로 구현하면 아래와 같다.

import java.util.Arrays;

public class Dice4 {
	static int N = 3;
	static int[] chase;
	static int total = 0;
	
	static void combination(int start, int count) {
		if (count == N) {
			System.out.println(Arrays.toString(chase));
			total++;
			return;
		}
		
		for (int i = start; i <= 6; i++) {
			chase[count] = i;
			combination(i, count+1); // 주의!!
		}
	}
	
	public static void main(String[] args) {
		chase = new int[N];
		
		combination(1, 0);
		System.out.println("총 횟수는 " + total + "입니다.");
	}
}