브루트포스

• 브루트포스 : 모든 경우의 수를 다 해보는 것이다. 이때, 경우의수를 다 해보는데 걸리는 시간이 문제의 시간제한(보통 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()));