2019-03-21 브루트포스

브루트포스

  • 브루트포스 : 모든 경우의 수를 다 해보는 것이다. 이때, 경우의수를 다 해보는데 걸리는 시간이 문제의 시간제한(보통 1,2초)를 넘지 않아야 한다.

  • 3가지 단계로 생각해볼 수 있다.
    1. 가능한 경우의 수를 계산(직접 계산을 해야한다. 손으로 직접? 대부분은 제곱정도로)
    2. 가능한 모든 방법을 다 만들어본다(코딩을 사용, 하나도 빠지면 안된다. 대표적으로 그냥 다 해보는 방법을 사용 : for문, 순열, 재귀호출사용, 비트마스크사용)
    3. 각각의 방법을 이용해 답을 구한다.
  • 시간복잡도 : 2번에 걸리는 시간 * 3번에 걸리는 시간

일곱난쟁이

  1. 9명의 난쟁이 중에 7명의 난쟁이 찾기
  2. 일곱난쟁이의 키의 합은 100이다.
  • 9중에 7명을 고른다. => 2명을 고른다. 9C2 = 36가지
  • 9명중에 7명을 고르는것은 9명중에 2명을 고르는 것과 같다. 난쟁이의 수를 N이라고했을때, 2명을 고르는 경우의 수 N^2라고 할 수 있다.
  • 나머지 난쟁이의 키의 합을 고르는 시간 복잡도 : O(N)
  • 방법의개수:O(N^2) * 값O(N) = O(N^3)

날짜계산

  • 준규가 사는 나라는 E S M이라는 연도를 사용한다.
  • 1<=E<=15, 1<=S<=28, 1<=M<=19
  • E S M
  • 경우의수 151819 = 7980

N중 for문

  • N개 중 일부를 선택해야 하는 경우에 많이 사용
  • 재귀 호출이나 비트마스크를 사용하면 더 간결하고 보기 쉬운 코드를 작성할 수 있기때문에, 사용할 일이 거의 없다.

1 2 3 더하기

  • 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제

  • n = 4
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3

  • 3+1

  • n이 10보다 작거나 같기 때문에 최대 10개 이하로 표현 가능
  • 2중 for문을 넘어가면 보통 재귀함수를 사용한다. 폭이 넓어지고 실수할 확률이 증가해서.

순열

  • 1~N까지 이루어진 수열
  • 크기는 항상 N이 되어야 하고, 겹치는 숫자가 존재하지 않음
  • 순열을 이용해서 문제를 풀면, 순서가 매우 중요하다.
  • 크기가 N인 순열은 N!개 존재한다.
  • 순열을 만든다. => 첫순열 : 오름차순, 마지막순열 : 내림차순

다음순열(Next Permutation)

  • 순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법
  1. A[i-1] < A[i]
  2. j>=i 이면서 A[j]>A[i-1]을 만족하는 가장 큰 j를 찾는다
  3. A[i-1]과 A[j]를 swap한다
  4. A[i]부터 순열을 뒤집는다.
bool next_permutation(int *a, int n) {
	int i = n-1;
    while (i>0 && a[i-1] >= a[i]) i -= 1;
    if (i <= 0) return false; //마지막 순열
    int j = n-1;
    while(a[j] <= a[i-1]) j -= 1;
    swap(a[i-1], a[j]);
    j = n-1;
    while (i<j) {
    	swap(a[i], a[j]);
        i += 1;
        j -= 1;
    }
    return true;
}

이전순열

bool next_permutation(int *a, int n) {
	int i = n-1;
    while (i>0 && a[i-1] <= a[i]) i -= 1;
    if (i <= 0) return false; //마지막 순열
    int j = n-1;
    while(a[j] >= a[i-1]) j -= 1;
    swap(a[i-1], a[j]);
    j = n-1;
    while (i<j) {
    	swap(a[i], a[j]);
        i += 1;
        j -= 1;
    }
    return true;
}

모든순열

  1. 첫순열을 만든다. 1…N
  2. 다음순열
  3. 다음순열….
  4. 다음순열이 존재하지 않을때까지.
  • do-while은 모든순열을 구할때만 사용을 한다. 다음순열을 만들어 주기때문에 사용.

팩토리얼

  • 모든순서를 만드는데 걸리는 시간 : N!
  • 모든 순열을 만드는데 걸리는 시간이 O(N!)? 아니다. 순열의 갯수가 총 N!가 있고. 다음수열을 구하는것{O(N)}을 N!이 걸리므로 O(N*N!).
  • 10정도까지만 구할 수 있다. 10팩토리얼이 3000만정도되서

차이를 최대로

  • 수N개가 주어셨을때(3<=N<=8) 최대8의 경우의 수는 4만개.
  • 배열의 크기 :N, 배열A: 순서만 바꾸는 것이 가능
  • A[0]-A[1] + A[1]-A[2] +…+ A[N-2]-A[N-1] 를 최대로 하는 문제
  • N!=8!=40320
정렬한번하고..
do {
	int temp = calculate(a);
    ans = max(ans, temp);
} while(next_permutation(a.begin(), a.end());

외판원순회(TSP)

  • 1~N번까지 도시가 있다.
  • 한 도시에서 시작해 N개의 모든 도시를 거쳐 다시 원래 도시로 돌아오려고 한다.(한번갔던 도시로는 다시 갈 수 없다)
  • 이때, 가장 적은 비용을 구하는 문제
  • w[i][j] = i->j비용
  • 2<=N<=10, 10! = 3628800*N
  • 모든 경우를 다해봐도 시간 안에 나온다.
  • d: [1,2,3,4,…n]
do {
	bool ok = true;
    int sum = 0;
    for (int i=0; i<n-1; i++) {
    	if (w[d[i]][d[i+1]] == 0) ok = false;
        else sum += w[d[i]][d[i+1]];
    }
    if (ok && w[d[n-1]][d[0]] != 0) {
    	sum += w[d[n-1]][d[0]];
        if (ans > sum) ans = sum;
    }
} while (next_permutaion(d.begin(), d.end()));
  • 1,2,3,4
  • 2,3,4,1
  • 3,4,1,2
  • 4,1,2,3은 모두 같은 경우이다.
  • 즉, 시작점을 1로 고정해도 된다.
do {
	bool ok = true;
    int sum = 0;
    for (int i=0; i<n-1; i++) {
    	if (w[d[i]][d[i+1]] == 0) ok = false;
        else sum += w[d[i]][d[i+1]];
    }
    if (ok && w[d[n-1]][d[0]] != 0) {
    	sum += w[d[n-1]][d[0]];
        if (ans > sum) ans = sum;
    }
} while (next_permutaion(d.begin()+1, d.end()));
// begin이 1이니까. begin+1로시작을 해서 begin을 1로 고정을 한다.
// 복잡도가 (N-1)(N-1)! = O(N!)로 줄어든다.


do {
	if (d[0] != 1) break;
	bool ok = true;
    int sum = 0;
    for (int i=0; i<n-1; i++) {
    	if (w[d[i]][d[i+1]] == 0) ok = false;
        else sum += w[d[i]][d[i+1]];
    }
    if (ok && w[d[n-1]][d[0]] != 0) {
    	sum += w[d[n-1]][d[0]];
        if (ans > sum) ans = sum;
    }
} while (next_permutaion(d.begin(), d.end()));
Written on March 21, 2019