순열(Permutation)
순열은 여러 가지 물건이나 숫자 중에서 몇 개를 골라 줄을 세우는 방법이에요. 예를 들어, '1, 2, 3'이라는 숫자가 있을 때, 이 숫자들을 순서를 바꿔서 만들 수 있는 모든 경우의 수를 찾는 거예요. 순열은 '순서를 바꾸기' 때문에 결과가 달라질 수 있어요!
순열을 간단히 표현해 볼까요?
- 순열을 수학 기호로는 nPr라고 써요. 여기서 n은 전체 숫자(또는 물건)의 개수, r은 고를 숫자의 개수예요.
- 예를 들어, 3P2는 '3개 중에서 2개를 골라 순서를 정한다'는 뜻이에요.
순열이 어디에 쓰일까요?
TSP(여행하는 판매원 문제) 같은 어려운 문제를 풀 때 순열을 이용해요. 예를 들어, 여러 도시를 한 번씩만 방문하고 원래 출발했던 도시로 돌아오는 가장 짧은 경로를 찾는 거예요. 각 도시의 방문 순서를 바꿔가며 모든 경우를 계산할 수 있어요. 다만, 도시가 많아질수록 계산 시간이 늘어나기 때문에 더 똑똑한 방법이 필요할 수도 있어요.
참고: 순열을 모두 계산하려면 시간이 아주 많이 걸려요. 예를 들어, 10개의 숫자를 다 나열하면 계산할 때마다 엄청난 시간이 걸릴 수 있어요.
순열을 찾는 4가지 방법
- 방문 기록 (visited) 사용하기
- 비트마스크 (bitmask) 사용하기
- 스왑 (swap) 사용하기
- 다음 순열 (Next Permutation) 사용하기
각 방법을 하나씩 살펴볼까요?
1. 방문 기록(visited) 사용하기
이 방법은 숫자를 사용할 때마다 "이 숫자는 사용했어요!"라고 표시하는 방법이에요. 마치 여러 개의 색깔 공을 뽑아서 줄 세울 때, 뽑은 공에 표시를 해두는 것과 비슷해요! 그리고 다 뽑으면 공을 다시 제자리에 놓고 처음부터 다시 뽑는 과정을 반복하는 것이죠.
import java.util.Arrays;
public class Permutation {
public static int N; // 입력 데이터 수
public static int R; // 뽑을 데이터 수
public static int[] data; // 입력 데이터 배열
public static int[] numbers; // 뽑은 데이터 배열
public static boolean[] visited; // 방문한 데이터 표시 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3 };
N = data.length;
R = 3; // 3개의 숫자를 뽑음
numbers = new int[R];
visited = new boolean[N]; // 방문 여부를 기록하는 배열
permutation(0); // 순열 만들기 시작
}
public static void permutation(int depth) {
if (depth == R) { // R개의 숫자를 모두 뽑았을 때
System.out.println(Arrays.toString(numbers)); // 결과 출력
return;
}
for (int i = 0; i < N; i++) {
if (visited[i]) // 이미 뽑은 숫자는 건너뜀
continue;
numbers[depth] = data[i]; // 숫자를 뽑아서 자리에 넣음
visited[i] = true; // 방문 표시
permutation(depth + 1); // 다음 숫자 뽑기
visited[i] = false; // 다시 원래 상태로 돌림
}
}
}
결과
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
이 방법은 각 숫자가 한 번씩만 사용되도록 관리하는 visited 배열을 사용해요. 그래서 숫자를 뽑았는지 확인하고, 뽑았던 숫자는 다시 뽑지 않도록 해주는 거예요.
시간복잡도: 숫자가 많아질수록 시간이 매우 오래 걸려요! 10개 정도의 숫자를 모두 나열하려면 약간 위험할 수 있어요.
2. 비트마스크(bitmask) 사용하기
이번에는 비트마스크라는 방법을 써볼 거예요. 이 방법은 마치 작은 스위치를 켜고 끄는 것처럼, 숫자를 사용했는지 안 했는지 비트를 이용해 기록해요. 비트는 컴퓨터가 사용하는 0과 1의 값을 뜻해요.
import java.util.Arrays;
public class Permutation {
public static int N; // 입력 데이터 수
public static int R; // 뽑을 데이터 수
public static int[] data; // 입력 데이터 배열
public static int[] numbers; // 뽑은 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3 };
N = data.length;
R = 3;
numbers = new int[R];
permutation(0, 0); // 순열 만들기 시작
}
public static void permutation(int depth, int bit) {
if (depth == R) {
System.out.println(Arrays.toString(numbers));
return;
}
for (int i = 0; i < N; i++) {
if ((bit & 1 << i) != 0) // 비트로 사용 여부 체크
continue;
numbers[depth] = data[i]; // 숫자 선택
permutation(depth + 1, bit | 1 << i); // 비트로 방문 처리
}
}
}
결과
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
비트마스크를 사용하면 숫자가 많아져도 별도의 배열 없이 숫자를 사용했는지 빠르게 확인할 수 있어요.
3. 스왑(swap) 사용하기
스왑은 숫자의 위치를 바꿔가며 순서를 만드는 방법이에요. 처음에 뽑은 숫자를 다른 숫자들과 자리만 바꿔가며 모든 경우를 찾아내는 것이죠!
import java.util.Arrays;
public class Permutation {
public static int N; // 입력 데이터 수
public static int[] data; // 입력 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3 };
N = data.length;
permutation(0);
}
public static void permutation(int depth) {
if (depth == N) {
System.out.println(Arrays.toString(data));
return;
}
for (int i = depth; i < N; i++) {
swap(depth, i); // 두 숫자의 위치를 바꿈
permutation(depth + 1); // 다음 순열을 만듦
swap(i, depth); // 원래대로 되돌림
}
}
public static void swap(int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
결과
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
스왑은 숫자의 위치를 바꾸는 방식으로 순열을 만들어내는 방법이에요. 실제로 물건을 바꾸는 것처럼 숫자의 순서를 계속 바꿔가며 여러 가지 경우를 찾아낼 수 있답니다.
4. 다음 순열(Next Permutation) 사용하기
이 방법은 다음으로 나올 수 있는 순서를 차례차례 찾아가는 방법이에요. 마치 사전에서 단어를 찾는 것처럼, 처음에 주어진 순서를 기준으로 그다음 순서를 찾아내요.
import java.util.Arrays;
public class Permutation {
public static int N; // 입력 데이터 수
public static int[] data; // 입력 데이터 배열
public static void main(String[] args) {
data = new int[] { 1, 2, 3 };
N = data.length;
Arrays.sort(data); // 숫자를 처음에 오름차순으로 정렬
do {
System.out.println(Arrays.toString(data));
} while (np()); // 다음 순열을 계속 찾아감
}
private static boolean np() {
int i = N - 1;
while (i > 0 && data[i - 1] >= data[i]) {
i--;
}
if (i == 0)
return false;
int j = N - 1;
while (data[i - 1] >= data[j]) {
j--;
}
swap(i - 1, j);
int k = N - 1;
while (i < k) {
swap(i++, k--);
}
return true;
}
private static void swap(int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
결과
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
이 방법은 숫자의 다음 순서를 차례차례 찾아가며 모든 순열을 만듭니다. 사전에서 단어를 하나하나 찾아가는 것처럼, 규칙에 따라 다음 순서를 찾는 것이에요.
정리
순열(Permutation)은 여러 가지 물건이나 숫자를 줄 세우는 다양한 방법이에요. 초등학생 여러분도 숫자 놀이를 하듯이 이런 프로그램을 만들어보며 재미있게 배울 수 있답니다!
