순열

06 May 2021

Reading time ~2 minutes

순열 알고리즘

인자로 배열과, 순열 알고리즘의 시작 인덱스, 순열 알고리즘의 끝 인덱스를 받음
시작 인덱스와 끝 인덱스가 같다면, 원소가 하나이거나 모든 인덱스를 순회했다는 의미이므로 출력합니다.
인덱스가 서로 다르면, 시작부터 끝까지 모든 인덱스에 대해 시작 인덱스와 자리를 바꾸고 시작 인덱스를 1만큼 이동하여 재귀 함수를 호출한 후, 다시 자리를 바꾼 인덱스와 시작 인덱스의 자리를 스왑 (결과적으로, dfs의 느낌을 보입니다.)

알고리즘 구현

#include <iostream>

using namespace std;

void swap(char & a, char & b)
{
    char temp = a;
    a = b;
    b = temp;
}

void permutation(char data [], int depth, int n, int r)
{
    if (depth == r)
    {
        for(int i = 0; i < r; i++)
            cout << data[i] << " ";
        cout << endl;
        
        return;
    }
    
    for(int i = depth; i < n; i++)
    {
        swap(data[depth], data[i]);   // 스왑
        permutation(data, depth + 1, n, r);  // ⭐재귀
        swap(data[depth], data[i]);  // 다시 원래 위치로 되돌리기
    }
}

int main()
{
    char arr [] = {'a', 'b', 'c', 'd'};
    
    permutation(arr, 0, 4, 3); // 4P3

    return 0;
}

백준 - 연산자 끼워넣기(삼성기출)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N;
int cal_method[4];
vector<int> int_vec;
vector<int> answer_vec;
vector<int> now_cal_method; 
 
int calculator(){
    int answer = 0 ; 
 
    // 연산자에 따라서 다른 연산을 적용해준다.
    answer = int_vec[0];
    for ( int i = 0 ; i < N-1 ; i++){
        switch (now_cal_method[i]) {
            case 0:
                answer += int_vec[i+1];
                break;
            case 1:
                answer -= int_vec[i+1];
                break;
            case 2:
                answer *= int_vec[i+1];
                break;
            case 3:
                answer /= int_vec[i+1];
                break;
            default:
                break;
        }
    } 
    
    return answer;
}
 
void dfs(int depth){
    // 깊이의 마지막이면 답을 구한다.
    if (depth == N-1) {
        int now_val = calculator();
        answer_vec.push_back(now_val);
    }else{
        // 중간 깊이이면 다음 깊이를 구한다.
        for ( int i = 0 ; i < 4; i++){
            if (cal_method[i]){
                cal_method[i]--;
                now_cal_method.push_back(i);
                
                dfs(depth+1);
                
                cal_method[i]++;
                now_cal_method.pop_back();
            }
        }
    }
    
}
 
int main(){
    cin >> N;
    
    for ( int i = 0 ; i < N ; i++){
        int sub;
        scanf("%d", &sub);
        int_vec.push_back(sub);
    }
    
    for ( int i = 0 ; i < 4 ; i++)
        cin >> cal_method[i];
    
    // dfs를 이용해서 현재 연산자들을 결정한다.
    now_cal_method.clear();
    
    dfs(0);
    
    // 정렬
    sort(answer_vec.begin(), answer_vec.end());
    
    // 답 출력
    printf("%d\n%d", answer_vec.back(), answer_vec[0]);
    
    return 0;
}

Algorithm