프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 책 내용 정리입니다.

19.1 도입

• 일렬로 늘어선 자료들
• 특정 순서로 넣고 특정 순서로 꺼낼 수 있음

큐 queue

• 가장 먼저 들어간 자료를 가장 먼저 꺼낸다.
• 선입선출 (FIFO, First In First Out)
• ex) 놀이공원 줄

스택 stack

• 한 쪽 끝에서만 자료를 넣고 뺀다 : 가장 늦게 들어간 자료를 가장 먼저 꺼낸다
• 후입선출 (LIFO, Last In First Out)
• 컴퓨터는 내부적으로 스택을 사용해 함수들의 문맥 관리

데크 dequeue

• 양쪽 끝에서 자료를 넣고 뺄 수 있음

작업

• push : 자료를 넣는 작업
• pop : 자료를 꺼내는 작업

→ $O(1)$에 이루어져야 함

19.2 큐와 스택, 데크의 구현

연결 리스트

• 장점: 모든 연산이 상수 시간이어야 한다는 요구 조건 쉽게 충족
• 단점: 노드의 할당, 삭제, 포인터를 따라가는데 시간 소요

동적 배열

• 스택 : 그냥 하면 됨
• 큐, 덱
  • 배열의 맨 앞에서 원소를 삭제하려면 $O(n)$
  • 환형 버퍼 (circular buffer)
    • 처음, 마지막 원소의 위치를 head, tail에 유지
    • 맨 앞에서 원소를 꺼낼 때, head를 다음 원소로 옮김

    cf) 실제 대부분은 tail이 마지막 원소 다음 위치: 텅 빈 큐 구현

표준 라이브러리

이미 구현되어 있다!

19.3 스택과 큐의 활용

큐: 조세푸스 문제

죽을 사람을 가리키는 포인터를 옮기는 대신, 사람들을 움직인다.

1. 큐의 첫 번째 사람이 나와서 죽고
2. 큐의 맨 앞에 있는 사람을 맨 뒤로 보내는 작업을 k -1 번 반복

스택: 울타리 자르기 문제 (FENCE)

분할정복: $O(NlogN)$

스택: $O(N)$

최대 사각형: 어떤 판자를 완전히 포함하는 사각형 중 면적이 최대인 사각형

특징:

• 이 사각형의 높이는 i번 판자와 항상 같다
• 이 사각형의 왼쪽 끝과 오른쪽 끝은 i번 판자보다 낮다 → left[i], right[i]

최대 사각형의 넓이: (right[i] - left[i] - 1) * h[i]

left[i], right[i]를 찾는 알고리즘은 판자의 개수에 비례하는 시간이 걸림

전체 알고리즘은 $O(N^2)$이 걸림!

모든 판자에 대해 left[i], right[i]를 상수 시간에 찾는 법?

→ 다른 판자에 대해 계산했던 정보 재활용!

스위핑 알고리즘의 설계

맨 왼쪽 0번 판자부터 순서대로 각 판자를 처리.

• i번째 판자가 맨 왼쪽/오른쪽에 있을 경우에 대비해 입력으로 주어진 판자들의 양쪽 끝에 높이 0인 판자 첨가

---

0번 판자

left[0] = -1

right[0] : 지금 계산할 방법 없음

1번 판자

• h[0] > h[1] 인 경우 (1번 판자의 높이가 낮다)

  right[0] = 1

  → 0번 판자의 최대 사각형 찾음

  이후 0번 판자는 더이상 의미가 없음

  • 1번 판자가 더 낮음 → 이후의 어떤 판자 i에 대해서도 left[i] = 0이 될 일이 없음

    → 0번 판자 지움

    왼쪽에는 아무런 판자도 없음

    → left[1] = -1

• h[0] < h[1] 인 경우 (1번 판자의 높이 높다)

  이전 판자가 left임..

  left[1] = 0

  right[0], right[1]은 알 수 없음

• h[0] == h[1] 인 경우 (두 판자의 높이가 같다)

  두 판자의 최대 사각형은 완전히 똑같음

  → 0번 판자를 남겨둘 이유 없음

  → h[0] > h[1]인 경우와 똑같이 처리

---

일반화

i번 판자..

왼쪽에 자신보다 높은 판자들이 남아 있다면, 그들의 최대 사각형을 자신이 막고 있음

→ 이들 전부에 대해 최대 사각형의 넓이를 계산하고 이들을 지워버림

결과: i번 판자 왼쪽에는 자신보다 낮은 판자만 있음 → left[i]를 항상 알 수 있음

