조합이란 ?
서로 다른 n개중에 r개의 숫자를 순서를 고려하지않고 뽑는 경우를 말합니다.
조합의 정의를 아는것을 가정하에 프로그래밍을 하기전, 사전조사 작업을 해볼 필요성이 보입니다.
- 길이 n만큼의 배열이 필요합니다
- n개의 배열중 r개를 뽑을수있게끔 길이 r만큼의 배열이 필요합니다.
여기서 두가지 버젼이 존재합니다 - 반복문을 사용할것인가?
- 반목운을 사용하지않을것인가? 로 구분짓습니다.
자 사전조사 작업이 끝났으니 본격적으로 프로그래밍 시점으로 조합을 바라봅시다.
1. 조합은 순서도 중요하지않고, 중복또한 싫어하는 성격을 띕니다.
- 순서가 중요하지 않는것은 다른위치의 값들이 똑같은건 안된다는 의미입니다.
- 1,2 와 2,1는 안됩니다.
- 중복를 허용하지않는다는 것은 중복의 방문여부를 생각해야된다는 의미입니다.
다른위치의 값들이 똑같은게 안된다는 의미를 다시 생각해봅시다
예시로 순열로 [1,2,3] ,[1,3,2] ,[2,1,3] ,[2,3,1] ,[3,1,2,], [3,2,1] 가있습니다.
조합의 시선으로 [1,2,3] = [1,3,2] =[2,1,3] = [2,3,1] = [3,1,2] = [3,2,1] 입니다.
그렇다면 조합은 해당하는 숫자 내에서 사전순으로 나열을 한번만 하게된다면 그 앞을 볼필요 없다는 의미가됩니다.
2. 졸라맨들은 선배 졸라맨의 칸은 볼수없습니다.
방금까지 우리는 해당하는 숫자 내에서 나열을 한번만 하게된다면 그 앞을 볼필요없다는 의미를 알게 되었습니다.
즉 후배 졸라맨들은 선배 졸라맨을 건들수 없다는 의미가 되는것입니다.
오류가있습니다!! cnt가 있는곳은 idx로, idx가 있는곳은 cnt로 생각해주세요
그림을 보시면 r개의 각각 졸라맨들은 자신의 선배 졸라맨들이 시작하는 칸은 건들지 못하게됩니다.
3. 프로그래밍 관측에서 어떻게 더 생각할수있을까?
저희는 방금 조합의 성격, 조합의 특징을 알아내었습니다.
하지만 코드로 구현하기는 아직 어렵지만 우리는 지금 1,2번과 함께 유추할수있는것들을 나열해 볼수있습니다.
- 길이 n만큼의 배열이 필요합니다
이를 cards라는 배열로 가정합니다 - n개의 배열중 r개를 뽑을수있게끔 길이 r만큼의 배열이 필요합니다.
이를 arr라는 배열로 가정합니다. - 후배 졸라맨은 선배 졸라맨을 만질수 없게끔 만들어야합니다.
- 중복을 피할수있게끔 방문 여부를 가져야합니다.
- n개의 배열에서 r개만큼 가져가야하고 3번과4번을 적용시켜야합니다.
이를 idx라 가정합니다. - r개의 배열은 n개의 배열에서 주는 값을 넣어야합니다.
이를 cnt로 가정해야합니다.
4. 그림으로 이해 해봅시다.
cards[cnt]는 졸라맨이 가져야 하는값,
cnt는 몇개를 가져갔는지에대한 변수,
arr[idx]는 졸라맨이 가져온값을 실제로 넣을수있는 배열입니다.
idx는 r개에 넣어야하기위한 인덱스 값입니다.
loop 1
하나의 졸라맨의 역할은 한칸을 가져가는것이 끝입니다.
두번째 졸라맨을 호출하겠습니다.
loop 2
2번째 졸라맨은 내 선배 졸라맨[1번] 을 보고 그 바로 앞의 인덱스를 가져갑니다.
loop 3
idx가 꽉 차게된다면 [n개 중에 r개를 채웠다면?] 출력해주는 졸라맨은 출력을 해주고 퇴근을합니다.
loop 4
그럼 2번째 졸라맨은 남은 cnt가 있기때문에 퇴근을 하지않고 찾아나섭니다. 자연스레 졸라맨은 선배졸라맨 칸을 제외하고 모든칸을 봅니다.
loop 5
idx가 꽉차게 되었으니 새로운 출력졸라맨이 생기고 출력을하고 퇴근을합니다.
loop 6
이때 출력졸라맨과 2번째 졸라맨의 할일은 끝났으니 퇴근을 하게될겁니다
아직 1번째 졸라맨의 역할은 끝나지 않았습니다 1번째 졸라맨은 다시 2번 인덱스값을 가져오게됩니다.
loop 7
새로운 2번째 졸라맨입니다! 다시 제할일을 해야된다고 생각하고 선배졸라맨 칸 그 이후부터 값을 보게됩니다.
loop 8
모든 칸이 채워져있다면 새로운 출력 졸라맨이 출력을 다시하고 퇴근할것입니다
그 후
그 이후론 출력 졸라맨과 2번째 졸라맨이 퇴근하는 동시에 1번쨰 졸라맨은 퇴근하지않고 3번째 값을 가져오게되지만,
3개중에 2개를 가져올수없는 구조가 만들어지면서 최종 [1,2], [1,3] , [2,3]을 출력하게될것입니다.
자 ! 다 끝났습니다 이제 프로그래밍 구현을 해볼까요?
프로그래밍 구현
import java.util.Arrays;
public class Test_조합 {
static int N = 5, R = 3;
static String[] cards = {"A","B","C","D","E"};
static String[] result = new String[R];
//idx는 졸라맨이 cnt가 만들어준 값을 갖고있는것에대한 인덱스, cnt는 졸라맨이 갖고와야하는값에대한 인덱스입니다.
comb(0,0);
static void comb(int idx, int cnt) {
//기저조건 졸라맨이 다 R개칸이 꽉 채워졌습니다.
if(idx == R) {
System.out.println(Arrays.toString(result));
return;
}
//나는 선배 졸라맨을 보지않을테니 i는 cnt부터 시작할것입니다
//cnt는 곧 졸라맨이 가져올 첫번째 값입니다.
for(int i=cnt; i<N; i++) {
result[idx] = cards[i];
comb(idx+1, i+1);
}
}
}