또다시 코딩

큐는 FIFO(First In First Out)특징을 가지는 자료구조입니다.

다음 사진과 같이 터널을 자동차가 지나간다고 이야기했을 때 가장 처음 들어간 자동차는 그대로 터널을 통과해서 나올겁니다.

즉 데이터를 삽입하고 출구앞에서부터 데이터가 쌓이기시작하기 때문에 데이터를 꺼낼 때 마다 데이터를 넣었던 순서대로 데이터를 삭제하거나 활용할 수 있습니다.

이러한 큐는 너비 우선 탐색(Breadth First Search)알고리즘에서 활용될 수 있습니다. 이러한 큐의 응용법은 BFS알고리즘 게시글에서 다시한번 확인하실 수 있습니다.

C++공식 홈페이지를 확인해보겠습니다.

https://www.cplusplus.com/reference/queue/queue/?kw=queue 

큐는 다음과같이 6개의 operations를 가지고있으며 스택과 동일하게 template구조로써 선언시 이용할 데이터의 자료형을 명시해주고 사용해야합니다.

앞서 스택게시글의 존재하는 함수와 동일하기 때문에 size, empty push_back 함수는 생략하겠습니다.

특별하게 다른점은 back, front라 명시되어있는데 이 부분은 현재로써는 입구와 출구가 서로 반대방향에 존재한다는 것으로 이해하시면 될것 같습니다. 이어서 push_back은 데이터를 삽입, pop_front는 데이터 제거, front는 가장 앞에 존재하는 데이터의 원소를 불러오는 함수가 되겠습니다.

큐 자료구조는 이후 덱(Double Ended Queue)자료구조에서 더 응용되어 사용될 수 있습니다.

이것으로 큐 자료구조에 대한 설명을 마치겠습니다.

Stack이란?

스택은 LIFO(Last In First Out) 구조를 가지고 있는 자료구조입니다.

자료구조를 처음 공부하는 입장에서는 이러한 구조가 이해하기 어려울 수 있기 때문에 그림을 보며 설명을 이어가겠습니다.

일상생활에서 이러한 LIFO구조인 물건을 생각해 보겠습니다.

다음사진과 같이 옷을 갠다고 생각해보겠습니다.

옷장서랍에 이 옷들을 전부 넣을 때 처음 넣은 옷은 가장 밑으로가게되며 마지막으로 넣은 옷을 가장 위에 있을겁니다.

이러한 방식으로 사용하는 데이터에 따라 스택이란 저장공간(자료구조)를 이용함으로 써 문제를 해결하거나 효율적으로 데이터를 활용할 수 있습니다.

알고리즘과 관련해서 스택을 사용하는 알고리즘은 깊이 우선 탐색(Depth First Search)가 존재하며 알고리즘탭에서 다시한번 스택을 이용하는 방법을 확인하실 수 있습니다.

이제 스택이란 저장공간이 이러한 특징을 가지고있다는 것을 알았으니 내부 구현은 어떤방식으로 되어있는지 라이브러리를 살펴보겠습니다.

C++공식 사이트를 참고하였습니다.

https://www.cplusplus.com/reference/stack/stack/?kw=stack 

template으로 선언되어 있으며 자신이 저장하고자하는 데이터타입에 맞게 선언해준 후 사용하는 방식으로 이용할 수 있으며 앞서 말했던 내용과 동일하게 LIFO에 대한 이야기와 5가지의 operations 를 확인할 수 있습니다.

생성자와 C++11버전의 함수를 제외하고 말해드리면

empty - 현재 스택이 비어있는지 확인하기

size - 현재 스택의 사이즈 확인하기

top - 스택의 가장 위에 있는 데이터를 확인하기.

push - 스택의 데이터를 추가하기.

pop - 스택의 데이터(top에 존재하는) 제거하기.

로 구성되어있으며 언어에따라 함수의 반환값이나 함수구성의 차이가 존재할 수 있기 때문에 사용하는 언어에 맞춰 다시한번 검색해보시는 걸 추천드립니다.

이것으로 간단하게 스택 자료구조에 대한 설명을 마치겠습니다.

https://www.acmicpc.net/problem/10546

이 문제는 무조건 n명의 사람이 완주하였고 1명의 사람이 완주하지못하였다고 했다. 그러나 참가자의 수를 고려하고 문자열이라는 것을 생각하여 멀티 셋 자료구조를 사용하여 해결하였다. 그냥셋을 사용하여도 되었으나 동명이인이 존재한다는 것을 생각하여 멀티셋을 사용하여야 했다.

소스 코드 : https://github.com/ukjinlee66/BOJ/blob/master/10546.cpp

https://www.acmicpc.net/problem/7785

이 문제는 자료구조를 이용하여 해결하는 문제였다. 처음 문제를 접하였을 때 자료구조중 set 를 이용하여 enter 가 들어오면 set에 넣어주었고 leave 가 들어 올 경우 set에서  이름을 확인 한 후에 빼주었다.

소스코드 : https://github.com/ukjinlee66/BOJ/blob/master/7785.cpp