// 각 판자의 높이를 저장하는 배 열 
vector<int> h;
// 스택을 사용한 o (n) 해법 
int solveStack() 
{
	// 남아 있는 판자들의 위치들을 저장한다. 
	stack<int> remaining;
	h.push_back(0);
	int ret = 0;
	for (int i = 0; i < h.size() ; ++i) 
	{
		// 남아 있는 판자들 중 오른쪽 끝 판자가 h[il보다 높다면 
		// 이 판자의 최대 사각형은 i에서 끝난다.
		while ( !remaining.empty() && h[remaining.top()] >= h [ i ] ) 
		{
			int j = remaining.top();
			remaining.pop();
			int width = -1;
			// j번째 판자 왼쪽에 판자가 하나도 안 남아 있는 경우 left[j]=-l ,
			// 아닌 경우 left(j]=남아 있는 판자 중 가장 오른쪽에 있는 판자의 번호 
			// 가 된다.
			if ( remaining.empty())
				width = i;
			else
				width = ( i - remaining.top() - 1 );
			ret = max(ret, h[j] * width);
		}
		remaining.push(i);
	}
	return ret;
}

시간복잡도

• while 문 내부가 몇 번 반복되는가?

  while문이 한 번 수행될 때마다 remaining에서 원소가 하나 빠짐

  remaining에는 정확히 N개의 원소가 들어감

  → while문의 총 수행 횟수는 $O(N)$

∴ $O(N)$으로 문제 해결 가능

19.4 문제: 짝이 맞지 않는 괄호 (BRACKETS2)

여는 괄호: 스택에 push

닫는 괄호: 스택 맨 위의 괄호와 맞춰봄

→ 안 맞으면 오류

💡실수!
1. 스택에서 여는 괄호 꺼내려고 하는데, 스택이 비어 있는 경우
2. 마지막에 열린 괄호가 남아 있는지 확인

💡꿀팁!
여는 괄호/닫는 괄호의 목록을 문자열에 저장
→ 문자가 여는 괄호인지/짝이 맞는지 쉽게 확인

bool wellMatched(const string& formula) 
{
	// 여는 괄호 문자들과 닫는 괄호 문자들
	const string opening("({["), closing(")}]");
	// 이미 열린 괄호들을 순서대로 담는 스택
	stack<char> openStack;
	for(int i = 0; i < formula.size(); ++i)
		// 여는 괄호인지 닫는 괄호인지 확인한다 
		if(opening.find(formula[i]) != -1)
			// 여는 괄호라면 무조건 스택 에 집어넣는다. 
			openStack.push(formula[i]); 
		else 
		{
			// 이 외의 경우 스택 맨 위의 문자와 맞춰보자.
			// 스택이 비어 있는 경우에는 실패 
			if(openStack.empty()) return false;
			// 서로 짝이 맞지 않아도 실패
			if(opening.find(openStack.top()) != closing.find(formula[i])) 
			return false;
			// 짝을 맞춘 괄호는 스택에서 뺀다. 
			openStack.pop();
		}
	// 닫히지 않은 괄호가 없어야 성공 
	return openStack.empty();
}

19.6 문제: 외계 신호 분석 (ITES)

수열이 주어질 때, head와 tail 사이 구간을 검사한다.

구간합이 K 이상이 되었을 경우, 더 이상 구간의 길이를 늘려봐야 답을 찾을 수 없다.

종료하기 전에 마지막으로 검사한 구간.. head가 정해져 있을 때 이 구간 외의 구간은 답이 될 수 없다. 후보 구간이라 부르다.

head가 늘어났을 때 tail이 줄어드는 일은 없다.

head가 증가했는데, tail이 감소 했다면 이 후보 구간은 이전 후보 구간의 일부가 된다.

이 구간의 합이 이미 K 이상이라면 이전 후보 구간은 더 일찍 끝났어야 하므로, 이런 경우는 있을 수 없다.

⇒ 후보 구간의 tail을 찾을 때 head에서 시작하지 말고 마지막에 찾았던 tail에서부터 시작하자!

head가 증가하고 나면 지나쳐온 숫자들은 고려할 필요 없음: 후보 구간에 포함된 숫자들만 저장하면 됨

//코드 19.4 외계 신호 분석 문제를 해결하는 최적화된 알고리즘
int optimized(const vector<int>& signals, int k) { 
int ret = 0, tail = 0, rangeSum = signals[0]; 
for(int head = 0; head < signals.sizeO; ++head) {
	// rangeSum이 k 이상인 최초의 구간을 만날 때까지 tail을 옮긴다. 
	while(rangeSum < k && tail + 1 < signals.size《)) 
	rangeSum += s gnals[++tail];
	f(rangeSum = k) ret++;
	// signalsthead]는 이제 구간에서 빠진다. 
	rangeSum -= signals[head];
}
return ret;

시간복잡도

중첩 반복문..

while문의 내부가 실행될 때마다 tail은 증가

tail은 0부터 N까지 증가하므로, while문의 내부는 최대 N번 수행됨.

분할 상환 분석을 이용하면 코드 19.4의 시간 복잡도는 $O(N)$이다.