Intro
알고리즘 문제 단골 문제로 기본적인 원칙과 중복순열, 중복조합 , NP , NC 까지 이해하고 암기까지 해야할 정도의 중요도를 지닌 개념이라서 한번 정리해보는 포스팅을 하겠습니다.
순열 , 중복 순열
순열 📖 : 서로다른 것들 중 몇 개를 뽑아서 한 줄로 나열. -> 순서에 따라 달라짐
private static void 순열(int cnt) // 현재까지 뽑은 순열의 개수
{
if(cnt == N) // 뽑고자 하는 순열 생성 완료.
// R 개를 뽑고 싶다면, if(cnt == R)
{
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i = 0; i < N ; i++) // 가능한 모든 수를 시도.
{
if(isSelected[i]) continue; // 이미 선택했다면 넘어감.
numbers[idx] = i; // 현재 해당 수에 해당 수 pick
isSelected[i] = true; // 사용중 처리
순열(idx+1); // 다음 순서의 뽑기 진행
isSelected[i] = false; // 할 수 있는거 다 넣어봤으니 선택 되돌려줌.
}
}중복순열 📖 : 중복을 허락하는 몇 개를 뽑아서 한 줄로 나열 -> 중복허용
private static void 중복순열(int cnt)
{
if(cnt == R) // N개중R개의 순열 생성 완료.
{
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i = 0; i <N ; i++) //배열의 모든 원소 시도.
{
numbers[cnt] = i; // R개의 numbers에 i 넣어줌.
중복순열(cnt+1); // 다음 숫자 선택을 위함.
}
}코드를 보면 중복 순열의 경우 일반적인 순열과는 다르게 visited가 없다 왜냐하면 한번 선택해도 다음 자리의 순열 원소를 만듦에 있어 모든 후보가 다시 후보로 오르기 때문이다.
로또 1등2등3등 모두 같은 사람일 수 있는거랑 같음..!
NextPermutation(다음 순열)
현재의 순열의 상태에서 사전순으로 다음 순열을 생성하는 알고리즘.
Ex) 숫자 순열이라고 치면 가장 작은 수부터 시작하는 순열을 차례대로 만듦.
- 뒤부터 탐색해서 가장 큰 수 (i)를 탐색.
- 뒤부터 탐색해서 i-1위치와 교환할 큰 값위치 j 찾기.
- i-1,j 위치 교환
- i부터 맨 뒤까지 오름차순 정렬
static boolean np(int[] numbers) {
int N = numbers.length; // 배열의 길이 가져옴.
// step1. 꼭대기(i)를 찾는다. 꼭대기를 통해 교환위치(i-1) 찾기
int i = N-1; // 끝인덱스.
while(i>0 && numbers[i-1]>=numbers[i]) --i;
if(i==0) return false; // 젤 앞이 젤 큼 = 마지막 순열.
// step2. i-1 위치값과 교환할 큰 값 찾기
int j = N-1;
while(numbers[i-1]>=numbers[j]) --j;
// step3. i-1위치값과 j위치값 교환
swap(numbers,i-1,j);
// step4. 꼭대기(i)부터 맨뒤 까지 내림차순형태의 순열을 오름차순으로 처리
int k = N-1;
while(i<k) {
swap(numbers,i++,k--);
}
return true;
}
private static void swap(int[] numbers,int i,int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}🙋 그냥 순열이랑 결과는 같은데 왜 쓰나요??
🤖 일반적인 순열은 재귀로 들어가지만 np는 for문으로 작동하기 때문에 더 빠릅니다.
조합, 중복 조합.
조합 📖 : 서로다른 것들 중 몇 개를 순서없이 뽑음. -> 순서상관 없음!
주머니에서 N개의 공 중에 R개를 뽑는 모든 경우의 수.
private static void 조합(int cnt,int start) // 현재뽑은 갯수, 조합 시도할 원소의 시작인덱스
{
if(cnt == R) // R개를 모두 뽑았다면 조합 생성완료
{
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i = start; i < N; i ++) // 시작인덱스 부터 모든 경우 탐색
{
numbers[cnt] = i; //한번 넣어보고
조합(cnt+1,i+1); // 하나 넣었으니 cnt+1, 지금꺼 다음꺼 부터 봐도 ㄱㅊ으니 i+1-> 중복 제거하기위함.
//numbers[cnt]에 리셋 안해도 되는 이유 : 차피 for문안에서 덧씌워지기 때문임.
}
}중복 조합 📖 : 서로다른 것들 중 몇 개를 순서없이 뽑음.
주머니에서 N개의 공 중에 R개를 뽑는 중에 다시 주머니에 안넣고 R개까지 뽑는 모든 경우의 수.
private static void 중복조합(int cnt,int start)
{
if(cnt == N)
{
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i = start; i <= 6; i ++)
{
numbers[cnt] = i;
중복조합(cnt+1,i); // i+1안해서 지금 인덱스인 i 부터 시작해서 중복을 허용해줌.
}
}NextPermutation 활용 조합.
// 다음 큰 순열이 있으면 true, 없으면 false
private static boolean np(int[] numbers) {
int N = numbers.length;
// step1. 꼭대기(i)를 찾는다. 꼭대기를 통해 교환위치(i-1) 찾기
int i = N-1;
while(i>0 && numbers[i-1]>=numbers[i]) --i;
if(i==0) return false;
// step2. i-1 위치값과 교환할 큰 값 찾기
int j = N-1;
while(numbers[i-1]>=numbers[j]) --j;
// step3. i-1위치값과 j위치값 교환
swap(numbers,i-1,j);
// step4. 꼭대기(i)부터 맨뒤 까지 내림차순형태의 순열을 오름차순으로 처리
int k = N-1;
while(i<k) {
swap(numbers,i++,k--);
}
return true;
}
private static void swap(int[] numbers,int i,int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}부분집합
문제 중에서 주로 개수에 상관없이 ~~~ 최대를 구하라 라는 문제를 많이 접해 봤을 것이다. 위의 조합과 순열의 경우 정해진 숫자만큼의 경우를 고려하지만, 부분집합은 해당 집합에 포함된 모든 원소의 경우를 선택하는 것입니다.
예를들어 배낭 짐싸기문제.
private static void makeSubset(int idx)
{
if(idx == N) // idx가 집합의 길이만큼 모두 순회했다면 1개의 부분집합이 만들어진것.
{
totalCnt++;
for (int i = 0; i < N; i++) // 어떤 원소가 선택 됐는지 순회
{
System.out.print((isSelected[i]? input[i] : "X") + " ");
}
System.out.println();
return;
}
//현재 원소를 부분집합에 넣기
isSelected[idx] = true;
makeSubset(idx+1);// 다음 원소 넣을지 고민
//현재 원소를 부분집합에 넣지 않기.
isSelected[idx] = false;
makeSubset(idx+1);// 다음 원소 넣을지 고민
}코드가 저런 이유는 원소 1개의 입장은 선택하는 부분집합에 포함되냐? 안되냐? 이 두가지 경우 밖에 없기 때문이다.
