BOJ14888 연산자 끼워넣기

2017 하반기 삼성전자 기출문제 (2번)

1. 문제링크 : BOJ14888 연산자 끼워넣기

2. 문제요약
  - N개의 자연수 수열이 주어진다.
  - 수열의 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어짐
  - 연산자는 덧셈, 뺄셈, 곱셈, 나눗셈 으로만 이루어짐.

GOAL : 만들수 있는 식의 최대값과 최소값 구하기

EX) 1 2 3 4 가 주어짐 (N=4) , ( +, + , *) 가 주어짐 (N-1=3)
 경우의수
 (1) 1+2+3*4 = 15
 (2) 1+2*3+4 = 11
 (3) 1*2+3+4 = 9

경우의 수는 3!/2! 임으로 3개.
이때 최대값은 15 최소값은 9

3. 문제풀이
  - 수열의 순서는 바뀌지 않음으로 연산자의 순열의 경우의 수만 세주면됨
  - 가장 단순한 방법은 C++의 next_permutation을 이용해 연산자의 순열의 경우를 다 따져서 계산해보면 됨
 - DFS나 BFS를 이용하여 브루트 포스를 수행할 수도 있음.
 - DFS의 경우 연산자를 하나씩 정해가며 다음 단계로 진행하고 모두 진행했을 경우 이전단계로 돌아와 다른 연산자를 고르고 다음단계로 진행, 추후 마지막 단계에서 계산을 수행
 - BFS의 경우 각 노드별로 다른 연산자를 선택하고 큐에 넣은다음 다음단계로 진행하며 마지막 단계에서 계산을 수행

4. 소스코드 ( C )
- DFS 이용

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PLUS 1
#define MINUS 2
#define MUL 3
#define DIV 4
int oper[13];
int su[13];
int num[5];
int max;
int min;
int n;
int k;

void dfs(int start){
    if(start==k){
        int temp=su[0];
        for(int i=1;i<n;i++){
            int op=i-1;
            if(oper[op]==PLUS)
                temp+=su[i];
            else if(oper[op]==MINUS)
                temp-=su[i];
            else if(oper[op]==MUL)
                temp*=su[i];
            else if(oper[op]==DIV)
                temp/=su[i];

            
        }
        if(temp>max)
            max=temp;
        if(temp<min)
            min=temp;
    }

    for(int i=1;i<=4;i++){
        if(num[i]>0){
            oper[start]=i;
            num[i]--;
            dfs(start+1);
            num[i]++;
        }
    }
}

int main(void){
    max=-2000000000;
    min=2000000000;
    scanf("%d",&n);
    k=n-1;
    for(int i=0;i<n;i++){
        scanf("%d",&su[i]);
    }
    for(int i=1;i<=4;i++){
        scanf("%d",&num[i]);
    }
    dfs(0);

    printf("%d\n%d\n",max,min);
    return 0;
}

2018 SCPC 1차 풀이

1번
선수들의 실력을 가장 많이 포함하는 길이가 K이하인 구간을 찾았다고 합시다. 이 구간에 포함되는 선수들을 다른 버스를 타야하고 나머지 선수들은 구간에 포함된 선수 중 한명과 같은 버스를 탈 수 있습니다. 따라서 찾은 구간에 포함되는 선수들의 수를 출력하면 됩니다. 투포인터 테크닉을 써서 O(N)에 가능합니다.

2번
n=10000까지 회문인 수는 몇 개 안됩니다. (300개?) 모든 조합을 시도 해보는데 이분 탐색같은 걸로 시간을 줄여줍시다. DP도 가능할 듯 합니다.

3번
초기 상태에서 '>' 모양을 붙여서 나가는 대신 완성된 상태에서 가장 많이 떼내는 방법을 생각해봅시다. 때내는 정점은 Degree가 2여야 하고 그 정점과 연결된 정점을 u, v 라고 하면 그래프에 uv간선이 그래프에 포함되어 있어야 합니다. 생각해보면 어떤 정점을 떼내었을 때 다른걸 떼낼 수 없는 경우가 존재하지 않기 때문에 보이는대로 다 떼면 됩니다. 떼낼때 마다 그래프 갱신(Degree 수정, 간선 지우기)을 빠르게 하는게 관건입니다.

