(Data Structure) #0. Data Structure이란 무엇일까?

0.들어가기에 앞서서..

대학교를 다니면서 자료구조론 시간때 여러가지 자료구조 형태와 시간복잡도 및 간단한 정렬 알고리즘들을 배웠다. 하지만 시간이 지날수록 배웠던 내용들이 희미해져갔고, 궁극적으로 내가 왜 이러한 것들을 알고 있어야하는지, 어떤식으로 코드를 구현해야 쉽게 구현을 할 수 있는지 스스로에게 혼란이 오게 되었다.

이러한 고민을 안고 있던 와중, 학과 선배가 추천해준 Udemy의 Master the Coding Interview: Data Structures + Algorithms 강의를 들어보았는데, 쉬운 설명과 함께 Javascript코드로 예시를 보여주었다. 이번 글부터 이 강의를 통해 알게 되었던, 복습을 하게 되었던 내용들을 정리해보고자 한다.

---

1. 자료구조(Data Structure), 알고리즘(Algorithm), 프로그램(Program)

1) 각각의 정의

자료 구조(Data Structure)

Collection of values.

값(또는 데이터)의 모음집이다.

알고리즘(Algorithm)

The steps or processes we put into place to manipulate these collection of values.

값(또는 데이터)의 모음들을 조작하기(만지기) 위한 일련의 순서 또는 프로세스를 의미한다.

위와 같이 자료구조는 데이터의 모음집, 알고리즘은 값들을 조작하는 순서 및 프로세스를 의미한다.

그렇다면 우리가 흔히 부르는 프로그램은 무엇일까?

프로그램(Computer Program)

Collection of instructions to perform a specific task.

특정 업무를(일을) 처리하기 위한(수행하기 위한) 명령들의 집합이다.

특정 업무를(일을) 처리하기 위해서 컴퓨터 프로그램에서는 사용하는 데이터들을 저장하거나(store), 원하는 데이터를 검색하거나(retrieve), 또는 데이터에 대한 계산들을 수행하여야 한다(perform computations).

2) 자료구조, 알고리즘, 그리고 프로그램의 상관관계

위와 같은 작업을 하기 위해선 데이터들을 메모리상에 정갈하게 담아야하고,내가 원하는 기능들을 수행하기 위해선 효율적인 데이터 조작이 필요할 것이다.
이를 다르게 생각해보면, 결국 프로그램이라는 것은 자료구조(Data Structure)와 알고리즘(Algorithm)이 동시에 합해져 있는 형태라고 볼 수 있을 것이다.

시중에는 요러한 자료구조와 알고리즘책이 있다

3) 자료구조와 알고리즘이 왜 중요할까?

우리가 어떤 이슈들을 마주쳤을때, 그 이슈와 관련된 본질적이고 기본적인 개념들(fundamentals)을 알고 있다면, 올바른 해결방안으로 이끌 수 있다.

가령, 빵을 먹고 싶어서 집에서 스스로 만들었더니 빵이 다 타버린 상태이라면, 빵을 만들때 사용했던 오븐을 확인해본다든지, 빵을 만들때 사용했던 재료들을 확인 해보는 형태로 정상적인 빵을 만들 수 있을 것이다.

아직도 비주얼베이직이 상위에 있는건 놀라운 일이다.

개발 세계에서도 마찬가지이다. 리엑트(React)나 앵귤러(Angular)을 사용하는 프론트엔드 개발자나 유니티(Unity)나 C#을 사용하는 게임 개발자등 어떠한 프로그래밍 언어를 사용하더라도 자료구조와 알고리즘은 필수 불가결이다.

응용 프로그램(Application)을 포함한 모든 프로그램들은 앞서 서술했듯이 자료구조와 알고리즘으로 구현되어 있기도 하고, 자료구조와 알고리즘의 경우 오래전부터 널리 사용되고 있고 쉽게 내용이 변경되지 않는 영속성(Timelessness)의 특징을 가지고 있기 때문에, 이 둘을 잘 알고 있다는 것은 프로그램을 1)효율적인 코드로 작성할 수 있을 뿐만아니라, 2)기술적인 이슈들에 대해 쉽게 적응하며, 3)다른 사람들이 짜놓은 프로그램에 태클도 걸어버릴 수 있다 ㅋㅋㅋㅋㅋ(tackle all sorts of technical problems).

위의 내용을 읽게 된다면, 왜 구글이나 페이스북, 아마존, 애플같은 곳에서 자료구조와 알고리즘에 관하여 구체적인 질문들을 던지는지 알 수 있을 것이다.물론, 현존하는 프로그래밍 언어의 최신 문법들을 익히는 것도 중요하지만, 언어를 활용하여 효율적인 코드를 짜기 위해선 자료구조와 알고리즘은 매우 매우 중요하다.

따라서, 좋은 개발자 또는 엔지니어가 되기 위해선, 또는 개발이라는 필드에서 더 오랫동안 남기 위해선 자료구조와 알고리즘의 필수적인 규칙/요소들을 더 많이 익히고, 필요하게 된다.

---

2. 자료구조의 조금 더 TMI한 설명

1) 자료구조의 좀 더 구체적인 정의

Data Structure is a collection of values, the values can have relationships among them and they can have functions apply to them

