24 데이터를 구조해죠
적합한 데이터 구조를 선택하는 것은 문제해결의 첫걸음
# 01 가장 안쪽에 있는 물건이 필요한 날이 창고 정리를 하는 날
창고에서 가방을 꺼낼 수가 없어!!
[사례 1] 창고에서 짐 꺼내기
코로나-19 덕분에 정말 오랜만에 여행을 가보는 것 같습니다.
"여보, 여행가방 좀 창고에서 꺼내 줘"라고 아내가 말했죠. 그래서 창고를 열었는데 이게 웬 걸.. 장거리 여행을 갈 일이 없었어서 인지 여행가방이 구석에 박혀 있었습니다. 짐이 어마어마합니다. 도대체 뭘 어디서부터 시작해야 할지 모르겠더라고요. 가만히 살펴보니, 뒤에 빨간 여행 가방을 꺼낼려니까, 앞에서 부터 차례대로 꺼내야 하겠더라고요.
그래서 선풍기 꺼내고, 튜브 꺼내고, 튜브 꺼내다가 박스 떨어져서 박스도 꺼내고.
이렇게 하나하나, 꺼내다 보니까 결국 여행가방 꺼내다가 창고를 다 정리해 버렸습니다. 여행 가기 전날에 엄청나게 체력을 소진해버리게 되었습니다.
창고에 짐을 넣을 때 먼저 넣은 것은 가장 나중에 꺼낼 수밖에 없는 구조입니다. 짐을 안쪽부터 하나씩 차례대로 쌓아 나가죠. 반면에 편리한 점도 있죠. 가장 나중에 넣은 짐은 가장 먼저 뺄 수가 있어요. 예를 들어서 손님이 오셔서 지저분한 것들은 상자에 넣어 창고 문 바로 뒤에 놓으면, 손님이 가신 후에 바로 꺼낼 수가 있어 참 좋아요.
창고 = 데이터를 담는 공간
짐 = 데이터
여기서 "창고 = 데이터를 담는 공간"이라고 생각하고, "짐 = 데이터"라고 생각해보면 어떨까요?
그러면 우리가 맨 마지막에 넣은 데이터는 가장 먼저 꺼낼 수가 있고요, 가장 처음 넣은 데이터는 맨 마지막에 꺼내게 돼요. 이렇게 데이터를 담는 방식을 스택(STACK)이라고 해요.
스택(STACK)은 말 그대로 "쌓다"라는 뜻이니까, 데이터를 창고에 쌓아 둔다 정도로 이해하시면 좋을 것 같아요. 그럼 이렇게 데이터를 쌓는 방식은 어디에 흔히 쓰일까요?
혹시 여러분들 파워포인트나 엑셀 등에서 작업을 하시다가 바로 전으로 되돌아가기 버튼이 필요한 적 많으시죠? Control + Z 단축키로 말이죠. 간혹 실수를 하거나 이전 상태가 필요할 때 취소하기 기능이 있어서 얼마나 다행인지 모릅니다. 우리 인생에도 이런 되돌리기 버튼이 있으면 얼마나 좋을까요?^^
이것을 데이터 관점에서 보면 맨 마지막에 쌓은 작업 또는 기능의 데이터를 잠시 다시 치우는 것을 말합니다. 만일 이런 데이터 구조 형태로 만들지 않고 검색하는 방식으로, 일일이 내가 한 일들에 이름을 붙여서 찾아서 지우는 방식이라면 얼마나 불편할까요? 인터넷 웹페이지에서와 같이 바로 전 페이지로 돌아갈 수도 있고, 텔레비전을 보다가 이전 채널로 갈 수 있는 것이 그 스택(STACK) 데이터 구조의 예입니다.
이처럼 스택(STACK) 데이터 구조는 데이터의 입출력 속도가 빠르다는 장점이 있는 반면에, 아까 창고에서 빨간 여행가방을 꺼낼 때처럼 데이터의 삽입과 삭제가 비효율적이라는 단점이 있습니다.
우리는 스택(STACK) 데이터 구조를 마지막(LAST)에 들어간(IN) 데이터가 가장 먼저(FIRST) 나온다고(OUT) 해서 LAST IN FIRST OUT, 줄여서 LIFO라고 부릅니다.
거듭 말씀드리지만, 멋진 용어는 중요하지 않아요. 스택이라는 용어는 잠시 잊어두셔도 상관없어요. 데이터의 구조에 따라 다루는 방식이 다르다는 것을 이해하시는 것이 더 핵심입니다. 창고에 짐을 쌓는다(STACK)만 기억해주세요.
# 02. 지구의 종말이 올 때까지의 시간을 계산해보자.
[사례 2] 하노이의 탑
사실, 방금 여러분들이 익힌 스택(STACK)은 지구의 종말을 예언한 방법입니다. 무슨 이야기인지 모르시겠다고요? 제가 스토리텔링을 좀 곁들여 드리겠습니다.
스택(STACK)은 세상의 종말을 예언합니다.
인도 베레 나스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고, 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 50Cm이고, 굵기는 벌의 몸통만 합니다.
바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 "브라흐마의 탑"입니다.
브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.
-위키백과-
위에서 소개드린 이야기는 "하노이 탑"에 얽힌 전설입니다. 3개의 다이아몬드 바늘에 64개의 순금 원판을 전부 반대쪽으로 옮기면 세상의 종말이 온다는 이야기이죠.
혹시 이렇게 생긴 것 보신 적 있으시죠?
출처 : YES24이 하노이의 탑은 실제 어린이 두뇌계발에 좋은 보드게임의 일종으로 나왔었어요. 일종의 퍼즐이죠.
크기가 다른 저 원판들을 다른 기둥으로 전부 같은 모양으로 옮기면 되는 게임이에요
단 두 가지 규칙이 있는데요
한 번에 가장 위에 있는 원판 한 개만 옮길 수 있다.
큰 원판은 항상 작은 원판 아래 있어야 한다.
하노이의 탑 해결 순서(애니메이션)
https://commons.wikimedia.org/wiki/File:Iterative_algorithm_solving_a_6_disks_Tower_of_Hanoi.gif어떠신가요? 눈으로 잘 따라가실 수 있나요?
2의 □제곱 - 1
하노이의 탑에서 원판이 3개라면 2의 3 제곱만큼 옮긴 수에서 1을 뺀 횟수만큼으로 옮길 수 있어요.
그림에서처럼 원판이 4개라면 2의 4 제곱만큼 옮긴 수에서 1을 빼고요.
이것을 일반화해보면, 원판의 개수가 □개 일 때, (2의 □제곱) - 1번 이동하면 게임을 마칠 수 있죠.
다시 세상의 종말로 돌아가서, 원판의 수 □에 64를 넣어볼까요?
2의 64 제곱 - 1 = 18,446,744,073,709,551,615번 움직여야 합니다.
시간으로 바꿔보면 한번 옮길 때 1초만 걸린다고 가정해도, 약 5849억 4241만 7355년이 걸립니다.
스택(STACK)이라는 데이터 구조를 사용하면 이렇게 간단해 보이는 작업도 오래 걸립니다.
따라서 우리가 네이버나 구글에서 검색하는 것과 같은 기능이 필요하다면 스택보다는 다른 방식의 데이터 구조가 필요할 것입니다. 이것이 바로 우리가 데이터를 어떤 구조로 만들 것인가가 중요한 이유입니다.
데이터의 구조는 그 활용 목적과 용도에 맞게 설계되어야 하고 수집되어야 합니다.
# 03. 줄을 잘 서야 한다고 들었습니다만
QUEUE(큐)라는 단어를 아시나요?
[사례 3] 놀이동산 줄 서기
놀이동산 하면 신나는 놀이기구를 타는 것은 좋은데 한 가지 안 좋은 점이 있어요. 바로 줄서기인데요. 이 줄 서기를 우리는 영어로 Stand in line이라고 알고 있습니다. 그런데 다른 표현이 하나 더 있습니다. 바로 QUEUE입니다. Stand in line은 미국식 표현이고, QUEUE는 영국식 표현이라고 알고 계시면 되겠네요
https://www.snappyjack.co.uk/pillar-sign---please-queue그런데 이 줄 서기는 참 공평한 방식인 것 같습니다. 먼저 온 사람에게 먼저 차례를 주기 때문이죠. 가장 먼저 놀이동산에 줄을 선 사람에게 가장 먼저 놀이기구를 타도록 줄에서 나가게 해 줍니다.
줄 = 데이터를 담는 공간
사람 = 데이터
이번에는 "줄 = 데이터를 담는 공간", "사람 = 데이터"라고 해볼까요?
이처럼 큐(QUEUE) 데이터 구조는 데이터가 입력된 순서대로 처리한다는 장점이 있는 반면에, 놀이동산 줄 서기에서 처럼 앞사람이 빠지면서 조금씩 계속 이동해야 한다는 점과 스택(STACK)과 마찬가지로 중간에 있는 데이터에 대한 접근이 어렵다는 단점이 있습니다.
우리는 큐(QUEUE) 데이터 구조를 가장 먼저(FIRST)에 들어간(IN) 데이터가 가장 먼저(FIRST) 나온다고(OUT) 해서 FIRST IN FIRST OUT, 줄여서 FIFO라고 부릅니다. 쉽게 말해 "선착순"입니다.
# 04. 편의점에 음료수가 진열되는 방식
[사례 4] 편의점 냉장고
어떻게 유통기한이 앞선 제품이
항상 맨 앞에 있을까?
https://www.hankookilbo.com/News/Read/201701052075759132편의점에서 냉장고에 음료수를 안쪽 창고에서 넣으면 소비자가 보이는 냉장고 쇼케이스에서는 편의점 아르바이트 생이 가장 먼저 넣은 음료수를 가장 먼저 집게 됩니다. 사실 편의점의 냉장고 뒤편에는 창고이고 직원이 넣은 음료는 경사진 진열대를 타고 앞으로 이동하게 됩니다.
진열대 = 데이터를 담는 공간,
음료 = 데이터
이렇게 먼저 넣은 음료가 먼저 소비자의 눈에 띄게 되는 것이죠. 마찬가지로, 진열대 = 데이터를 담는 공간, 음료 = 데이터라고 해보겠습니다. 역시 큐(QUEUE) 데이터 구조에서 가장 먼저(FIRST)에 들어간(IN) 데이터가 가장 먼저(FIRST) 나옵니다.(OUT)
# 05. 이름은 무엇이고, 전화번호는 무엇입니다.
이름 : 홍길동
나이 : 30
전화번호 : 010-1234-5678
몸무게 : 70
위에 있는 정보에서 이름, 나이, 전화번호는 어떤 값을 나타내는지를 구분 지어 줍니다. 그래서 이름을 다양한 값의 분류가 있을 때 '홍길동'은 이름에서 검색해줄 수가 있고, '30'은 나이에서 검색해줄 수 있습니다.
이처럼 어떤 데이터가 가지는 값을 구분해주는 "이름", "나이", "전화번호" 등의 데이터를 "키(KEY)"라고 하고, 실제 우리가 원하는 값인 "홍길동", "30" 등의 데이터를 "값(VALUE)라고 합니다.
그리고 이름과 홍길동, 나이와 30을 연결하는 것을 맵핑(MAPPING)이라고 합니다.
이렇게 키와 값의 쌍으로 이루어진 데이터 구조를 맵(MAP)이라고 부릅니다.
이처럼 맵(MAP) 데이터 구조는 데이터의 검색 속도가 빠르다고 키를 통해 값에 접근할 수 있다는 장점이 있는 반면에, 데이터의 순서가 없다는 단점이 있습니다.
# 06. 데이터의 구조를 왜 알아야 하나요?
결론을 맺기 위해 다시 맨 처음 창고로 돌아가 볼게요.
창고에서 여행가방을 꺼내기 위해 고생을 하고 저는 이렇게 다짐했습니다. '아, 이제부터는 다음에 활용하기 편하도록 차곡차곡 짐 정리를 잘하겠어!'라고 말이죠.
창고에 있는 물건을 필요할 때 쉽게 꺼내서 사용하려면 정리를 잘해야 합니다. 하지만 그보다 더 좋은 방법은 애초부터 목적에 맞는 공간에 보관하는 것입니다. 예를 들어, "자주 쓰는 물건은 쉽게 넣다 뺐다 할 수 있는 공간"에 넣는 것이고, 아이들 동화책처럼 순서가 있는 경우는 번호와 칸에 맞춰서 정리할 수 있는 공간"에 넣는 것입니다.
마찬가지로 데이터를 활용하려면 문제 해결에 적합하도록 데이터를 구조화해야 합니다. 데이터의 구조화란 데이터를 원하는 데로 묶음으로 묶고, 활용하는 방법을 약속한 것을 말합니다. 데이터는 일정한 규칙 없이 저장하거나, 하나의 구조로만 활용하는 것보다 각 데이터와 문제의 특징에 맞게 저장하고 변형해야 합니다.
아까 보았던 것처럼 인터넷에서 이전 페이지로 이동하려면 데이터를 스택(STACK) 구조로 쌓아야 했고, 고객정보 DB를 구축하고 마케팅을 할 때는 키와 값을 가지는 맵(MAP) 형태로 문제를 풀어야 합니다.
문제에 맞는 데이터 구조를 선택하기 위해
이렇게 "문제에 적합한 데이터 구조를 선택하는 것"이 문제 해결을 위한 첫 번째 단계이자 가장 중요한 단계입니다. 데이터에 쉽고 빠르게 접근할 수 있다. 또는 검색할 수 있다에서 "빠르게"에 해당하는 멋진 용어가 바로 "시간 복잡도"라는 개념입니다.
이처럼 많은 데이터 구조들을 알아두면 우리가 일상에서 그리고 기업에서 발생하는 문제를 빠르게 해결하는데 가장 적합한 데이터 구조를 찾을 수 있습니다. 이것은 우리가 컴퓨터에게 일을 시키는 절차인 알고리즘과 매우 밀접한 관계가 있습니다. 데이터는 그 자체로 보면 지루하거나 왜 해야 하는지 복잡해 보이는 경우가 대부분입니다. 하지만 문제 해결을 염두에 둔 데이터는 결코 지루할 수 없습니다.
감사합니다.