4번
Simulated annealing (SA)을 이용해서 만점을 받을 수 있습니다.
https://en.wikipedia.org/wiki/Simulated_annealing

예제로는 검증하기 힘드니 문제에 나와 있는 데이터 생성 방식을 참고하여 데이터를 많이 만듭니다. 처음에는 랜덤 순열부터 시작하여 랜덤하게 두 수의 자리를 바꾸는 방식으로 SA를 합니다. 상수를 조절하면서 변화를 관찰하고 제일 좋은 상수를 찾으면 됩니다. step횟수를 늘리기 위해서 새로운 상태를 계산하는 부분을 빠르게 구현해야 합니다.

Quick & Selection - Median of Medians

▪ 문제 요약

 k번째 큰 원소를 찾기

▪ 문제 풀이

1. 크기가 5인 배열으로 나눈다
2. *원소 5개중 중간값을 찾는다.
3. 그 중간값들 끼리 sorting을 한다.
4. 중간값들의 중간값을 pivot으로 설정한다.
5. pivot을 기준으로 pivot앞은 pivot보다 큰 원소, pivot뒤는 pivot보다 작은 원소가 되도록 정렬한다.
6. pivot의 index가 
6-1. k와 같으면 pivot을 retrun 
6-2. k보다 작으면 배열의 맨 앞~pivot바로 앞 까지 중간값의 중간값 다시 구해서 4번부터 다시
6-3. k보다 크면 pivot바로 뒤 ~ 배열의 맨 끝 까지 중간값의 중간값 다시 구해서 4번부터 다시

* 원소가 5개인 이유 : 5개 중에 중간값을 6번만에 찾을 수 있어서(더 좋은 효율을 내는 수도 있지만 가장 쉽다.)
* 5개중 중간값 구하는법 
① 랜덤으로 2쌍을 지어서 비교한다.(1쌍당 1번 : 비교 (2)) 
② 2쌍 중 이긴 것 끼리 비교한다.(3) 
③ ②에서 이긴 것은 적어도 2등이므로 중간인 3보다 크기 때문에 비교에서 제외한다. 
④ 제외된 것에게 ①에서 진 것과, 비교하지 않은 나머지 하나를 비교한다(4) 
⑤ 그 둘 중에 이긴 것과 ②에서 진 것과 비교한다.(5) 
⑥ 둘 중 큰 것은 마찬가지의 이유로 비교대상에서 제외한다. 
⑦ 제외된 것에게 진 것과 ②에서 진 것을 비교한다.(6) 
⑧ 둘 중 큰 값이 mid 값!

▪ 소스코드

#include <stdio.h>
#include <stdlib.h>


#define SWAP(x, y, t) t=x, x=y, y=t


int find_MM(int *ary, int low, int high);
int QSMM(int *ary, int low, int high, int k);
int part(int *ary, int low, int high, int pivotpoint);


int execute = 0;
int fir;


int main() {
    FILE *f;
    char filename[30];
    int *ary, pivot;
    //scanf("%s", filename);
    f = fopen(filename, "r");
    int size, k, i;
    scanf("%d %d", &size, &k);
    ary = (int *)malloc(sizeof(int) * size);
    
    for(i = 0; i < size; i++){
        scanf("%d", &ary[i]);
    }
    
    pivot = QSMM(ary, 0, size-1, k);
    
    printf("%d\n", pivot);
    printf("%d\n", fir);
}


