CS/알고리즘
[알고리즘] 순열(permutation), 조합(Combination), 중복순열
ChaeHing
2023. 3. 23. 23:06
순열(permutation)
- 요소 n개 중에 r개를 선택하여 순서에 상관 있게 뽑는 경우의 수
- 순서에 상관이 있다는것은 알파벳 3개를 뽑을때 [ A, B, C ]와 [B, A, C] 는 다르다
- 뽑은 요소가 같아도 순서가 다르면 다른것
- 요소가 중복되면 안된다.
- nPr = n! / (n - r)!
- 5장에서 3장을 뽑는다면 5P3
- 5 * 4 * 3 * 2 * 1 / 2 * 1
- 120 / 2 = 60
자바 순열 템플릿 (Template)
//뽑을 요소들이 담긴 리스트 n
//뽑을 갯수 r
//결과를 담을 리스트
ArrayList<Integer[]> result = new ArrayList<>();
boolean[] visited = new boolean[n.size()]; // 요소 사용 여부 체크용
return permtation(r, n, visited, result, new Integer[]{}, 0) // 재귀함수 호출
// 재귀함수
public permtation(int r(뽑을 개수), ArrayList<Integer[]> n (뽑을 요소들 리스트),
boolean[] visited, ArrayList<Integer[]> result(최종결과),
Integer[] tmp(임시배열), int depth(깊이 조절) ){
if( depth == r ) // 깊이가 r(뽑는갯수)만큼 도달하면 (재귀 종료)
{
result.add() // 리스트에 추가
return
}
// 뽑을 요소 크기 만큼 반복
for(int i=0; i<n.size(); i++){
//해당 요소를 방문하지 않았다면
if(!visited[i]) {
//방문 여부 체크
visited[i] = true;
//해당 요소를 임시 배열에 넣는다.
tmp[i] = n.get(i);
// 재귀함수 호출, 뎁스를 높여서
result = permtation(r, n, visited, result, tmp,depth + 1);
// 한번 재귀를 순회후, 반복문을 다시 실행하기 위해 false;
visited[i] = false;
}
}
return result;
}
}
중복순열(permutation with repetition)
- 순열과 같이 요소 n개 중에 r개를 선택하여 순서에 상관 있게 뽑는 경우의 수
- 뽑은 요소가 같아도 순서가 다르면 다른것
- 요소의 중복을 허용 한다.
- 알파벳 3개를 뽑을때 [ A, A, A], [ A, B, B ] 같이 요소를 중복으로 뽑을 수 있다.
- n π r = n^r
- 5장에서 3장을 뽑는다면
- 5 * 5 * 5 = 125
// 중복수열
// 수열 템플릿에서 중복체크 부분만 빼줘서 사용 (같은 요소 가능)
// 뽑을 요소들이 담긴 리스트 n
// 뽑을 갯수 r
//결과를 담을 리스트
ArrayList<Integer[]> result = new ArrayList<>();
return permtation(r, n, reulst, new Integer[]{}, 0) // 재귀함수 호출
// 재귀함수
public permtation(int r(뽑을 개수), ArrayList<Integer[]> n (뽑을 요소들 리스트),
ArrayList<Integer[]> result(결과를 담을 그릇) ,int[] tmp(임시배열),
int depth(깊이 조절) ){
if( depth == r ) // 깊이가 r(뽑는갯수)만큼 도달하면 (재귀 종료)
{
result.add(tmp) // 결과 리스트에 추가
return result;
}
// 뽑을 요소 크기 만큼 반복
for(int i=0; i<n.size(); i++){
//해당 요소를 넣는다.
// 임시 배열에
tmp[i] = n.get(i);
// 재귀함수 호출, 뎁스를 높여서
result = permtation(r, n, result, tmp, depth + 1);
}
}
return result;
}
}
조합(Combination)
- 요소 n개 중에 r개를 선택하여 순서에 상관 없이 뽑는 경우의 수
- 순서에 상관이 없다는것은 [ A, B, C ] 와 [ B, A, C ] 는 같다.
- 뽑은 요소가 같으면 순서가 달라도 같은것
- 요소가 중복되면 안된다.
- nCr = n! / (r! * (n - r) !)
- 5장에서 3장을 뽑는다면
- 5*4*3*2*1 / ( (3*2*1) * (2*1) )
- 120 / 12 = 10
// 순열과 비슷한데 요소를 반복할때 현재요소는 제외해야함
// 다음 반복문에 시작 인덱스를 +1 한다.
//뽑을 요소들이 담긴 리스트 n
//뽑을 갯수 r
//결과를 담을 리스트
ArrayList<Integer[]> result = new ArrayList<>();
boolean[] visited = new boolean[n.size()]; // 요소 사용 여부 체크용
return permtation(r, n, visited, result, new Integer[]{}, 0, 0) // 재귀함수 호출
// 재귀함수
public permtation(int r(뽑을 개수), ArrayList<Integer[]> n (뽑을 요소들 리스트),
boolean[] visited, ArrayList<Integer[]> result(최종결과),
Integer[] tmp(임시배열), int start(인덱스 조절) ,int depth(깊이 조절) ){
if( depth == r ) // 깊이가 r(뽑는갯수)만큼 도달하면 (재귀 종료)
{
result.add() // 리스트에 추가
return
}
// 뽑을 요소 크기 만큼 반복
// 조합은 순서를 상관하지 않기 때문에 -> 순서가 달라도 같은것 이기때문에
// 이전에 뽑은걸 안뽑아도 된다.
// 그렇기 때문에 시작인덱스가 이전인덱스 +1(start) 이다. (이전꺼는 고려대상이 아님)
for(int i=start; i<n.size(); i++){
//해당 요소를 방문하지 않았다면
if(!visited[i]) {
//방문 여부 체크
visited[i] = true;
//해당 요소를 임시 배열에 넣는다.
tmp[i] = n.get(i);
// 재귀함수 호출, 인덱스(start)와 뎁스를 높여서
result = permtation(r, n, visited, result, tmp, start+1, depth + 1);
// 한번 재귀를 순회후, 반복문을 다시 실행하기 위해 false;
visited[i] = false;
}
}
return result;
}
}
각 순열과 조합 문제를 각 템플릿과 비슷한 형식으로 알고리즘 문제를 해결 할 수 있다.
공통 템플릿
public RETURN_TYPE recursive(재귀호출을 하면서, 즉 게임을 진행하면서 필요한 정보들을 선언) {
// base case
// 더 이상 경우의 수가 없거나
// 목적을 달성했거나
// 세상의 끝에 도달했거나
if (끝이다) {
// 항상 리턴
// 이때 어떤 조작을 하고 싶은지에 따라 코드가 추가된다.
// 예. 결과 배열에 지금까지의 결과를 add한다 등
// 예. 하나 찾았으니까 정답에다가 1 더한다.
return
}
// recursive case
// 현재 호출 (상태, 라운드, 순서, idx, 남아있는 경우)
// 현재에서 선택 가능한 경우를 모조리 검토
// 거의 대부분 반복문으로 구현된다
// 선택 가능한 경우가 항상 같다면 (ex. 가위바위보) -> so Simple
// 선택 가능한 경우가 매번 바뀐다면 그 정보가 필요하다 -> flag (ex. isVisited, isUse)
for (let i = 0; i < 선택의길이; i++) {
// 선택을 해도 되는지 검사할 필요가 있으면 해야지
if (선택해도 된다면) {
// 선택을 하자
// 선택을 했으니까 이건 내가 찜했다고 표시해야지 -> flag
isUsed[i] = true;
// 선택이 끝났으니까 다음 호출(라운드, 순서, idx)로 넘어가야지
recursive()
// 다음라운드 갔다가 돌아왔으니까
// 현재 라운드 마저 해볼까?
// 아까 건드렸던거 다시 원복해야지
isUsed[i] = false;
}
}
}