[정보처리기사][알고리즘][자료구조] 병합

Q. 배열 A,B에는 정수가 오름차순으로 정렬되어 있다. 데이터는 10건 미만이다. 배열 A,B에서 0이 들어있는 다음의 요소에는 데이터가 없는 것으로 간주한다. 배열 A,B를 병합시켜 배열 C에 기억시키고 맨 마지막에는 0을 기억시킨다. 배열 A와 B에 같은 데이터가 있으면 한번만 C에 옮긴다.

 

%%%%복잡주의%%%%

1. 배열 A의 크리를 A(10), 배열 B의 크기를 B(10)으로 선언하고, 배열 C는 2개의 배열 크기를 합한  C(20)으로 선언한다. 

2. 배열 A의 첫 번째 자료를 지정하기 위해 배열 A의 위치를 지정하는 i를 1로 초기화한다.

 

3. 배열 B의 첫 번째 자료를 지정하기 위해 배열 B의 위치를 지정하는 j를 1로 초기화한다.

 

4. 배열 C의 위치를 지정하는 K를 0으로 초기화한다.

 

* AA위치 *

5. 배열 C위치를 증가시킨다. C배열의 첨자로 사용하는 변수가 무엇인지 생각한다.

 

6. 병합할 자료 A(i)와 B(j)를 비교하여 A(i)가 작으면 배열 A의 자료를 배열 C에 넣고 크면 배열 B의 자료를 배열 C에 넣고, 같으면 배열 A의 자료를 배열 C에 넣는다.

 

* 작은 경우 *

 

1) 배열 A의 자료를 배열 C에 저장한다.

 

2) 배열 A의 위치를 지정하는 i를 1 증가시킨다.

 

3) A(i)가 0이면 배열 A의 자료를 모두 처리한 것으로 배열 B의 자료를 배열 C에 넣기 위해 BB로 가고, 아니면 다음 자료를 처리하기 위해 AA로 간다.

 

* 같은 경우 *

 

1) 배열 A의 자료를 배열 C에 저장한다.

 

2) 배열 A의 위치를 지정하는 i를 1 증가시킨다.

 

3) 배열 B의 위치를 지정하는 j를 1 증사시킨다.

 

4) A(i)가 0이면 배열 A의 모든 자료를 처리한 것이므로, 배열 B의 나머지 자료를 배열 C에 넣기 위해 BB로 가고, 아니면 B(j)가 0인지 확인한다.

 

A. B(j)가 0이면 B의 모든 자료를 처리한 것이므로, 배열 A의 나머지 자료를 배열 C에 넣기 위해 CC로 가고, 아니면 다음 자료를 처리하기 위해 AA로 간다.

 

* 큰 경우 *

 

1) 배열 B의 자료를 배열 C에 저장한다.

 

2) 배열 B의 위치를 지정하는 j를 1 증가시킨다.

 

3) B(j)가 0이면 B배열의 모든 자료를 처리한 것이므로 배열 A의 나머지 자료를 배열 C에 넣기 위해 CC로 가고, 아니면 AA로 간다.

 

* BB위치 *

 

1. 배열 C의 위치를 지정한 K를 1 증가시킨다.

 

2. 배열 B의 자료를 배열 C에 저장한다.

 

3. 배열 B의 취리를 지정하는 j를 1 증가시킨다.

 

4. 배열 A의 자료를 모두 넣고 온것이므로 B(j)가 0이면 병합이 끝난 것이다. 그러므로 DD로 가고, 아니면 BB로 간다.

 

* CC위치 *

 

1. 배열 C의 위치를 지정하는 K를 1 증가시킨다.

 

2. 배열 A의 자료를 배열 C에 저장한다.

 

3. 배열 A의 위치를 지정하는 i를 1 증가시킨다.

 

4. 배열 B의 자료를 모두 넣고 온것이므로 A(i)가 0이면 병합이 끝난 것이다. 그러므로 DD로 가고, 아니면 CC로 간다.

 

* DD위치 *

 

1. 배열 C의 위치를 지정하는 K를 1 증가시킨다.

 

2. 병합된 배열 C의 맨마지막 요소에 0을 넣고 끝낸다.

 

 

해당 글은 제가 만든 어플을 기준으로 작성하였습니다.

더 많은 자료는 알고리즘 어플을 참조해주세요.