int find_MM(int *ary, int low, int high){
    int i, j, *mid, mid_count;
    int n;
    n = high - low;
    mid = (int *)malloc(sizeof(int) * ((n/5)+1));
    i = low; j = 0;
    
    while(1){//배열을 5씩 나눠서 중간값 찾기
        if(i+4 > high)
            break;
        
        int group1[2], group2[2]; // 0이긴것 1진것
        
        int **WinGroupP; //이겼던 그룹을 가리키는 포인터 (3개보다 큰 것은 제거, 비교대상 추가를 위해)
        WinGroupP = (int **)malloc(sizeof(int *));
        *WinGroupP = (int *)malloc(sizeof(int) * 2);
        
        // 첫번째 쌍 비교 (1)
        if(ary[i] > ary[i+1]) { group1[0] = i; group1[1] = i+1; }
        else                  { group1[0] = i+1; group1[1] = i; }
        
        // 두번째 쌍 비교 (2)
        if(ary[i+2] > ary[i+3]) { group2[0] = i+2; group2[1] = i+3; }
        else                    { group2[0] = i+3; group2[1] = i+2; }
        
        // 이긴 것들 끼리 비교 (3)
        if(ary[group1[0]] > ary[group2[0]]) *WinGroupP = group1;
        else                                *WinGroupP = group2;
        
        // (이긴 그룹의 이긴것은 자기가 이긴것, 이긴 것은 진그룹의 진 것, 진그룹의 이긴 것보다 큼. 밑에3개있으므로 mid X)
        // 이긴그룹의 이긴것이 제외되었고, 이긴그룹의 진 것과 비교하지 않은 것을 비교 (4)
        // 이긴group[0]에 이긴그룹의 진 것과, 비교하지 않았던 것 중에 큰 것이 들어가고 [1]엔 작은것이 들어감.
        if(ary[(*WinGroupP)[1]] > ary[i+4])
        { (*WinGroupP)[0] = (*WinGroupP)[1]; (*WinGroupP)[1] = i+4; }
        else
        { (*WinGroupP)[0] = i+4; }
        
        // 또 두 쌍의 winner중에 큰 것을 비교대상에서 제외함(5)
        if(ary[group1[0]] > ary[group2[0]]) group1[0] = group1[1];
        else                                group2[0] = group2[1];
        
        // 이겼던 그룹의 진 것과 진 그룹의 이긴 것을 비교함(6)
        // 둘 중 큰 것이 mid값 (자기가 이긴것이 두개) or (자기가 이긴 것과 자기가 이긴 것이 이긴 것)
        if(ary[group1[0]] > ary[group2[0]]) mid[j] = group1[0];
        else                                mid[j] = group2[0];
        
        i += 5;
        j++;
    }
    
    int id = high-i;
    
    switch (id) { // 5로 나누어 떨어지지 않는 인덱스 처리
        case 4:
        case 3:
            mid[j] = ary[i] > ary[i+1]? i : i+1;
            j++;
            break;
            
        case 2:
        case 1:
            mid[j] = i;
            j++;
            break;
            
        default:
            break;
    }
    
    mid_count = j;
    int min, temp;
    
    for(i = 0; i < mid_count-1; i++){
        min = i;
        for(j = i+1; j < mid_count; j++){
            if(ary[mid[j]] < ary[mid[min]])
                min = j;
        }
        SWAP(mid[i], mid[min], temp);
    }
    
    if (!execute){
        fir = ary[mid[mid_count/2]];
        execute = 1;
    }
    int index = mid[mid_count/2];
    free(mid);
    return index; // index
}


int QSMM(int *ary, int low, int high, int k){
    int pivotpoint;
    
    if(low >= high) return ary[low];
    else{
        pivotpoint = find_MM(ary, low, high);
        pivotpoint = part(ary, low, high, pivotpoint);
        if(pivotpoint+1 == k) return ary[pivotpoint];
        else if(k < pivotpoint+1)
            return QSMM(ary, low, pivotpoint-1, k);
        else
            return QSMM(ary, pivotpoint+1, high, k);
    }
}


int part(int *ary, int low, int high, int pivotpoint){
    
    int temp, i, j, pivot = ary[pivotpoint];
    SWAP(ary[low], ary[pivotpoint], temp);
    
    i = low+1;
    j = high;
    
    while(i<=j){
        while(ary[i] > pivot && i<=j) i++;
        while (ary[j] < pivot && i<=j) j--;
        
        if(i<=j){
            SWAP(ary[i], ary[j], temp);
            i++; j--;
        }
    }
    
    SWAP(ary[low], ary[j], temp);
    
    return j;
}