[실전 알고리즘] 0x03강 - 스택, 큐, 덱_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x05강 - 스택, [실전 알고리즘] 0x06강 - 큐, [실전 알고리즘] 0x07강 - 덱 에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

 

 

이번 시간에는 스택, 큐, 덱 자료구조에 대해 배워보겠습니다.

 

 

스택을 들어본 적 있나요? 보통 스택이라고 하면 뭔가 잔뜩 쌓아놓은 이미지가 연상이 갈텐데, 컴퓨터 과학에서의 스택은 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조입니다. 프링글스 통을 생각하면 이해가 쉬울 것입니다. 구조상 먼저 들어간 원소가 제일 나중에 나오게 되는데, 이런 의미로 FILO(First In Last Out) 자료구조라고 부르기도 합니다.

 

큐, 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있습니다. 이런 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 합니다.

 

스택에서 원소의 추가/제거는 모두 $O(1)$입니다. 저번 강의에서 했던, 배열의 끝에서 원소를 추가/제거하는 것과 비슷하게 생각해보면 왜 $O(1)$인지 알 수 있을 것입니다.

 

그리고 제일 꼭대기의 원소를 확인하는 것 또한 $O(1)$입니다. 추가와 제거의 위치에 제한을 걸어서 모든 연산을 $O(1)$에 할 수 있습니다.

 

스택이 뭔지는 알았는데 어디에 써먹는지는 감이 잘 안올 것입니다. 어차피 배열로 다 할 수 있는거 아닌가라는 생각이 들 수도 있구요. 그렇지만 스택은 굉장히 응용 사례가 많습니다. 학부 과정에서 반드시 짚고 가는 응용 사례는 수식의 괄호 쌍, 전위/중위/후위/표기법, DFS, Flood Fill이 있습니다. 각 사례를 이 강의 안에 담기엔 양이 너무 많아 각각에 대한 독립적인 강의를 따로 만들 것입니다. 특히 DFS는 코딩테스트 단골 문제이기 때문에 반드시 익숙해져야 합니다.

 

문자열 뒤집기도 스택을 이용해 풀 수 있는 문제이긴 한데, 굳이 스택을 이용하는 것 보다 그냥 배열에서 for문을 한 번 역으로 돌리는게 훨씬 간편합니다.

 

이제 스택을 실제 코드에서 써먹을 시간입니다. STL에 Stack이 있기 때문에 그냥 가져다 쓰면 됩니다. 코드와 레퍼런스 사이트를 참고하세요.

 

만약 STL을 쓸 수 없는 상황이라고 하더라도 직접 배열로 구현을 하면 됩니다. 스택은 배열로 정말 간단하게 구현할 수 있는 자료구조입니다.

 

스택을 만들기 위해 필요한 변수는 dat, pos 2개입니다. dat는 원소의 값이 들어갈 배열이고 pos는 스택 내에 새로운 원소가 들어갈 위치입니다. 이 값은 스택 내의 원소의 갯수와 동일합니다. pos의 초기값은 0입니다.

 

 

스택에 10, 20, 30이 들어있는 것을 실제 코드 상의 배열과 변수는 이런 식으로 표현을 합니다.

 

 

이제 50을 스택에 넣는 과정을 step by step으로 이해해보겠습니다.

 

 

우선 pos가 가리키는 곳에 새로 삽입할 원소를 씁니다.

 

 

그리고 pos를 1 증가시키면 끝입니다.

 

 

굳이 두 줄로 하지 않고 증감연산자를 이용해 한 줄에 처리할 수도 있습니다.

 

 

삭제는 더 간단합니다. pos를 1 빼기만 하면 됩니다.

 

 

굳이 2번지의 30을 지우지 않더라도 관념적으로 더 이상 Stack에 속해있지 않은 값이기 때문에 상관없습니다. 만약 pos가 0일 경우에는 pop 함수를 실행하지 않아야 합니다. 저는 STL과의 통일성을 위해 pop 함수에서 예외처리를 하지 않았지만 편의에 따라 pop 함수에서 pos가 0인지를 확인하도록 수정해도 괜찮습니다.

 

 

꼭대기의 원소 확인은 그냥 dat[pos-1] 을 반환하기만 하면 됩니다. 삭제와 마찬가지로 pos가 0일 때 조심해야합니다.

 

BOJ 10828번 : 스택을 풀어봅시다. 이 문제는 스택을 충실하게 구현하면 되는 문제입니다. STL을 사용한 정답 코드와 배열로 직접 구현한 정답 코드 모두를 두었으니 둘 다 참고해보세요.

 

스택 다음에 큐를 살펴보겠습니다. 큐는 공항에서 줄을 서는 과정과 같이 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조입니다. 스택과는 반대로 먼저 들어간 원소가 제일 먼저 나온다는 의미로 FIFO(First In First Out) 자료구조라고 부르기도 합니다.

 

큐에서도 스택과 마찬가지 이유로 원소의 추가/제거, 제일 앞/제일 뒤에 위치한 원소의 확인이 모두 $O(1)$입니다.

 

