알고리즘 문제 해결 전략2 19장 큐와 스택, 데크 (1)

19.1 도입

현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예로 큐와 스택, 데크가 있음. 큐와 스택, 데크가 중요한 이유는 흔히 사용하게 되는 자료 구조의 형태에 이름을 붙였다는 데 있음. 

 

큐와 스택, 데크

큐와 스택, 데크는 일렬로 늘어선 같은 형태의 자료들을 저장함. 이때 세 자료 구조들을 구분하는 것은 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가입니다. 컴퓨터는 내부적으로 스택을 사용해 함수들의 문맥을 관리함. 데크는 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구조를 말함. 데크를 이용하면 스택과 큐를 모두 구현할 수 있음. 

 

19.2 큐와 스택, 데크의 구현

연결리스트의 경우 노드의 할당과 삭제 그리고  포인터를 따라가는 데 드는 데 시간이 걸리기 떄문에 여결 리스트가 가장 효율적인 구현은 아님. 동적 배열의 처음과 끝을 붙여 원형으로 만들었다고 생각할 수도 있음. 때문에 이와 같은 배열의 구현을 대개 환형 버퍼라고 부름. 

 

19.3 스택과 큐의 활용

예제:큐를 이용한 조세푸스 문제의 해법

연결 리스트를 사용하는 18.3절의 연습 문제 조세푸스 문제의 해법. 죽을 사람을 가리키는 포인터를 옮기는 대신 사람들을 움직이는 것. 그러면 다음 과정을 큐에 두 명이 남을 때까지 반복해서 문제를 풀 수 있습니다. 

 

예제:스택을 이용한 울타리 자르기 문제의 해법

어떤 파나자를 완전히 포함하는 사각형 중 면적이 최대인 사각형을 해당 판자의 최대 사각형이라고 부름. left[i], right[i]를 알고 있으면 최대 사각형의 넓이를 구할 수 있음. 열쇠는 각 판자에 대해 문제를 따로 푸는 것이 아니라 다른 판자에 대해 계산했던 정보를 재활용하는 것임.

 

스위핑 알고리즘의 설계

1번 판자의 높이와 0번 판자의 높이 중 어느 쪽이 더 클까요. 경우를 나눠 생각해봅니다. 가로 화살표는 최대 사각형의 너비를 나타냄. 이때 아직 지워지지 않은 판자들을 어디에 내버려 둬야 할까요. 좋은 방법은 이들을 스택에 집어넣는 것입니다. 

 

구현

vector<int> h;
int solveStack() {
	stack<int> remaining;
	h.push_back(0);
	int ret = 0;
	for (int i = 0; i < h.size(); i++) {
		while (!remaining.empty() && h[remaining.top()] >= h[i]) {
			int j = remaining.top();
			remaining.pop();
			int width = -1;
			if (remaining.empty())
				width = i;
			else
				width = (i - remaining.top() - 1);
			ret = max(ret, h[j] * width);
		}
		remaining.push(i);
	}
	return ret;
}

이 알고리즘의 시간 복잡도를 분석하려면 와일문 내부가 몇 번이나 반복되는지를 알아야 함. 와일문이 한 번 수행될 때마다 remaining에서 원소가 하나 빠지는데, remianing에는 정확히 N개의 원소가 들어가기 때문에 while문의 총 수행 횟수는 O(N)임.