Page 238 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

스택에 쌓인 데이터가 가장 많을 때는 e 와 h 입니다. 따라서 스택의 용량은 3 이상이어야 합

니다. 이때 배열을 나눈 뒤에 얻는 왼쪽 그룹, 오른쪽 그룹의 요소 개수를 비교하여 그 많고 적
음에 따라 푸시 순서를 바꾸면 스택에 쌓이는 데이터의 개수를 조절할 수 있습니다. 푸시 순서
는 아래처럼 두 가지 방법을 사용할 수 있습니다.

1. 요소의 개수가 많은 그룹을 먼저 푸시합니다.
2. 요소의 개수가 적은 그룹을 먼저 푸시합니다.

이 두 가지 방법의 차이를 구체적인 예를 들어 살펴보겠습니다.

1. 요소의 개수가 많은 그룹을 먼저 푸시하는 경우
예를 들어 b 에서 꺼낸 a[0] ~ a[7]은 a[0] ~ a[1], a[2] ~ a[7]로 나누어집니다. 요소의 개수가
많은 {2, 7}을 먼저 푸시하면 스택은 c 처럼 됩니다. 먼저 팝되어 나누어지는 배열은 요소의 개
수가 적은 그룹 {0, 1}입니다( d ). 이렇게 하면 스택에 쌓여 있는 데이터의 최대 개수는 2가 됩니

다( c , f , i ).

요소의 개수가 많은 그룹을 먼저 푸시합니다.

{0, 7} {0, 7}을 분할 {2, 7}, {0, 1} {0, 1}을 분할 {2, 7}을 분할 {2, 5}, {6, 7}

0 1 6 7
0 7 2 7 2 7 2 5
a b c d e f

{6, 7}을 분할 {2, 5}를 분할 {2, 3}, {4, 5} {4, 5}를 분할 {2, 3}을 분할 종료

4 5
2 5 2 3 2 3
g h i j k l
[그림 6-25] 스택의 변화 과정(2)

238 C 알고리즘