2개의 정렬된 배열을 합쳤을 때의 중간값 구하기
 대문  주제별 보기  함수사전  코드모음  바뀐글  목록   Anonymous
총 페이지 수 : 3224

전체 함수/용어사전
Facebook Joinc 그룹   Joinc QA 사이트
현재위치 : 미니사이트>Test>Middle_Merged



joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.

문제

2개의 정렬된 배열이 있다. 이를 합쳤을 때, 중간값을 찾아야 한다.

문제에 의견

일반적인 합병정렬을 이용하면 문제를 해결할 수 있을 것이다. 하지만 중간값을 찾는다고 한다면, 완전한 합병정렬을 할 필요가 없을 것이다. 그렇다면 어딘가에 성능을 개선할 여지가 있을 것이다.

일반적인 합병정렬

전형적인 합병정렬이다. 이미 만들어진 코드를 참고하기 바란다. 일반적이지만 성능개선은 기대할 수 없다.

성능 개선

중간값이 필요하다면, 굳이 완전한 합병정렬의 필요가 없을 것이다. 일부분에 대한 합병정렬만으로도 원하는 값을 찾아낼 수 있다.

     +---------------------------------------+ 
     | Array A                               | 
     +---------------------------------------+ 
        +---------+    |     +--+   
        |         |    |     |  |    Array B 
        +---------+    |     +--+ 
                       | 
                   <---| 이동
다음과 같은 방법을 이용할 수 있을 것이다.
  1. Array A의 중간값을 찾는다.
  2. Array A와 Array B를 비교한다. 그러면 새로 추가될 원소의 갯수를 파악할 수 있을 것이다.
  3. Array A의 중간값을 기준으로 좌 우 각각 어느쪽에 몇개의 원소가 추가되었는지 확인할 수 있을 것이다.
  4. 만약 좌에 5개 우에 1개의 원소가 추가되었다면, Array A의 중간값의 위치를 왼쪽으로 2만큼 이동시키면 된다.
  5. 이때 이동은 Array A와 Array B 모두를 고려해야 하므로 합병정렬에서의 비교연산이 들어가게 될 것이다.

아이디어 자체는 문제가 없을 거라 생각된다.

예외사항

이 예외 사항은 Array A와 Array B의 원소가 중복되지 않을 경우에 해당된다.

배열과 배열의 범위가 겹치지 않을 때 


  +----------++---------------------+ 
  | Array B  || Array A             | 
  +----------++---------------------+
  • 전체배열의 크기 / 2 만큼해서 이동시키면 되겠다.
    • Array B의 max를 기준으로 하면 앞뒤로 얼마만큼 이동해야 할지 결정할 수 있다.
      • 예) Size B = 10, Size A = 20 이라면, A에서 5만큼 이동
    • 윗 절의 성능개선방식을 적용해도 문제를 풀 수 있다.
      • 새로 추가되는 원소가 10 이므로 index를 기준으로 해서 앞으로 5 (10/5)만큼 이동시키면 된다. 결국 A[5]를 읽어들이게 될 것이다.

    C++/C 코드

    아직 완성된 코드는 아니다. 아마 제대로 돌아가지 않을 것이지만 대략 방법은 알 수 있을 것 같다. 어떻게 구현될 수 있는지만 신경썼다. 깔끔하게 만드는건 내일쯤 해볼 생각이다. 
    #include <stdio.h> 
#include <vector> 
 
using namespace std; 
 
int find_middle(int *a, int size_a, int *b, int size_b); 
void show_array(int *a, int size_a, int *b, int size_b); 
int lsearch(int *sp, int size_sp, int search_n); 
 
int main(int argc, char **argv) 
{ 
        int a[] = {5, 8, 10, 14, 19, 20, 25, 30, 33, 35, 39}; 
        int b[] = {5, 8, 25}; 
 
        show_array(a, sizeof(a)/4, b, sizeof(b)/4); 
        find_middle(a, sizeof(a)/4, b, sizeof(b)/4); 
        return 0; 
} 
 
