[알고리즘 중급] 순열(연습)

- 다 해봐야하는 경우

- 순서만 변경 가능한 경우

 

💚 2529 부등호 문제

한 자리 숫자, 선택된 수는 모두 달라야 한다. -> 순서만 바꿔가면서 답을 구하면 된다.

- 10개의 수 중에서 k + 1개를 고름

- (k + 1)! 순서를 만든 후 부등호 유효한지 검사

 

너무 많은 경우의 수가 발생하기 때문에 최적화가 필요하다.

실제로 모든 경우의 수가 필요한 것이 아니라 가장 작은 수와 가장 큰 수만 구하면 된다.

 

algorithm 헤더에 next_permutaion, prev_permutation이라는 유용한 메소드가 존재한다.

이 메서드에 vector을 넣으면 vector의 요소의 다음 순열이 리턴된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 입력된 부등호 문자열에 부합하는지 확인
// 각기 다른 수임을 전제
bool check(vector<int> perm, vector<char> &a){
    for(int i = 0;i < a.size();i++) {
        if(a[i] == '<' && perm[i] > perm[i + 1]) {
            return false;
        }
        if(a[i] == '>' && perm[i] < perm[i + 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    int k;
    cin >> k;
    vector<char> a(k);
    for(int i = 0;i < k;i++) {
        cin >> a[i];
    }

    vector<int> small(k + 1);
    vector<int> big(k + 1);

    // 모든 경우의 수를 해볼 필요 없이
    // 최대, 최소의 값만 구하면 되기 때문
    for(int i = 0;i <= k;i++) {
        small[i] = i;
        big[i] = 9 - i;
    }

    do {
        if(check(small, a)) {
            break;
        }
    } while(next_permutation(small.begin(), small.end()));

    do {
        if(check(big, a)) {
            break;
        }
    } while(prev_permutation(big.begin(), big.end()));

    for(int i = 0;i < big.size();i++) {
        cout << big[i];
    }
    cout << '\n';

    for(int i = 0;i < small.size();i++) {
        cout << small[i];
    }
    cout << '\n';
}

 

💚1339번 단어 수학

0부터 9까지의 수를 나타낼 뿐이기에 10!의 경우의 수밖에 안된다.

그래서 각각의 알파벳에 0부터 9까지의 숫자를 적절히 대입하며 된다.

 

이 때 합의 최대값을 구하는 문제이기 땜누에 서로 다른 알파벳이 M개라면

큰 숫자 M개만 넣어서 조사해보면 된다.

 

예시 코드가 있었는데 예시 코드가 허술한 면이 있어서 코드를 보완하였다.

char 타입 배열에 Int 형 값을 저장하는 등에 오류는 발생하지 않으나, 이는 올바른 사용법은 아니라고 생각했기 때문이다.

 

여기서 파악하면 좋은 메소드는 unique이다.

unique 실행 시 중복되는 인덱스는 모두 벡터 뒤에 몰려있고, 중복되는 값들이 시작되는 인덱스가 리턴된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int alpha[26];
int calc(vector<string> &a, vector<char> &letters, vector<int> &d) {
    // 알파벳별 숫자 저장
    // letter와 숫자 매칭
    int m = letters.size();
    int sum = 0;
    for(int i = 0;i < m;i++) {
        alpha[letters[i] - 'A'] = d[i];
    }

    for(string s : a) {
        int now = 0;
        for(char x : s) {
            now = now * 10 + alpha[x - 'A'];
        }
        sum += now;
    }

    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<string> a(n);
    vector<char> letters;

    for(int i = 0;i < n;i++) {
        cin >> a[i];
        for(char x : a[i]) {
            letters.push_back(x);
        }
    }

    sort(letters.begin(), letters.end());
    // unique 실행 시 중복되는 인덱스는 모두 벡터 뒤에 몰려있고, 중복되는 값들이 시작되는 인덱스 리턴
    letters.erase(unique(letters.begin(), letters.end()), letters.end());

    int m = letters.size();

    // 알파벳에 해당하는 숫자 배열
    vector<int> d;

    // 모든 경우의 수를 다 고려할 필요는 없기 때문
    for(int i = 9;i > 9 - m;i--) {
        d.push_back(i);
    }

    sort(d.begin(), d.end());
    int ans = 0;

    do {
        int now = calc(a, letters, d);
        if(ans < now) {
            ans = now;
        }
    } while(next_permutation(d.begin(), d.end()));
    cout << ans << '\n';
    return 0;
}

 

💚14888번 연산자 끼워넣기

N <= 11이고, 연산자는 최대 10개이기 때문에, N! 가지로 모든 경우의 수를 순회하면 된다.

여기서는 minmax_element를 사용해 벡터 내 최소, 최대 요소를 추출한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int calc(vector<int> &a, vector<int> &b) {
    int n = a.size();
    int ans = a[0];
    // n - 1 번 순회
    for(int i = 1;i < n;i++) {
        if(b[i - 1] == 0) {
            ans += a[i];
        } else if(b[i - 1] == 1) {
            ans -= a[i];
        } else if(b[i - 1] == 2) {
            ans *= a[i];
        } else if(b[i - 1] == 3) {
            ans /= a[i];
        }
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }

    for(int i = 0;i < 4;i++) {
        int cnt;
        cin >> cnt;
        // 개수만큼 해당 연산자를 삽입
        for(int k = 0;k < cnt;k++) {
            b.push_back(i);
        }
    }

    sort(b.begin(), b.end());
    vector<int> result;
    do {
        int temp = calc(a,b);
        result.push_back(temp);
    } while(next_permutation(b.begin(), b.end()));

    // first에는 최솟값, second에는 최댓값
    auto ans = minmax_element(result.begin(), result.end());
    cout << *ans.second << '\n';
    cout << *ans.first << '\n';
    return 0;
}

 

💚14889번 스타트와 링크

- N명을 N / 2명씩 두 팀으로 나누려고 한다.(4 <= <= 20, N은 짝수)

- 두 팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제

- S[i][j] = i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치

- 팀의 능력치: 팀에 속한 모든 쌍의 S[i][j]의 합

 

스타트와 링크 팀을 각각 1팀, 2팀으로 표기한다면 순열로 풀 수 있다.

이 문제를 순열로 풀 수 있는 것은 각 팀의 사람 수가 정해져있기 때문에 가능하다.

 

최대 경우의 수를 구하면 20! / 10! 10! 으로 수가 크지 않아서 BruteForce가 가능하다.

왜냐하면 1은 동일한 역할을 수행하고, 차이가 없기 때문이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    vector<int> b(n);
    for (int i = 0; i < n / 2; i++) {
        b[i] = 1;
    }

    sort(b.begin(), b.end());

    int ans = (1 << 7) - 1;
    do {
        vector<int> first, second;
        for(int i = 0;i < n;i++) {
            if(b[i] == 0) {
                first.push_back(i);
            } else {
                second.push_back(i);
            }
        }

        int one = 0;
        int two = 0;
        // 행렬 방문 최소화
        for(int i = 0;i < n / 2;i++) {
            for(int j = i + 1;j < n / 2;j++) {
                one += a[first[i]][first[j]];
                one += a[first[j]][first[i]];
                two += a[second[i]][second[j]];
                two += a[second[j]][second[i]];
            }
        }

        int diff = one - two;
        if(diff < 0) diff = -diff;
        if(ans > diff) ans = diff;
    } while(next_permutation(b.begin(), b.end()));

    cout << ans << '\n';
    return 0;
}

 

첫 번째 강의였는데 벌써 많은 메서드와 스킬을 습득하였다..역시 강의를 듣는 데는 이유가 있다..

순열에는 next_permutation, prev_permutation을 사용하고

이외에도 algorithm 헤더에는 unique, sort, minmax_element 와 같이 유용한 메서드들이 존재했다!