[코딩테스트] 브루트 포스(순열 이용한 브루트포스 문제)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
차이를 최대로(10819번)
https://www.acmicpc.net/problem/10819
문제
- 수 N개가 주어졌을 때(3 ≤ N ≤ 8)
-
A[0]-A[1] + A[1]-A[2] + … + A[N-2]-A[N-1] 를 최대로 하는 문제
입력
첫째 줄에 N(3 ≤ N ≤ 8), 둘째 줄에 배열 A에 들어있는 정수(-100≤정수≤100)
출력
첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값 출력
풀이
- 수 변경x 수의 순서를 변경 O, 방법의 수 : N!, 최대 : 8! = 40320
- 모든 순열과 거의 흡사
- 시간복잡도 N! 반복 - 1. 계산 2. 다음순열, 둘 다 N 걸림
- O(N x N!)
import java.util.*;
public class Main {
static int ans = 0;
static int sum = 0;
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);
do {
for(int i=0; i<n; i++) {
if(i+1==n)
break;
go(a[i],a[i+1]);
}
if(ans<sum) {
ans = sum;
}
sum = 0;
} while(next_permutation(a));
System.out.println(ans);
}
private static void go(int i, int j) {
sum += Math.abs(i-j);
}
private 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;
}
}
-> 선생님 풀이는 120ms 인데 내가 푼 풀이는 288ms가 걸린다ㅠ do-while문 안에 쓴 합함수를 for문 돌릴때마다 호출하는게 아니라 아예 for문 합쳐서 따로 떼고 i=1로 시작해서 a[i+1]-a[i] 로 쓰는 식의.. 더 빠르고 깔끔한 답안 작성을 연습하자!
외판원 순회2 (10971번)
https://www.acmicpc.net/problem/10971
문제
- 영어로 Traveling Salesman Problem (TSP)
- 1번부터 N번까지 번호가 매겨져있는 도시가 있다
- 한 도시에서 시작해 N개의 모든 도시를 거쳐 다시 원래 도시로 돌아오려고 한다(한 번 갔던 도시로는 다시 갈 수 없다)
- 이 때, 가장 적은 비용을 구하는 문제
- W[i][j] = i -> j 비용, 0인 경우는 갈 수 없음
입력
첫째 줄에 N(2 ≤ N ≤ 10), 다음 N개의 줄에 비용 행렬, 갈 수 없는 경우 0
출력
외판원 순회에 필요한 최소 비용 출력
풀이
- N개 모두 방문, 중복x = 순열
- N! = 10! = 3628800, 모든 경우 다 가능, 시간복잡도 : O(N x N!)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n][n];
int[] arr = new int[n];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
arr[i] = i;
for(int j=0; j<n; j++) {
a[i][j] = sc.nextInt();
}
}
do {
boolean ok = true;
int sum = 0;
for(int i=0; i<n-1; i++) {
if(a[arr[i]][arr[i+1]]==0) { //도시를 가지 못하는 경우
ok = false;
}
else {
sum += a[arr[i]][arr[i+1]];
}
}
//돌아오는 길 계산
if(ok && a[arr[n-1]][arr[0]]!=0) {
sum += a[arr[n-1]][arr[0]];
if(ans>=sum)
ans = sum;
}
} while(go(arr));
System.out.println(ans);
}
private static boolean go(int[] arr) {
int i = arr.length-1;
while(i>0 && arr[i-1]>=arr[i])
i -= 1;
if(i<=0)
return false;
int j = arr.length-1;
while(arr[j]<=arr[i-1])
j -= 1;
int temp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = temp;
j = arr.length-1;
while(i<j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i += 1;
j -= 1;
}
return true;
}
}
-> 도시에서 도시로 못가는 불가능한 경우까지 같이 코드 작성해줘야 정답 처리 된다!ㅠㅠ 이거 몰라서 한참을 헤매고… 문제를 꼼꼼하게 읽자
- 1234, 4123, 2341, 3412는 모두 같은 경우. 다시 시작한 도시로 돌아가야 하기 때문에. 한칸씩 옮긴 경우는 다 같은 방법이니까 저 경우는 제외하고 코드 작성하면 속도가 빨라진다. O(N!) 가 아니라 O(N!/N) = (N-1)!
- 시작 도시를 한 도시로 고정시키기, 순열 함수에 고정된 위치(ex.1)은 제외하고 그 다음 순열만 바뀌도록
next_permutation(d.begin()+1,d.end())) - 전체에 대해 다음순열을 구하는데 첫번째 도시가 1이 아닌 2가 되면 탐색 종료. 자바의 경우 이 방법 사용해야함.
if(d[0]!=1) break;
- 시작 도시를 한 도시로 고정시키기, 순열 함수에 고정된 위치(ex.1)은 제외하고 그 다음 순열만 바뀌도록
로또 (6603번)
https://www.acmicpc.net/problem/6603
문제
- 같은 수가 있어도 순열을 만들 수 있다.
- 입력으로 주어진 K개의 수 중에서 6개의 수를 고르는 문제
입력
첫번째 수 k (6 < k < 13), 다음 k개 수는 집합 S에 포함되는 수(오름차순), 입력 마지막 줄엔 0
출력
각 테스트 케이스마다 사전 순으로 수를 고르는 방법 모두 출력
풀이
- N과 M(2) 와 비슷한 문제임. 재귀 이용하면 되는데 순열로도 풀기 가능. 재귀를 더 추천함.
- k개에서 6개 고른걸 1, k-6개 고르지 않은걸 0
- 모든 순열에서 1이 나온 것만 답을 구해주면 k개 중에 3개만 선택한 것 전부 처리 가능함. ex) 00111, 01011, 01101, 10011…
- 0을 K-6개, 1을 6개 넣고 next_permutation을 수행하면 모든 조합 구할 수 있음, 그 조합에 따라 어떤 수가 골라졌는지 출력
import java.util.*;
public class Main {
static int arr[] = new int[6];
static int a[];
static int n;
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while (true) {
n = sc.nextInt();
if (n == 0)
break;
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
go(0,0);
System.out.println();
}
}
private static void go(int index, int start) {
if(index==6) {
for(int i=0; i<6; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
return;
}
for(int i=start; i<n; i++) {
arr[index] = a[i];
go(index+1, i+1);
}
}
}
-> 재귀로 푼 방식, n과 m문제를 응용해서 풀었다.
댓글남기기