1. 순열, 조합, 부분조합문제 💡
순열, 조합, 부분조합 문제는 원소의 선택과 배열을 다루는 경우의 수 문제로, 주로 다양한 경우를 탐색하거나 최적의 선택을 위해 활용된다.
개인적인 생각으로는 조합이 가장 많이 쓰이고, 그다음이 순열, 그다음이 부분조합인 것 같다.
SSAFY의 알고리즘 과정에서도 가장 먼저 배우는.. 알고리즘의 기초라고 생각한다.
대표적으로 BruteForce 방식으로 해결해야 하는 문제에서, 사용되고, 컴퓨터가 가장 잘하는 방식으로 단순하고, 완벽하게 탐색할 수 있기 때문에 많은 문제에서 사용되고 응용되기 때문에 반드시 알아야 하는 알고리즘이다.
완벽히 외우기 쉽지 않으니 정말 매일 매일 반복해서 써봐야 한다. 🔍📈
2. 사용용도❓
문제 예시
브론즈의 대표적인 조합 문제이다.
9명의 난쟁이 중 진짜 난쟁이 7명을 찾아야 한다.
그렇기 때문에 모든 난쟁이 조합을 만들어 보면 알 수 있지만, 그렇게 하기 위해선 7중 for문이 필요하다.
물론 이 문제의 경우 7중 for문으로 해결해 볼 수 있기 때문에 조합 알고리즘을 몰라도 풀만 하지만 난이도가 올라가면 그마저도 못하는 경우가 생긴다. 🤯
순열과 조합의 차이는 간단하다.
순열: 순서가 다르면 다른 경우로 보는 선택
조합: 순서를 무시하고 선택한 구성만으로 보는 경우
순열 예시: A, B를 선택할 때, AB와 BA는 다른 경우 -> 경우의 수 : 2가지
조합 예시: A, B를 선택할 때, AB와 BA는 같은 경우 -> 경우의 수 : 1가지
3. 순열 🔄
아래는 순열의 코드이다.
public class BruteForce {
static int N, R, numbers[], selected[];
static boolean visited[];
public static void main(String[] args) {
N = 9; //전체 갯수
R = 7; //선택할 수
numbers = new int[N];
selected = new int[R];
visited = new boolean[N];
for(int i=0; i<N; i++) numbers[i] = i;
permutaion(0); //매개변수는 항상 0 고정이어야 한다.
}
private static void permutaion(int cnt) {
if(cnt==R) { //cnt가 선택할 수만큼 차면 초기화 해줘야하기 떄문에 if문으로 끊고 return해준다.
System.out.println(Arrays.toString(selected));
return; //이걸 자주 빼먹어서 틀리는 경우가 많다.
}
for(int i=0; i<N; i++) {
if(visited[i]) continue; //방문처리
visited[i] = true;
selected[cnt] = numbers[i]; //선택
permutaion(cnt+1);
visited[i] = false;
}
}
}재귀함수 형태로 되어있어서 이해하기 어렵지만 중단점 걸고 따라가면서 보다 보면 충분히 이해할 수 있다.
(💡 참고: 재귀 함수는 함수가 스스로를 호출하며 작업을 진행하는 방식으로, 복잡한 경우의 수를 효율적으로 탐색할 수 있는 방법이다. 순열은 선택한 원소들의 순서까지 고려하는 경우에 사용)
4. 조합 🎲
조합은 순열에서 방문처리 부분만 빼고, 매개변수, for문만 살짝 수정해주면 끝이다.
그렇기 때문에 순열만 외우면 조합도 따라온다고 보면 된다.
public class BruteForce {
static int N, R, numbers[], selected[];
static boolean visited[];
public static void main(String[] args) {
N = 9; //전체 갯수
R = 7; //선택할 수
numbers = new int[N];
selected = new int[R];
visited = new boolean[N];
for(int i=0; i<N; i++) numbers[i] = i;
combination(0, 0); //여기도 마찬가지로 매개변수는 항상 0,0 고정이다.
}
private static void combination(int start, int cnt) {
if(cnt==R) {
System.out.println(Arrays.toString(selected));
return;
}
for(int i=start; i<N; i++) { //i=0 이었지만 start로 바꿔줘야 한다.
selected[cnt] = numbers[i];
combination(i+1, cnt+1); //여기도 중요하다. start+1이 아니라 i+1이다. 자주 헷갈린다.
}
}
}(💡 참고: 조합은 순서와 상관없이 특정 개수를 선택하는 경우에 사용된다. 인덱스 i를 활용해 이전 원소는 선택하지 않도록 하며, 순열보다 선택의 폭이 넓어진다)
- 부분조합 🔢
부분조합은 두 가지 방법이 유명하지만, 나는 개인적으로 바이너리를 이용한 방법을 선호한다.
for문 두 개만으로 표현 가능하기도 하고, 비트 연산이 처음 보기에는 어려워 보여도 재귀 함수보다는 이해하기가 편한 것 같다.
public class BruteForce {
static int N, R, numbers[], selected[];
static boolean visited[];
public static void main(String[] args) {
N = 9; //전체 갯수
R = 7; //선택할 수
numbers = new int[N];
selected = new int[R];
visited = new boolean[N];
for(int i=0; i<N; i++) numbers[i] = i;
subcombination(); //매개변수는 받지않는다.
}
private static void subcombination() {
for(int i=0; i<(1<<N); i++) {
for(int j=0; j<N; j++) {
if((i & 1<<j) != 0) System.out.print(numbers[j] + " ");
}
System.out.println();
}
}
}1씩 증가시킬 때의 이진수의 1의 개수, 위치가 부분조합과 똑같이 작동하기 때문에 이용할 수 있는 방법이다.
(💡 참고: 이진수에서 특정 비트가 1로 설정된 경우에만 출력하도록 하여 부분집합을 생성한다. 각 비트가 원소의 포함 여부를 나타내기 때문에 유용한 방법이다)
글을 마치며 ✍️
위 세 가지 알고리즘을 처음 배울 때는 하루에 열 번씩 썼다 지우는 것을 반복하며 한 달여간을 외웠고, 그 이후로도 오랜만에 쓰려고 하면 늘 까먹어서 새로 찾아보곤 했다. 그러기를 서너 번 반복하자 이제는 오랜만에 봐도 손이 저절로 쓰게 된다. 그 정도로 익숙해져야 하기 때문에 자꾸 까먹는다고 스스로를 자책하지 말고 계속해서 써보자. 💪
