데이터과학 유망주의 매일 글쓰기 — 85일차
Stack과 Queue
# Stack, #Queue
오늘 한일:
오늘은 자가 점검의 시간이었다. 전반적으로 큰 문제는 없었다. 알고리즘을 공부하면서 드는 생각은 정말 배울게 많다는 생각 뿐이었다.
오늘은 그동안 내가 미쳐 리뷰하지 못했던 가장 기본적인 자료 구조들인 Stack과 Queue에 대해 리뷰하고자 한다. 연결리스트(Linked List)를 기반으로 할 수도 있고, 연결리스트와 함께 가장 많이 쓰이는 데이터 구조지만, 이번 주 이 둘의 개념이 헷갈려서 낭패를 볼 뻔했다. 그래서, 확실하게 Stack과 Queue의 차이점을 리뷰하려고 한다.
Stack(2)
Stack은 먼저 들어간 입력값이 먼저 나오는 선입선출(First In First Out) 형태이거나, 나중에 들어간 것이 먼저 나오는 후입선출(Last In First Out)의 구조를 가지고 있으나, 일반적으로 후입선출형태로 많이 사용하는 편이다. Stack은 연결리스트(Linked List)나 다른 형태로 이루어질 수 있도 있다. 예를 들어 인터넷 브라우져를 떠올려보자. 브라우져에서도 방문한 페이지의 기록이 담겨져있는 History를 볼 수 있는 기능이 있을 것이다. 싸이트 A -> B -> C -> D의 순서로 방문을 할 것인데, 한 싸이트에서 다른 싸이트로 가면서 Tail 쪽에 웹사이트를 삽입하는 PUSH를 하게된다. 이러한 구조는 최근 방문한 싸이트일수록 Stack의 위에 위치하게끔 만든다. 만약 Stack에서 데이터를 제거하는 POP 명령을 실행하면, 가장 최근에 들어간 데이터가 나오게끔 설계되어있다. 예를 들어 아래 예제를 보자.
# 싸이트 방문시 Stack 기록
# 방문 싸이트를 기록하기 위한 텅빈 리스트 생성
site_visited = []
# 싸이트 방문할 때마다 기록하기 위한 함수
def visit_site(site):
site_visited.append(site)
return site_visited# "A" 싸이트 방문visit_site("A")>> ['A']# "B" 싸이트 방문visit_site("B")>> ['A', 'B']# "C" 싸이트 방문visit_site("C")>> ['A', 'B', 'C']# "D" 싸이트 방문visit_site("D")>> ['A', 'B', 'C', 'D']# 최종 방문 싸이트 기록site_visited>> ['A', 'B', 'C', 'D']
위 코드는 Stack을 예제로 보여준다. 유저가 방문할 때마다 싸이트가 기록되는데, 먼저 방문한 싸이트의 순서로 쌓이는 것을 볼 수 있다. 가장 오래전 방문한 싸이트 “A”가 리스트의 가장 먼저 위치하고, 가장 최근에 방문한 싸이트 “D”가 리스트의 가장 뒤에 위치하는 것이다.
방문한 싸이트의 기록을 POP할 경우, 가장 최근에 방문한 싸이트 “D”가 먼저 나오는 것을 알 수 있다. 그렇게 되면 자연스럽게 Stack에 가장 위에 위치하게되는 싸이트는 “C”가 된다.
# 싸이트를 pop하면 어떤 결과가 나오나?site_visited.pop()>>> Dsite_visited>>> ['A', 'B', 'C']
Queue(3)
Queue의 경우 반대로 선입선출(First In First Out)의 형태로 많이 사용된다. 예를 들어 매우 유명한 핫도그 가게에서 핫도그를 먹기위해 줄을 선다고 하자, 그렇게되면 먼저온 순서대로 주문을 받게 될 것이다. 바로 이렇게 먼저 요청이 들어온 업무를 먼저 처리하는 방식을 말한다고 할 수 있다. 이러한 특성 때문에 Queue는 순서를 가진 시퀀스 데이터에 널리 쓰일 수 있다.
예를 들어 아래 처럼 한 핫도그 가게에서 4개의 주문이 들어왔다고 가정하자. 주문된 핫도그는 “New York”, “Bavarian”, “Barbeque”, “Chili”의 순이다. 여기서 새로운 주문 2개인 “Barbeque”, “Chili”가 또 들어왔다고 가정한다. Stack과 반대로 선입선출의 개념을 보여주기 위해 양방향의 POP 동작이 가능한 collections 모듈의 deque를 사용하였다. 이미 처리된 오더는 POP(popleft())를 통해 제거된다.
# 핫도그 가게 Queuefrom collections import deque# 이미 들어온 오더 "New York", "Bavarian", "Barbeque", "Chili"queue = deque(["New York", "Barvarian", "Barbeque", "Chili"])# 먼저 들어온 2개의 오더 처리print('처리된 주문 1: ',queue.popleft())print('처리된 주문 2: ',queue.popleft())# 새로 들어온 오더 "Barbeque", "Chili"queue.append("Barbeque")queue.append("Chili")# 남은 주문 현황 확인print('남은 주문: ', queue)>>> 처리된 주문 1: New York
처리된 주문 2: Barvarian
남은 주문: deque(['Barbeque', 'Chili', 'Barbeque', 'Chili'])
이미 들어온 오더 중 먼저 들어온 “New York” 및 “Bavarian” 핫도그의 주문이 처리되었다. 이후, 새로운 주문은 나중에 들어왔으므로 나중에 들어간다. 남은 주문 현황을 확인해보면, 기존에 들어왔으나 아직 처리되지 않은 “Barbeque”와 “Chili”가 남았고, 새로 들어온 동명의 2개 주문이 순서대로 또 존재하는 것을 알 수 있다. 이처럼 새로운 주문을 할때 리스트에 PUSH(append)를 하게되면, 먼저 온 순서대로 오더 순서에 추가된다. 이 상태에서 주문을 하나 더 처리하게 되면, “Barbeque”가 먼저 처리될 것이다.
# 다음 주문 처리print('처리된 주문 3: ',queue.popleft())# 남은 주문 현황 확인print('남은 주문: ', queue)>>> 처리된 주문 3: Barbeque
남은 주문: deque(['Chili', 'Barbeque', 'Chili'])
앞으로 할일:
오늘은 가장 기본적인 데이터 구조인 Stack과 Queue를 리뷰했다. 그동안 이 자료구조들에 기반해 많은 알고리즘을 배워왔으면서도, 정작 이 개념을 정리하지 못한 것이 조금 아쉬웠다. 이번 주 배웠던 DFS도 Stack을 바탕으로 구현된 개념이었다. 그만큼, 중요한 알고리즘이 이러한 데이터 구조들에 기반해있으니, 앞으로도 제대로 기억하는 것이 좋겠다.
오늘은 정말 마지막 시험이었다. 이번 주는 정식 강의가 있는 마지막 스케쥴이었다. 막상 이렇게 끝나니 시원 섭섭하다. 무언가 열심히 해서 여기까지 오긴했는데, 정말 내가 제대로 배웠는지, 아직도 갈길이 먼 것 같은 느낌이 더 크다. 물론, 1달도 안되서 컴퓨터 과학의 모든 기초를 깨우치고, 나아가서 더 심화된 알고리즘까지 습득하는 것에는 한계가있다.
하지만, 한편으로는 정말 많이 성장했다. 이전까지는 그냥 검색하고 코드를 가져다썼다면, 이제는 그 코드가 어떠한 로직이나 원리로 돌아가는지에 대해 조금 더 깊게 생각해 볼 수 있었다. 코드 하나를 짤 때도, 이 것이 과연 가장 효율적인 방법인지 생각해보게 되었다. 그래서, 그 어느때보다 어려웠던 것 같다. 하지만, 동시에 그 어느때보다도 즐거웠다.
전체적으로 통계와 수학 이론을 복습하면서 대학생활로 다시 돌아간 느낌이 들기도 했고, 머신러닝을 배우면서 코드를 가져다 쓰는 법을 배웠다. 데이터 엔지니어링을 통해서는 어떻게 웹 프로그래밍을 하는지 배웠고, 엄청난 인내와 끈기로 문제를 하나 하나 고쳐나가는 법을 배웠다. 딥러닝에서는 단순히 코드 뿐만아니라 개념에 대해 조금 더 깊게 들어가고, 수식화하여 중요한 개념들을 설명하는 연습을 했다. 마지막으로 이번 섹션에서는, 이전에 배웠던 모든 것들에 대해 숲을 볼 수 있는, 코드의 목적과 방법론에 대해 깊게 탐구했다. 이제는 코드를 가져다 쓰더라도, 이 코드가 어떠한 로직으로 이루어졌을지, 어떠한 개념을 활용했는지 감을 잡을 수 있을 정도는 되었다고 생각한다. 물론, 거기서도 더 나아가서 정확히 각각의 툴의 코어를 아는 것은 아직 갈길이 멀지만.
나 뿐만 아니라, 동료 수강생들 모두가 지난 6개월간의 여정동안 정말 많이 성장했다. 다들 정말 큰 박수를 쳐주고 싶다. 모든 사람들이 자랑스럽다. 이렇게 빠른 페이스의 스케쥴을 소화하려면 정말 적지 않은 인내심과 끈기, 노력이 필요하기 때문이다. 이런 과정을 거쳐왔으니, 그 어떤 문제가 닥치더라도 당황하지 않고 최대한 할 수 있는 만큼 도전해 볼 수 있는 태도가 어느 정도 길러졌다고 생각한다. 이번 과정을 통해 배운 가장 큰 것들은, 그 어떤 것들 보다도 이러한 진취성과 적극성, 그리고 강한 의지인 것 같다.
다음 주 프로젝트도 잘 끝내서, 정말 후회없이 이 모든 과정을 마무리 지었으면 좋겠다. 다들 정말 수고하셨다. 나도, 동료 수강생들도, 과정을 준비하고 끝까지 우리를 도와주려 노력하신 모든 선생님들도, 그 누구하나 이 과정에서 덜 칭송받아야 하는 사람은 없을 것이다. 첫 날만 해도, 당장 한 달후가 까마득했지만, 벌써 여기까지 왔다. 막상 당시에는 너무 힘들고 시간이 느리게 가는 것 같아도, 돌아보면 정말 시간은 빠르게 흘렀다는 것을 느낀다. 앞으로 우리에게 주어질 프로젝트가 어떤 것들이 있는지 모르겠지만, 매 순간 최선을 다해 앞으로도 잘 이겨낼 것이라 믿어 의심치 않는다.
모두에게 즐거운 주말이 되기를!
참조:
(1) Data Structure: Stack and Queue
(2) Stacks, queues and linked lists
(3) Queue of people buying fast food from a butger and hot dog stand at a country fair
