[알고리즘/자바] 조합, 순열, 중복조합, 중복순열

알고리즘 문제를 접하다 보면 조합, 순열, 중복 조합, 중복순열을 필요로 하는 문제가 많다.

브루트 포스를 이용할 때 이러한 로직들을 많이 사용한다.

그래서 로직을 만들어놓고 사용하면 그때그때 필요한 로직을 갖다 쓸 수 있어서 문제 풀기에 용이하다. 

그래서 정리도 하고 알려도 줄 겸 이렇게 포스팅을 시작한다...

---

기본적으로 static 배열로 

	static int[] arr = { 1, 2, 3, 4, 5 };

선언했다고 생각하자.

 

조합

1,2,3,4,5 중에서 3개를 뽑는 것이다.  1,2,3과 1,3,2 가 똑같은 것으로 치는 것이다. 1,1,2는 조합으로 안친다.

 -> 총 개수 5개에서 3개를 뽑는 것이다.(순서는 상관없음.)

 

자바 코드

private static void makeCombination(int r, int[] temp, int current, int start) {
		if (r == current) {
			System.out.println(Arrays.toString(temp));
		} else {
			for (int i = start; i < arr.length; i++) {
				temp[current] = arr[i];
				makeCombination(r, temp, current + 1, i + 1);
			}
		}
	}

파라미터 정의

• r : 뽑고자 하는 개수
• temp : r개를 뽑는 결과값을 저장해놓는 배열
• current : 현재 개수를 저장해 놓는 값
• start : 그다음 반복문을 시작하는 값

코드 설명 : 조합을 재귀로 구현을 하였다. current 값을 늘려주면서 r값에 도달하면 temp를 출력하게 했다. start 값이 i + 1 인 이유는 나왔던 값이 또다시 반복되면 안 되기 때문.(예를 들어 1이 배열에 들어갔는데 1이 또 배열에 들어가게 되면 조합이 성립이 안되기 때문.)

 

---

중복 조합

1,2,3,4,5 중에서 중복을 포함해서 3개를 뽑는 것이다. 조합에서 1,1,2 같은 중복되는 것도 중복 조합으로 친다.

-> 총 개수 5개에서 중복을 포함해서 3개를 뽑는 것이다.

 

자바 코드

private static void makeOverlabCombination(int r, int[] temp, int current, int start) {
		if (r == current) {
			System.out.println(Arrays.toString(temp));
		} else {
			for (int i = start; i < arr.length; i++) {
				temp[current] = arr[i];
				makeOverlabCombination(r, temp, current + 1, i);
			}
		}
	}

파라미터 정의

• r : 뽑고자 하는 개수
• temp : r개를 뽑는 결과값을 저장해놓는 배열
• current : 현재 개수를 저장해 놓는 값
• start : 그다음 반복문을 시작하는 값

코드 설명 : 재귀로 구현하였다. current 값을 늘려주면서 r값에 도달하면 temp를 출력하게 했다. start 값이 i 인 이유는 나왔던 값이 또 나와도 되기 때문.

 

---

순열

1,2,3,4,5 중에서 순서를 생각해서 3개를 뽑는 것이다. 1,2,3과 1,3,2를 다른 것으로 친다. 

-> 총 개수 5개에서 3개를 순서를 고려해서 뽑는 것이다. ( 3개를 뽑아서 순서를 다르게 정렬하는 것으로도 볼 수 있다.)

 

자바 코드

private static void makePermutation(int r, int[] temp, int current, boolean[] visited) {
		if (r == current) {
			System.out.println(Arrays.toString(temp));
		} else {
			for (int i = 0; i < arr.length; i++) {
				if (!visited[i]) {
					visited[i] = true;
					temp[current] = arr[i];
					makePermutation(r, temp, current +1, visited);
					visited[i] = false;
				}
			}
		}
	}

파라미터 정의

• r : 뽑고자 하는 개수
• temp : r개를 뽑는 결과값을 저장해놓는 배열
• current : 현재 개수를 저장해 놓는 값
• visited : 방문 여부를 확인하는 배열

코드 설명 : 재귀로 구현하였다. 방문 여부를 구하는 visited로 방문 여부를 체크해서 방문했다면 배열에 넣지 않고 방문하지 않았다면 배열에 넣어서 순열을 구현했다.

 

---

중복 순열

1,2,3,4,5 중에서 순서를 고려해서, 중복을 포함한 3개를 뽑는 것이다. 1,2,1과 2,1,1을 다른 것으로 친다. 

-> 총 개수 5개에서 중복 포함, 순서를 고려해서 3개를 뽑는 것이다.

 

자바 코드

private static void makeOverlabPermutation(int r, int[] temp, int current) {
		if (r == current) {
			System.out.println(Arrays.toString(temp));
		} else {
			for (int i = 0; i < arr.length; i++) {
				temp[current] = arr[i];
				makeOverlabPermutation(r, temp, current + 1);
			}
		}
	}

파라미터 정의

• r : 뽑고자 하는 개수
• temp : r개를 뽑는 결과값을 저장해놓는 배열
• current : 현재 개수를 저장해 놓는 값
• visited : 방문 여부를 확인하는 배열

코드 설명 : 재귀로 구현하였다. 기존 순열의 코드에서 방문 여부만 제외해서 뽑게 되면 중복을 포함할 수 있다.

 

---

위와 같이 만든 로직들을 문제에 맞게 변형해서 사용한다면 알고리즘 문제에 조금 더 쉽게 접근할 수 있을 것이다.

다음 포스팅 때는 DFS, BFS, 백트래킹에 대해 다뤄볼 예정이다.