int find_middle(int *a, int size_a, int *b, int size_b) 
{ 
        int *largep; 
        int *smallp; 
        int smallsize; 
        int largesize; 
        int idx; 
        if (size_a > size_b) 
        { 
                largep = a; 
                smallp = b; 
                idx = size_a/2; 
                smallsize = size_b; 
                largesize = size_a; 
        } 
        else 
        { 
                largep = b; 
                smallp = a; 
                smallsize = size_a; 
                largesize = size_b; 
                idx = size_b/2; 
        } 
 
        // large array의 중간값보다 작은 값의 범위에 대해서 
        int li = 0; 
        int si = 0; 
        int left_size=0; 
        int leftsame=0; 
        int same=0; 
        printf("pivot : %d %d\n", idx, largep[idx]); 
 
        printf("Large %d , Small %d\n", largesize, smallsize); 
        while(1) 
        { 
                if (li == largesize-1 && si == smallsize-1) break; 
 
                printf("%d %d\n", largep[li], smallp[si]); 
                if (largep[li] == smallp[si]) 
                { 
                    same++; 
                    if (li < idx) leftsame++; 
                    if (li < largesize-1) 
                        li++; 
                    if (si < smallsize-1) 
                        si++; 
                } 
                else if(largep[li] > smallp[si]) 
                { 
                    if (si < smallsize-1) 
                        si++; 
                    else 
                        li++; 
                } 
                else 
                { 
                    if (li < largesize-1) 
                        li++; 
                } 
                sleep(1); 
        } 
 
        printf("Small Insert Size %d %d\n", leftsame, same); 
 
        // large array의 중간값보다 큰것들 비교 
        int right_size = 0; 
        same = 0; 
        int small_center = si; 
        printf("small Center : %d\n", si); 
        printf("Center %d\n", largep[li]); 
 
 
        right_size -= same; 
        printf("Large insert %d\n", right_size); 
 
        int offset = (right_size - left_size)/2; 
 
        // 대략 idx를 기준으로 앞으로 2만큼 이동시킨게 중간값임을 알 수 있다. 
        // 이제 실제 idx를 이동시키면서 원하는 값을 찾아보자. 
 
        printf("Offset is %d\n", offset); 
        int big_center = size_a/2; 
        int value; 
        if (offset > 0) 
        { 
            while(offset) 
            { 
                if (largep[big_center] > smallp[small_center]) 
                { 
                    big_center --; 
                    offset --; 
                    value = largep[big_center]; 
                } 
                else if (largep[big_center] < smallp[small_center]) 
                { 
                    small_center --; 
                    offset --; 
                    value = smallp[small_center]; 
                } 
                else 
                { 
                    small_center --; 
                    big_center --; 
                    value = smallp[small_center]; 
                } 
            } 
            printf("[1] middle Value : %d \n", value); 
        } 
        else 
        { 
            value = largep[big_center]; 
            while(offset) 
            { 
                if (largep[big_center] < smallp[small_center]) 
                { 
                    big_center ++; 
                    offset ++; 
                    value = largep[big_center]; 
                } 
                else if (largep[big_center] > smallp[small_center]) 
                { 
                    small_center ++; 
                    offset ++; 
                    value = smallp[small_center]; 
                } 
                else 
                { 
                    small_center ++; 
                    big_center ++; 
                    value = smallp[small_center]; 
                } 
            } 
            printf("[2] middle Value : %d\n", value); 
        } 
 
        return 0; 
} 
 
// 경우에 따라서 binary 검색으로 할 수 있다. 
int lsearch(int *sp, int size_sp, int search_n) 
{ 
        int i = 0; 
        while(i < size_sp) 
        { 
                if ( *(sp+i) > search_n) 
                        return i; 
                i++; 
        } 
        return 0; 
} 
 
void show_array(int *a, int size_a, int *b, int size_b) 
{ 
    int i = 0; 
    printf("[ "); 
    for(i = 0; i < size_a; i++) 
    { 
        printf("%d ",a[i]); 
    } 
    printf("]\n"); 
 
    printf("[ "); 
    for(i = 0; i < size_b; i++) 
    { 
        printf("%d ",b[i]); 
    } 
    printf("]\n"); 
}

    해야할일

    1. 위의 개선사항을 코드화해서 테스트해본다.
    2. 잘 돌아가는 가 ?
    3. 잘 돌아가지 않는다면, 문제점을 찾아본다. 혹은 방식자체가 잘못되었을 수도 있다.
    4. 잘 돌아간다면, 왜 잘 돌아가는지 (직관이 아닌)증명할 수 있는가 ?
    5. 그렇다면 위치를 인자로 받아서, 해당 위치의 값을 얻어올 수 있도록 코드를 수정할 수 있을까 ?
      1. 정렬된 배열의 70% 지점에 있는 값
      2. 정열된 배열의 60% 에서 70% 지점에 있는 값
    		•
    Email을 기입하면, 댓글이 메일로 전달됩니다.