순열
순열은 임의의 수열을 다른 순서로 섞는 연산을 말한다. 예를들어 A=[1,2,3]인 경우 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]이 순열이다.
이처럼 크기가 N인 수열의 서로 다른 순열은 총 개가 있다.
모든 순열을 사전순으로 나열했을 때 위에서 예시를 보인것처럼 결과가 나오게 된다. [1,2,3]이 첫 순열이 되는 것이고 [3,2,1]이 마지막 순열이 되는 것이다.
첫 순열에 경우 오름차순 또는 비오름차순으로 되어있고, 마지막 순열은 내림차순 또는 비내림차순으로 되어있다. 이 성질을 이용해서 다음에 오는 순열을 찾을 수 있다.
C++, 파이썬은 라이브러리로 다음 순열, 이전 순열을 구하는 함수가 존재하는데 자바에 경우 직접 구현해야한다.
즉, 어떤 수의 마지막 순열이면 이 다음 순열은 앞에 수의 제일 마지막 부분만 달라지는 첫 순열이다. 규칙을 아래와같이 정의할 수 있다.
- A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다.
- 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
- A[i-1]과 A[j]를 교환(Swap)한다.
- A[i]부터 순열을 뒤집는다.
예를 들어 A=[7,2,3,6,5,4,1]이 주어졌다고 해보자. 그러면 이 순열은 7,2,3으로 시작하는 마지막 순열인 것이다. 왜냐하면 7 > 2 > 3 < 6 > 5 > 4 > 1 에서 3부분에서 6으로 넘어갈때 부등호가 바뀌기 때문이다. 따라서 1번에 의해 6이 있는 자리가 i가 되고 3부분이 i-1이 된다. 이제 이 순열은 7,2,? 로 시작하는 첫 순열이 되어야한다. ?에 올 수 있는 건 3보다 커야한다. 그 이유는 다음 순열을 구하는 것이기 때문이다. 그리고 그 뒤에 4개의 수에서 하나를 골라야 하는데 앞에서 사용하지 않은 수로 골라야 한다. 그러면 4가 j가 되는 것이고 3번에 의해 3이랑 4가 교환이 되면서 7,2,4,6,5,3,1가 된다. 이제 마지막으로 4번에 의해 6,5,3,1부분이 뒤집혀 1,3,5,6이 되면서 최종 다음 순열은 7,2,4,1,3,5,6이 된다.
뒤집는 이유는 마지막순열을 뒤집으면 오름차순이 되면서 첫순열이 되기 때문이다.
1. 문제 : 다음 순열
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
if (nextPermutation(a)) {
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
} else {
System.out.println("-1");
}
}
public static boolean nextPermutation(int[] a) {
int i = a.length - 1;
while (i > 0 && a[i - 1] >= a[i]) {
i -= 1;
}
if (i <= 0) { // 마지막 순열일 경우
return false;
}
int j = a.length - 1;
while (a[j] <= a[i - 1]) {
j -= 1;
}
int temp = a[i - 1];
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}2. 문제 : 이전 순열
다음 순열 구하는 코드에서 부등호만 바꿔주면 된다.
public static boolean prevPermutation(int[] a) {
int i = a.length - 1;
while (i > 0 && a[i - 1] <= a[i]) {
i -= 1;
}
if (i <= 0) {
return false;
}
int j = a.length - 1;
while (a[j] >= a[i - 1]) {
j -= 1;
}
int temp = a[i - 1];
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}3. 문제 : 모든 순열
모든 순열을 구할 때 첫 순열까지 확인하기 위해 do ~ while문을 주로 사용한다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
do {
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
} while (nextPermutation(a));
}
public static boolean nextPermutation(int[] a) {
int i = a.length - 1;
while (i > 0 && a[i - 1] >= a[i]) {
i -= 1;
}
if (i <= 0) {
return false;
}
int j = a.length - 1;
while (a[j] <= a[i - 1]) {
j -= 1;
}
int temp = a[i - 1];
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}4. 문제 : 차이를 최대로
수 N개가 주어졌을 때 (3 ≤ N ≤ 8) 아래 식을 만족하면서 최댓값을 구하는 문제이다.
수의 순서만 변경한다는 것에 초점을 맞춰서 순열로 풀면 된다. 또한 N의 최대가 8이기 때문에 모든 값을 넣어서 풀어도 오랜 시간이 걸리지 않는다. 8! = 40320 정도인데 시간복잡도는 N * N! 이니까 충분하다.
입력으로 주어진 배열을 먼저 정렬하는 것이 중요하다. 그 이유는 첫 순열부터 시작해야하기 때문이다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int ans = 0;
do {
int temp = calculate(a);
ans = Math.max(ans, temp);
} while (next_permutation(a));
System.out.println(ans);
}
public static boolean next_permutation(int[] a) {
int i = a.length - 1;
while (i > 0 && a[i - 1] >= a[i]) {
i -= 1;
}
if (i <= 0) {
return false;
}
int j = a.length - 1;
while (a[j] <= a[i - 1]) {
j -= 1;
}
int temp = a[i - 1];
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}
public static int calculate(int[] a) {
int sum = 0;
for (int i = 1; i < a.length; i++) {
sum += Math.abs(a[i] - a[i - 1]);
}
return sum;
}5. 문제 : 외판원 순회 2
1번부터 N번까지 번호가 매겨져있는 도시가 있는데, 한 도시에서 시작해 N개의 모든 도시를 거쳐 다시 원래 도시로 돌아오려고 한다. (한 번 갔던 도시로는 다시 갈 수 없다.) 이때 가장 적은 비용을 구하는 문제이다.
이 문제에서 모든 도시를 거치는 것과 한 번 갔던 도시로는 다시 갈 수 없다 라는 것을 이용하여 순열로 풀 수 있다. 하지만 무조건 순열을 사용할 수 없는데 문제의 N 제한이 최대 10이기 때문에 사용할 수 있다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
int[] d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = i;
}
int ans = Integer.MAX_VALUE;
do {
boolean ok = true;
int sum = 0;
for (int i = 0; i < n - 1; i++) {
if (a[d[i]][d[i + 1]] == 0) {
ok = false;
} else {
sum += a[d[i]][d[i + 1]];
}
}
if (ok && a[d[n - 1]][d[0]] != 0) {
sum += a[d[n - 1]][d[0]];
if (ans > sum) {
ans = sum;
}
}
} while (next_permutation(d));
System.out.println(ans);
}
public static boolean next_permutation(int[] a) {
int i = a.length - 1;
while (i > 0 && a[i - 1] >= a[i]) {
i -= 1;
}
if (i <= 0) {
return false;
}
int j = a.length - 1;
while (a[j] <= a[i - 1]) {
j -= 1;
}
int temp = a[i - 1];
a[i - 1] = a[j];
a[j] = temp;
j = a.length - 1;
while (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}코드의 do~while문 안에서 for문은 비용이 0인 부분을 제외하기 위해 boolean변수를 사용하였고 그 외 sum에 더해주었다. for문이 끝나면 마지막에서 처음으로 돌아가는 부분을 고려하여 계산하였다. 이렇게 구현을 하면 시간복잡도는 O(N * N!)이 나온다.
추가적으로 다시 시작한 도시로 돌아가야 한다.라는 조건 때문에 1,2,3,4 , 2,3,4,1, 3,4,1,2 , 4,1,2,3 이 4가지가 값이 동일하다. 따라서 시작점을 1로 고정해도 동일한 문제 결과를 찾을 수 있다.
do {
if (d[0] != 0) {
break;
}
boolean ok = true;
int sum = 0;
for (int i = 0; i < n - 1; i++) {
if (a[d[i]][d[i + 1]] == 0) {
ok = false;
} else {
sum += a[d[i]][d[i + 1]];
}
}
if (ok && a[d[n - 1]][d[0]] != 0) {
sum += a[d[n - 1]][d[0]];
if (ans > sum) {
ans = sum;
}
}
} while (next_permutation(d));6. 문제 : 로또
입력으로 주어진 K개의 수 중에서 6개의 수를 고르는 문제이다. 순열은 순서에 관련된 것인데 이 문제는 선택에 대한 문제이다. 순서 문제를 이용해서 해결이 가능하다.!!
같은 수가 있어도 순열로 나타낼 수가 있다.
즉 선택과 관련된 문제를 순서에 관련된 순열로 바꾸어 풀 수 있다.
선택한 것을 1로 하고 선택하지 않은 것을 0으로 하여 문제를 풀면 된다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int n = sc.nextInt();
if (n == 0) {
break;
}
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int[] d = new int[n];
for (int i = 0; i < n; i++) {
if (i < n - 6) {
d[i] = 0;
} else {
d[i] = 1;
}
}
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
do {
ArrayList<Integer> cur = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if (d[i] == 1) {
cur.add(a[i]);
}
}
ans.add(cur);
} while (next_permutgetion(d));
Collections.sort(ans, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
int n = o1.size();
int m = o2.size();
int i = 0;
while (i < n && i < m) {
int t1 = o1.get(i);
int t2 = o2.get(i);
if (t1 < t2) {
return -1;
} else if (t1 > t2) {
return 1;
}
i += 1;
}
if (i == n && i != m) {
return -1;
} else if (i != n && i == m) {
return 1;
}
return 0;
}
});
for (ArrayList<Integer> al : ans) {
for (int x : al) {
System.out.print(x + " ");
}
System.out.println();
}
System.out.println();
}
}비트마스크
비트(Bit)연산을 사용해서 부분 집합을 표현할 수 있다.
비트 연산
비트 연산에는 &(and), |(or), ~(not), ^(xor)이 있다. 아래의 그림을 참조하면 된다.
예를 들어 A = 27, B = 83인 경우에는 이 수를 2진수로 변환하여 가장 뒤의 자리부터 하나씩 비트 연산을 하면 된다. not 연산의 경우 자료형에 따라 결과가 달라지기 때문에 유의해서 사용해야 한다.
Shift Left(<<) 와 Shift Right(>>) 연산이 있다. A << B 는 A를 왼쪽으로 B비트만큼 옮긴다는 의미인데 예를 들어 1 << 3 이라 하면 가 가 되는 것이다. 즉, A << B = 이다. 반대로 A >> B 는 A를 오른쪽으로 B비트만큼 옮기는 것이다. Shift Left연산과 유사하다. 최종적으로는 가 된다.
위의 성질을 이용하면 는 1 << N 을 해서 구하면 되고 (A+B) / 2를 하는 거면 (A+B) >> 1를 하면 된다.
비트 연산에서는 연산자 우선순위를 유의해서 해야한다. 1 << N - 1 이 주어졌을 때 (1 << N) - 1 로 해석이 될 수 있고 아니면 1 << (N-1)로 해석이 될 수 있기 때문이다.
비트마스크
비트마스크를 통해서 정수로 집합을 나타낼 수 있다는 점이다. 0, 1, 2, 3, 4 , 5, 6 이렇게 있을 때 어떤 수가 사용 했는지를 비트로 표현이 가능한 것이다. 예를 들어 {1,3,4,5,6}가 있으면 이는 570이라는 정수로 나타낼 수 있는데 그 이유가 이기 때문이다.
비트마스크는 보통 0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용한다. 만약 1부터 시작하는 경우 공간이 2배 더 필요하며 각종 연산을 조금 변형해서 사용해야 한다는 문제가 있다. 따라서 0부터 N-1까지로 변형해서 사용하는 것이 좋다.
현재 집합이 S일 때 i를 추가, 검사, 제거, 토글 하는 방법은 아래와 같다.
- 추가 : S | (1 << i)
- 검사 : S & (1 << i)
- 제거 : S & ~(1 << i)
- 토글 : S ^ (1 << i)
토글 : 0을 1로 1을 0으로 변환
전체 집합은 (1 << N) - 1를 하면된다. 이유는 1이 N개가 있으면 이고 이를 위의 식으로 표현할 수 있기 때문이다.
연습 문제 : 집합
위에 설명한 성질을 이용하면 쉽게 풀리는 문제이다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = 20;
int m = Integer.valueOf(br.readLine());
int s = 0;
StringBuilder sb = new StringBuilder();
while (m-- > 0) {
String[] line = br.readLine().split(" ");
if (line[0].equals("add")) {
int x = Integer.valueOf(line[1]) - 1;
s = (s | (1 << x));
} else if (line[0].equals("remove")) {
int x = Integer.valueOf(line[1]) - 1;
s = (s & ~(1 << x));
} else if (line[0].equals("check")) {
int x = Integer.valueOf(line[1]) - 1;
int res = (s & (1 << x));
if (res == 0) {
sb.append("0\n");
} else {
sb.append("1\n");
}
} else if (line[0].equals("toggle")) {
int x = Integer.valueOf(line[1]) - 1;
s = (s ^ (1 << x));
} else if (line[0].equals("all")) {
s = (1 << n) - 1;
} else if (line[0].equals("empty")) {
s = 0;
}
}
System.out.println(sb);
}문제
1. 문제 : 부분수열의 합
N개의 정수로 이루어진 수열이 있을 때 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다.
부분 수열의 개수는 개이다. 이를 비트마스크로 표현하면 1<<N 이라고 할 수 있다. 또한 문제에서 공집합은 제외해야 한다했으니 for문에 시작은 1부터 해야한다. 그리고 중간에 부분수열에 어떤 수가 들어가있는지를 알기위해 검사하는 코드를 넣어주어야 한다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int s = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int ans = 0;
for (int i = 1; i < (1 << n); i++) {
int sum = 0;
for (int k = 0; k < n; k++) {
if ((i & (1 << k)) != 0) {
sum += a[k];
}
}
if (sum == s) {
ans += 1;
}
}
System.out.println(ans);
}2. 문제 : 스타트와 링크
N명을 N/2명씩 두 팀으로 나누어 두 팀의 능력치를 구한 다음, 차이의 최솟값을 구하는 문제이다. S[i][j] = i번 사람과 j번 사람이 같은 팀에 속했을 때 팀에 더해지는 능력치이며 능력치는 팀에 속한 모든 쌍의 S[i][j]의 합을 의미한다. 각 사람을 두 팀 중 하나로 나누는 문제이기 때문에 비트마스크를 사용할 수 있다. 개가 나오면서 전체 경우의 수를 순회할 수 있다.
0부터 1<<N (이니까)까지 for문을 돌리면서 i에 j가 포함되어있으면 첫번째 집합 아니면 두번째 집합으로 넣는 방식으로 구현한다.
이후 집합의 합을 구해 최소값을 계속 구한다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] s = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
s[i][j] = sc.nextInt();
}
}
int ans = -1;
for (int i = 0; i < (1 << n); i++) {
ArrayList<Integer> first = new ArrayList<Integer>();
ArrayList<Integer> second = new ArrayList<Integer>();
for (int j = 0; j < n; j++) {
if ((i & (i << j)) == 0) {
first.add(j);
} else {
second.add(j);
}
}
if (first.size() != n / 2) {
continue;
}
int t1 = 0;
int t2 = 0;
for (int l1 = 0; l1 < n / 2; l1++) {
for (int l2 = 0; l2 < n / 2; l2++) {
if (l1 == l2) {
continue;
}
t1 += s[first.get(l1)][first.get(l2)];
t2 += s[second.get(l1)][second.get(l2)];
}
}
int diff = Math.abs(t1 - t2);
if (ans == -1 || ans > diff) {
ans = diff;
}
}
System.out.println(ans);
}3. 문제 : 종이 조각
N X M 크기의 종이를 조각으로 잘라서 합의 최대값을 구하는 문제이다.
각각의 칸은 가로 또는 세로 칸에 속하게 된다는 점을 이용하여 문제를 해결하면 된다. 즉, 각각의 칸에 대해서 가로(=0)인지 세로(=1)인지 정하면 된다. 이렇게 할 수 있는 이유는 N,M의 최대가 4이기 때문에 전체 칸수는 16칸이 최대이고 여기서 나올 수 있는 경우의 수는 개이기 때문이다. 이 전체의 경우의 수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] a = new int[n][m];
for (int i = 0; i < n; i++) {
String s = sc.next();
for (int j = 0; j < m; j++) {
a[i][j] = s.charAt(j) - '0';
}
}
int ans = 0;
// 0: - 1 : |
for (int s = 0; s < (1 << (n * m)); s++) {
int sum = 0;
for (int i = 0; i < n; i++) { // 가로
int cur = 0;
for (int j = 0; j < m; j++) {
int k = i * m + j;
if ((s & (1 << k)) == 0) {
cur = cur * 10 + a[i][j];
} else {
sum += cur;
cur = 0;
}
}
sum += cur; // -가 끝까지 갔을 때
}
for (int j = 0; j < m; j++) { // 세로
int cur = 0;
for (int i = 0; i < n; i++) {
int k = i * m + j;
if ((s & (1 << k)) != 0) {
cur = cur * 10 + a[i][j];
} else {
sum += cur;
cur = 0;
}
}
sum += cur;
}
ans = Math.max(ans, sum);
}
System.out.println(ans);
}가로의 최대값을 구하는 부분에서 k는 몇번째 칸인지를 나타내는 변수이다. (i,j)가 몇 번째 인지 구하려면 i * m + j를 하면 된다는 성질를 이용해서 구할 수 있다. k번째가 s에 포함되어 있으면 cur에 추가하고 세로를 만난 경우에는 sum에 누적시키면 된다. for문이 끝나고 sum을 한번 더 쓴 이유는 가로가 마지막 열까지 이어졌을 경우를 고려한 것이다. 세로 역시 가로와 마찬가지로 구하면 되는데, 행부분을 0 ~ N-1까지로 두고 구하면 된다.
참고
백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.
