CLOSE

Recommanded Free YOUTUBE Lecture: <% selectedImage %>

### 문제

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

### 문제에 의견

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

### 일반적인 합병정렬

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

### 성능 개선

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

```     +---------------------------------------+
| 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를 읽어들이게 될 것이다.

### 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(" 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(" 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% 지점에 있는 값