자료구조는 값(또는 데이터)의 모음집이며, 값(또는 데이터)끼리 서로 서로 관계를 가질 수 있으며 함수도 적용할 수 있다.

'서로 관계를 가진다'

쉽게 생각하면, 같은 구조의 값들끼리만 뭉쳐있을 수 있다는 것이다.

예를 들어, 집에 냉장고와 그릇을 담을 수 있는 서랍이 있다고 생각해보자.

냉장고에는 김치, 장조림 등 온도 유지가 필요한 음식들이 들어갈 것이고, 서랍에는 사용하지 않은 그릇들과 컵들이 보관되어 있을 것이다.

냉장고, 서랍은 각각의 용도에 맞는 물건들이 보관되고 있다. 그렇다면 만약에, 서랍에 김치와 장조림 같은 온도 유지가 필요한 음식들이 들어가있다면 어떻게 될까?

당연하게도, 음식들이 부패가 되어 먹을 수 없을 것이고, 음식을 담고 있는 용기가 단단하지 않거나 부식 등에 의해서 터지게 된다면, 보관되고 있는 나머지 그릇들은 더렵혀져 사용하기에 제약이 걸릴 것이다.

자료구조에서 다루고 있는 값(또는 데이터)도 마찬가지이다. 프로그램에서 요구하는 조건에 알맞은 형태의 값을(또는 데이터를) 가지고 있어야 원하는 기능들을 구현하거나 실현할 수 있을 것이다.

결론적으로 자료구조에서 값(또는 데이터)의 형태가 똑같은 것끼리 묶어서 정리해야하는 이유는 아래와 같이 정리할 수 있다.

The purpose of data structure is to organize data so that we can go into that and retrieve that data really easily.

데이터를 정리함으로써 내가 원하는 데이터를 쉽게 얻을 수 있을 것이다.

2) 자료구조의 종류

Each data structure is good and is specialized for its own thing.

각각의 자료 구조는 우수하고, 각자의 목적에 맞게 특수화되어 있다

위키피디아를 참고해보면, 수백개 형태의 자료 구조가 존재한다. 참조 링크
물론, 전부다 외울 필요는 없고 우리가 앞으로 자주, 그리고 오랫동안 돌려쓸 자료구조 몇가지만 알고 있으면 된다.

실생활에서의 자료구조 예시

도지코인 떡상 가즈아아아

가상화폐중 대장 코인이라고 불리는 비트코인은 개발자들 사이에서 다른 의미로 유명하였다. 비트코인을 거래할 때의 내역을 "블록체인(BlockChain)"이라는 기술을 사용하였다는 것이다.

블록체인이 엄청 어렵고 이해하기 어렵고 복잡해보이는 기술이 맞지만, 결국에는 거래 내역이라는 데이터를 가지고 있는 하나의 자료구조인 것이다.

개발을 하면서 엄청 자주 쓰이는 배열(Array)또한 하나의 자료구조이다.
각각의 인덱스를 통해 값을 저장하거나, 접근하여 데이터를 뽑아올 수 있는 것이다.
또한, 보통 배열의 데이터 타입은 배열 선언시에 정해지게 된다.
(물론 파이썬의 리스트는 타입이 여러개가 있을 수 있다)

3) 자료구조의 종류

위의 글에서 보듯이 자료구조의 종류는 너무나 많지만, 과연 각각의 자료구조가 좋은 자료구조인지 아닌지 확인하기가 힘들다. 이를 확인할 수 있는 척도가 크게 2가지가 있다.

1. Memory(Space Complexity : 공간복잡도)
2. Speed(Time Complexity : 시간복잡도)

##### 시간복잡도(Speed)와 공간복잡도(Memory)의 비교표

위의 비교표는 프로그램을 실행하는데, 또는 자료구조에서 데이터를 찾거나(Search), 집어넣거나(Insert), 삭제할 때(Delete) 필요한 시간이나 메모리 공간을 확인할 수 있다.

각각의 자료구조는 이 두가지가 동시에 좋은 것은 존재하지 않고, 둘 중에 하나의 특성을 지니고 있다.
(공간 효율이 좋으면 시간이 좋지 않고, 시간이 좋으면 오히려 공간이 효율적이지 않음)

---

3. 자료구조를 어떻게 공부해야하는가

우리가 자료구조에 대해 빠삭한 박사가 되기 위해선 2가지를 알아야한다.

1) how to actually build data structure

어떻게 자료구조를 만들까(코드로 구현을 해야할까)

2) how to use them

어떻게 자료구조들을 활용할 수 있을까

위의 두가지를 모두 고려하는 것이 좋으나, 우리가 중점적으로 생각해야 하는건 두번째이다. 자료구조를 코드로 구현하는 것은 필수적이고, 이를 어디에? 어느프로그램에? 적용해야하는지 고려를 해야하는 것이 매우 중요하다고 한다.

---

4. 마무리

이 이후로는 자료구조들 중에서 개발하는 데에 있어 필수적으로 알아야하는 자료구조들에 대해 공부하고 공부한 내용들을 업로드 할 예정이다.

연결리스트(Linked List), 배열(Array)와 스텍(Stack), 큐(Queue)의 구조 및 기능들을 작성해볼 것이며, 위 요소들을 활용하여 다른 자료구조들도 구현이 가능한데, 이 또한 같이 작성해볼 것이다.