주가 스팬 계산하기

https://pixabay.com/ko/photos/%EC%A3%BC%EC%8B%9D-%EB%AC%B4%EC%97%AD-%EB%AA%A8%EB%8B%88%ED%84%B0-%EC%82%AC%EC%97%85-1863880/

 길벗에서 출판한 책 <리얼월드 알고리즘>에서 처음으로 나오는 알고리즘은 스택을 이용한 주가 스팬 계산입니다. 마침 스택에 대한 포스트도 연이어 작성 중인 와중에 이 책을 읽고 있어 잘됐다 싶어 포스트 주제로 선정하게 되었습니다.

 주가 스팬을 구하는 기본적인 알고리즘 구조는 책에서 보실 수 있습니다. 저는 이 책에서 선보이는 의사 코드(pseudo code)를 C언어로 재구성하고자 합니다.

---

주가 스팬?

 먼저 문제를 풀어보기 전에 주가 스팬이 무엇인지 알아봅니다. 주가 스팬은 다음과 같습니다.

 왼쪽과 같은 주식 그래프가 존재한다고 생각해봅시다. 이때 1번 그래프는 앞에 주가 스팬을 판단할 값이 존재하지 않으므로 1번의 그래프 주가 스팬은 1입니다.

 2번 그래프는 1번 그래프보다 값이 크므로 주가 스팬은 2입니다. 이는 5번 그래프도 마찬가지로 작동하여 5번 그래프의 주가 스팬은 5가 됩니다.

 5번 그래프보다 작지만 앞선 6, 7번 그래프보단 큰 8번 그래프는 주가 스팬으로 3의 값을 가집니다. 7번 그래프 값은 6번 그래프와 같으므로 5번 그래프에 의해 7번 그래프는 2의 주가 스팬을 가지게 됩니다.

 이러한 사실을 토대로 주가 스팬의 값은 아래 법칙에 의해 결정됩니다.

"배열에서 본인보다 앞선 값 중 본인보다 크고 가장 가까운 값까지의 거리"

 예시로 든 그래프를 계산하면 아래 표와 같습니다.

그래프 순번	그래프 값	주가 스팬
1	4	1
2	6	2
3	5	1
4	3	1
5	8	5
6	5	1
7	5	2
8	7	3

---

프로그램 작성

 책에서 설명하기를, "주가 스팬은 스택을 이용하면 풀기 쉽다."라고 합니다. 따라서 저도 스택을 이용하겠습니다. 이 프로그램에서 사용하는 스택은 다음 링크에서 이용하는 함수들을 이용합니다. 혹은 아래 파일을 다운로드해도 됩니다.

 

pang2hStack.c

0.00MB

---

int main(void){
	stack* sq = CreateStack();
	int    arr[100];
	int output[100];
	int graphSize; // 그래프 크기
	
	scanf("%d", &graphSize);
	for(int i = 0; i < graphSize;++i){
		scanf("%d", arr + i);
	}
	
	DeleteStack(sq);
	return 0;
}

 여기서부터 시작하겠습니다. 그래프 길이를 먼저 받고, 받은 길이만큼 데이터를 받습니다.

 맨 처음 그래프는 판단할 필요가 없으니 output[0]에는 0을 대입합니다. 또한 0번 인덱스, 즉 맨 처음 들어온 그래프 값이 현재의 최댓값이므로 스택에 쌓아줍니다.

	output[0] = 1;
	push(sq, 0);

 이제 비교를 진행합니다. 처음 받은 데이터만 제외하고 모두 비교하면 되므로 n - 1번 반복하는 반복문을 작성합니다.

for(int i = 1; i < graphSize;++i){

}

 가장 높은 값을 가진 인덱스는 스택에 존재합니다. 그러므로 스택에서 현재 비교하는 값보다 작은 값을 가진 인덱스는 빼버립니다. 스택에 값이 존재하지 않은 경우 연산을 진행하지 않도록 isEmpty() 함수도 조건에 넣어주는 것은 잊지 말아야 합니다.

for(int i = 1; i < graphSize;++i){
        while(!isEmpty(sq) && arr[top(sq)] <= arr[i]){
        	pop(sq);
        }
        
        if(!isEmpty(sq)){
        	output[i] = i - top(sq);
        }else{
        	output[i] = i + 1;
        }
        
        push(sq, i);
}

 이제 주가 스팬을 계산하는 문제만 남았습니다. 바로 앞선 연산을 통해서 우리는 스택에 현재 값보다 큰 값이 든 인덱스가 존재함을 알고 있습니다. 따라서 스택에 값이 있다면(스택이 비어있지 않다면) 우리는 그 값을 가져와서 빼주면 됩니다. 만일 스택이 비어있다면 현재 값은 여태 나온 값 중 가장 큰 값이 되므로 주가 스팬은 현재 인덱스에 + 1 한 값이 됩니다.

 이렇게 끝내지 않고 다음 값의 스팬 계산을 위해 현재 인덱스를 push 해 스택에 넣어줍니다.

 이렇게 작성하면 프로그램은 입력에 대한 주가 스팬을 계산해 output 배열에 보관합니다. 마지막으로 제대로 계산이 이루어지는지 확인용 출력 코드를 작성합니다.

for(int i = 0 ; i < graphSize;++i){
	printf("%d %d\n", arr[i], output[i]);
}

---

코드 완성

이렇게 작성한 후 모든 코드는 다음과 같습니다. 스택에 대한 코드는 제외했습니다.

int main(void){
	stack* sq = CreateStack();
	int    arr[100];
	int output[100];
	int graphSize; // 그래프 크기
	
	scanf("%d", &graphSize);
	for(int i = 0; i < graphSize;++i){
		scanf("%d", arr + i);
	}
	
	output[0] = 1;
	push(sq, 0);
	for(int i = 1; i < graphSize;++i){
		while(!isEmpty(sq) && arr[top(sq)] <= arr[i]) pop(sq);
		
		if(isEmpty(sq)) output[i] = i + 1;
		else output[i] = i - top(sq);
		/* // 위 코드와 상동
		 if(!isEmpty(sq)) output[i] = i - top(sq);
		 else output[i] = i + 1;
		
		*/
		push(sq, i);
	}
	
	for(int i = 0 ; i < graphSize;++i){
		printf("%d %d\n", arr[i], output[i]);
	}
	
	DeleteStack(sq);
	return 0;
}

 이제 이 프로그램으로 예시로 보여드린 그래프를 작성하면 아래와 같은 결과를 받을 수 있습니다.

 처음 두 줄(8과 4 6 ...)은 입력, 이후 여덟 줄은 그에 대한 출력입니다.

---

마치며

 처음 이 코드를 보고 이렇게 진행할 수도 있구나 하는 생각이 들었습니다. 평소에는 원하는 프로그램을 만들려고 하면 그 프로그램에 필요한 기술들을 잠깐 검색해서 배워 쓰곤 했는데 확실히 알고리즘 책을 읽으면서 직접 해보는 것은 잠깐 배우는 것과 다름을 알게 됐습니다. 많은 시험에서 알고리즘 문제가 나오는데 이번 기회에 알고리즘에 대해 심도 있는 공부를 해봐야 할 것 같습니다 :)

---

더 알아보기

주가 스팬 : 활용

# index