큐는 BFS, Flood Fill에서 사용됩니다. 이 또한 마찬가지로 여기에서 다루지 않고 독립적인 강의에서 다루게 될 것입니다. BFS, Flood Fill 이외에는 딱히 코딩테스트에서 나올 부분이 보이지 않습니다.

 

STL에 queue도 있습니다 ^__^ 코드 예시와 레퍼런스 사이트를 참고해보세요.

 

큐도 스택처럼 배열로 정말 간단하게 구현할 수 있는 자료구조입니다. 정석적인 구현은 메모리누수를 막을 수 있는 원형 큐(Circular Queue)이지만 어차피 알고리즘 문제의 환경에서는 메모리누수를 걱정해야할 정도로 삽입이 일어나지 않으므로 그냥 선형 큐로 구현했습니다. 다만 나중에 면접 대비를 위해서는 원형 큐를 따로 공부하셔야 합니다. 원형 큐는 배열의 끝에 도달했을 때 다시 맨 앞으로 보내버리는 아이디어만 추가가 된 것이라 선형 큐만 제대로 이해하고 나면 그다지 어렵지 않습니다.

 

큐의 구현에서는 원소를 담을 dat 배열과 제거될 원소의 위치를 의미하는 head, 큐 내에서 삽입할 위치를 의미하는 tail 변수가 필요합니다. head, tail의 초기값은 0이며 tail-head가 큐의 길이를 의미합니다.

 

 

10, 20, 30이 큐에 들어있는 상황을 변수들로 나타내보면 아래와 같습니다. 후술할 연산들을 보면 알겠지만 시작점이 0에서 고정된 것이 아니라 점차 오른쪽으로 이동하는 모양을 가지기에 선형 큐에서는 메모리 누수가 필연적으로 발생합니다. 그리고 tail-head가 5-2 = 3으로 큐의 길이를 잘 나타냄을 알 수 있습니다.

 

 

50을 큐에 넣는 과정은 스택과 유사합니다.

 

 

우선 tail이 가리키는 곳에 새로 삽입할 원소를 쓰고

 

 

tail을 1 증가시키면 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

마찬가지로 증감 연산자를 이용해 한 줄에 처리할 수도 있습니다.

 

 

삭제는 head를 1 증가시키기만 하면 됩니다. 단 head = tail일 때, 즉 큐가 비어있을 때에는 해당 연산을 수행하지 않도록 해야합니다.

 

 

스택과 유사하게 2번지에 적힌 값은 앞으로 영영 참고될 일이 없으니 굳이 지우지 않아도 괜찮습니다.

 

 

제일 앞에 있는 원소는 dat[head]를 반환하면 됩니다.

 

 

그리고 제일 뒤의 원소는 dat[tail-1]입니다.

 

BOJ 10845번 : 큐를 풀어봅시다. STL을 활용한 정답 코드, 배열로 직접 구현한 정답 코드 모두를 확인해보세요.

 

마지막으로 다룰 자료구조는 덱입니다. 덱은 양쪽 끝에서 원소를 넣고 뺄 수 있는 자료구조입니다. 양 쪽이 전부 뚫린 셔틀콕 원통형 배드를 생각해보세요.

 

덱에서도 원소의 추가/제거, 제일 앞/뒤에 위치한 원소를 확인 모두가 $O(1)$입니다.

 

잘 생각해보면 스택/큐에서 할 수 있는 모든 일을 덱에서도 할 수 있습니다.

 

Linked List와 유사하게 덱을 사용해야하는 문제는 보통 양쪽에서 삽입/삭제가 일어나는 상황을 시뮬레이션하는 느낌의 문제입니다. 딱 보면 덱을 사용하는 문제라는 것을 알 수 있을 것입니다.

 

STL에 덱도 있습니다!! 레퍼런스 사이트도 같이 보세요. STL의 덱에서는 $i$번째 원소에 $O(1)$에 접근할 수 있습니다.

 

스택, 큐에서 했던 얘기와 동일한 내용입니다. 구현 또한 유사하기 때문에 굳이 각 과정을 스택과 큐에서 했던 것 처럼 풀어서 설명하지 않겠습니다. 예제의 정답 코드를 확인해주세요.

 

BOJ 10866번 : 덱 문제를 풀어봅시다. STL Deque를 활용한 정답 코드, 배열로 직접 구현한 정답 코드도 참고하세요.

 

그룹에 문제를 만들어두었는데, 전반적으로 발상이 조금 어렵습니다. 고민을 충분히 해보시고, 실마리가 잡히지 않으면 풀이를 찾아보세요. 그러나 꼭 구현은 직접 해보셔야 합니다.

 

이번 시간에는 스택, 큐, 덱의 정의와 구현 방법에 대해 알았습니다. 이 자료구조들의 응용을 앞으로 3-4개의 강의에 걸쳐 배우게 될 것이니 이번 강의의 내용을 확실히 이해하고 갑시다.