🎯 순열
순열이란 n개의 숫자 중에서 r개의 숫자를 모든 순서대로 뽑는 경우를 말합니다.
수학에서 순열은 서로 다른 n개의 원소에서 r개를 뽑아한 줄로 세우는 경우의 수입니다.
순열의 개수는 n!과 같습니다.
예를 들어 {1, 2, 3} 배열에서 2개의 숫자를 뽑는 순열은 다음과 같습니다.
{1, 2}
{1, 3}
{2, 1}
{2, 3}
{3, 1}
{3, 2}주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 합니다.
말 그대로, 순서가 존재하는 열이라는 것입니다.
즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 등.. 모두 다른 결과를 가져옵니다. 순서가 다르기 때문이죠.
📌 순열의 구현
public class 순열 {
static int N;
static int M;
static int[] permu;
static int[] num;
static boolean[] check;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
permu = new int[M];
check = new boolean[N];
num = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
DFS(0);
}
static void DFS(int depth) {
if (depth == M) {
for (int a : permu) {
System.out.print(a + " ");
}
System.out.println();
} else {
for (int i = 0; i < N; i++) {
if (!check[i]) {
permu[depth] = num[i];
check[i] = true;
DFS(depth + 1);
check[i] = false;
}
}
}
}
}📌 중복 순열의 구현
public class 중복순열 {
static int N;
static int M;
static int[] permu;
static int[] num;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
permu = new int[M];
num = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; ++i){
num[i] = Integer.parseInt(st.nextToken());
}
DFS(0);
}
static void DFS(int depth) {
if (depth == M) {
for (int a : permu) {
System.out.print(a + " ");
}
System.out.println();
} else {
for (int i = 0; i < N; i++) {
permu[depth] = num[i];
DFS(depth + 1);
}
}
}
}✅ 핵심 포인트
순열과 중복 순열의 구현 차이는 방문 배열 이용 유무 차이입니다.
순열은 중복을 허용하지 않으므로 이전에 삽입한 값과 현재 삽입할 값이 같아지지 않도록 방문 배열을 통해 검사해주어야 합니다.
{ 1, 2, 3 }의 3개 숫자를 순열로 만드는 경우
-
depth = 0
permu = {1};,check = {true, false, false}; -
depth = 1
permu = {1, 2};,check = {true, true, false}; -
depth = 2
permu = {1, 2, 3};,check = {true, true, true}; -
depth = 3
출력 -> 종료 -
depth = 2
i = N-> 종료 -
depth = 1
permu = {1, 3};,check = {true, false, true}; -
depth = 2
permu = {1, 3, 2};,check = {true, true, true}; -
depth = 3
출력 -> 종료
...
중복 순열의 경우 중복을 허용하므로 for문을 돌면서 차례대로 permu 배열에 값을 넣어주면 됩니다.
-
depth = 0
permu = {1};,i = 0; -
depth = 1
permu = {1, 1};,i = 0; -
depth = 2
permu = {1, 1, 1};,i = 0; -
depth = 3
출력 -> 종료 -
depth = 2
permu = {1, 1, 2};,i = 1; -
depth = 3
출력 -> 종료 -
depth = 2
permu = {1, 1, 3};,i = 2; -
depth = 3
출력 -> 종료
...
🎯 조합
조합이란 n개의 숫자 중에서 r개의 숫자를 모든 순서대로 뽑는 경우를 말합니다.
수학에서 조합은 서로 다른 n개의 원소에서 순서에 상관없이 r개를 선택하는 경우의 수입니다.
예를 들어 {1, 2, 3} 배열에서 2개의 숫자를 뽑는 조합은 다음과 같습니다.
{1, 2}
{1, 3}
{2, 3}조합은 순서가 상관이 없는 모임을 의미합니다.
순서가 상관없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3 } 모두 같은 것으로 취급을 합니다.
순서가 상관없기 때문에 1, 2, 3 이라는 3개의 숫자로 이루어져 있다는 점에서 똑같은 취급을 하는 것입니다.
📌 조합의 구현
public class 조합 {
static int N;
static int M;
static int[] combi;
static int[] num;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combi = new int[M];
num = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; ++i){
num[i] = Integer.parseInt(st.nextToken());
}
DFS(0, 0);
}
static void DFS(int depth, int start) {
if (depth == M) {
for (int t : combi) {
System.out.print(t + " ");
}
System.out.println();
} else {
for (int i = start; i < N; i++) {
combi[depth] = num[i];
DFS(depth + 1, i + 1);
}
}
}
}📌 중복 조합의 구현
public class 조합 {
static int N;
static int M;
static int[] combi;
static int[] num;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
combi = new int[M];
num = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; ++i){
num[i] = Integer.parseInt(st.nextToken());
}
DFS(0, 0);
}
static void DFS(int depth, int start) {
if (depth == M) {
for (int t : combi) {
System.out.print(t + " ");
}
System.out.println();
} else {
for (int i = start; i < N; i++) {
combi[depth] = num[i];
DFS(depth + 1, i + 1);
}
}
}
}✅ 핵심 포인트
조합과 중복 조합의 구현 차이는 다음 DFS를 호출 할 때의 시작점입니다.
조합은 중복을 허용하지 않으므로 현재 삽입한 값을 다시 삽입하지 않도록 함수를 재귀 호출 시 시작점에 1을 더해줍니다.
{ 1, 2, 3, 4, 5 }의 5개 숫자 중 3개를 선택하는 조합의 경우
-
depth = 0
combi = {1};,start = 0,i = 0; -
depth = 1
conbi = {1, 2};,start = 1,i = 1; -
depth = 2
combi = {1, 2, 3};,start = 2,i = 2; -
depth = 3
출력 -> 종료 -
depth = 2
combi = {1, 2, 4};,start = 2,i = 3; -
depth = 3
출력 -> 종료 -
depth = 2
combi = {1, 2, 5};,start = 2,i = 4; -
depth = 3
출력 -> 종료
...
중복 조합의 경우 중복을 허용하므로 모든 재귀 함수가 동일한 시작점에서 시작합니다.
-
depth = 0
combi = {1};,start = 0,i = 0; -
depth = 1
conbi = {1, 1};,start = 0,i = 0; -
depth = 2
combi = {1, 1, 1};,start = 0,i = 0; -
depth = 3
출력 -> 종료 -
depth = 2
combi = {1, 1, 2};,start = 0,i = 1; -
depth = 3
출력 -> 종료 -
depth = 2
combi = {1, 1, 3};,start = 0,i = 2; -
depth = 3
출력 -> 종료
...
