[C언어] 순열과 중복순열
순열
(1) 순열 _ nPr
- 서로 다른 n개 중에서 r개(n≥r)를 골라 순서를 고려해 나열한 경우의 수
- ex) 0~8 까지의 숫자 중에서 3개의 숫자를 순열로 뽑는 경우
→ ( 0 1 2 ) / (1 2 0) / ( 1 0 2 ) 는 모두 다른 경우
|
0
|
1
|
2
|
가능
|
|
1
|
2
|
0
|
가능
|
|
2
|
1
|
0
|
가능
|
순열 알고리즘 핵심
- 순열 알고리즘에서는 item과 bucket을 사용 ( 상황에 따라 item과 bucket을 어떻게 정하는지가 핵심 포인트 )
- item : 뽑을 수 있는 숫자 / 같은 특성을 갖고 있는 것들의 집단
→ 오늘 순열 예제에서 item은 0부터 n까지 총 item개만큼의 수를 뽑아야 한다는 것을 의미
( ex) int item = 5; // 0~4까지 총 5개의 수를 뽑아야 한다는 것을 의미 )
- bucket : item에서 뽑은 것( 값 자체 / 해당 값의 index )을 저장하는 곳
|
* 순열 알고리즘 포인트
- 새로운 item을 뽑아서 bucket에 담을 때, bucket에 존재하지 않는 item 중에서 뽑는다
(= 아직 뽑히지 않은 item 중에서 뽑는다)
- item을 뽑기 전에 뽑으려고 하는 값이 이미 bucket에 있는지 검사하는 알고리즘 필요
|
순열 예제 코드
Q. 0~4까지 총 5개의 숫자 중 3개를 뽑아 순서를 고려하여 출력하는 프로그램을 작성하라 (중복허용X)
- 5개 중 3개를 뽑고 순서를 고려하여야 하므로 순열과 중복순열 두가지 선택지가 있지만
중복을 허용하지 않기 때문에 순열을 사용하여 푸는 문제다!!
// 순열 예시 _ 5P3
#include <stdio.h>
#include <stdlib.h>
/*
n = item 정보
bucket = 뽑은 숫자를 담을 배열
bucketSize = bucket에 대한 정보(배열의 크기)
k = 앞으로 뽑아야 할 개수
*/
void pick(int n, int *bucket, int bucketSize, int k){
int i, j, lastIndex, smallest;
int flag; // 뽑힌 여부를 판별할 flag 변수
lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index
if(k == 0){ // 다 뽑았으면 모든 경우의 수 출력
for(i = 0; i < bucketSize; i++)
printf("%d ", bucket[i]);
printf("\n");
return; // 무한루프 방지
}
smallest = 0;
for(i = smallest; i < n; i++){
flag = 0;
for(j = 0; j <= lastIndex; j++){ // 이번에 뽑으려는 수가 이미 뽑힌 수인지 검사
if(bucket[j] == i){
flag = 1; // 뽑힌 적이 있다면 flag를 1로 세팅
break;
}
}
if(!flag){ // flag가 0이면 뽑기
bucket[lastIndex + 1] = i;
pick(n, bucket, bucketSize, k - 1); // 앞으로 뽑아야 할 개수를 하나 감소
}
}
return;
}
int main(void){
int n = 5; // item 정보
int bucket[3]; // 뽑은 숫자를 담을 곳
pick(n,bucket,3,3); // 순열 알고리즘
return;
}
중복순열
(1) 중복순열 _ nΠr
- 논리흐름은 순열과 유사
- item에서 값을 뽑아 bucket에 담을 때 매번 전체 item 중에서 뽑는다
- ex) 0~8 까지의 숫자 중에서 3개의 숫자를 순열로 뽑는 경우
→ ( 0 0 1 ) / ( 0 1 0 ) / ( 1 0 0 ) 는 모두 다른 경우
|
0
|
0
|
1
|
가능
|
|
0
|
1
|
0
|
가능
|
|
1
|
0
|
0
|
가능
|
중복순열 예제 코드
Q. 0~4까지 총 5개의 숫자 중 3개를 뽑아 순서를 고려하여 출력하는 프로그램을 작성하라 (중복허용O)
- 5개 중 3개를 뽑고 순서를 고려하여야 하므로 순열과 중복순열 두가지 선택지가 있지만
중복을 허용하기 때문에 중복순열을 사용하여 푸는 문제다!!
//중복순열 - 5ㅠ3
#include <stdio.h>
#include <stdlib.h>
/*
n = item 정보
bucket = 뽑은 숫자를 담을 배열
bucketSize = bucket에 대한 정보(배열의 크기)
k = 앞으로 뽑아야 할 개수
*/
void pick(int n, int *bucket, int bucketSize, int k){
int i, lastIndex, smallest;
lastIndex = bucketSize - k - 1; // 가장 최근에 뽑힌 수가 저장된 위치 index
if(k == 0){ // 다 뽑았으면 모든 경우의 수 출력
for(i = 0; i < bucketSize; i++)
printf("%d ",bucket[i]);
printf("\n");
return; // 무한루프 방지
}
smallest = 0;
for(i = smallest; i < n; i++){
bucket[lastIndex + 1] = i;
pick(n, bucket, bucketSize, k - 1); // 앞으로 뽑아야 할 개수를 하나 감소
}
return;
}
int main(void){
int n = 5; // item 정보
int bucket[3]; // 뽑은 숫자를 담을 곳
pick(n, bucket, 3, 3); // 중복순열 알고리즘
return;
}
오늘은 item과 bucket을 활용하여 순열과 중복순열 프로그램을 작성해보는 방법을 배워봤다!
오늘의 공부 끝 :)