Code States 28일차 - 자료구조 기초

자료구조란 무엇인가?

여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.

 

자료구조는 자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할수 있다. 자료구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 : 1인 선형구조, 1 : N 또는 N : N 구조인 비선형 구조, 마지막으로 파일 구조가 있다. 

구현에 따라 배열, 튜플, 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 환형 이중 연결 리스트, 해시 테이블이 있다.

형태에 따라 선형 구조인 스택, 큐, 덱이 있고, 비선형 구조인 그래프, 트리가 있다.

 

참조: 자료 구조 - 위키백과

---

오늘 Code States 코스엔 Stack과 Queue를 배운다.

Stack(스택)

스택은 제한적으로 접근할 수 있는 나열 구조이다. 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼재내기 목록(Pushdown list)이라고도 한다.

스택은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어있다. 자료를 넣는 것을 푸쉬(push), 빼는 것을 팝(pop)라고 한다. 나중에 넣은 값이 먼저 나오고 먼저 넣은 값이 나중에 나온다.

일상에서 예를 찾아보니까 프링글스가 생각이 났다.

프링글스(사진 출처: 농심 Brand)

프링글스 생산하는 것을 직접 못 봤지만 생각을 해보면 통에 담을 때 밑에서 쌓아질 것이다. 그리고 먹을 때는 뚜껑을 열고 위에서 하나씩 꺼내 먹을 수 있다. 이게 스택이지 않을까?

코드스테이츠에서는 차선이 하나 뿐이고 끝이 막혀있는 골목길에 차들이 들어오고 빠지는 예시와 브라우저의 앞으로 가기, 뒤로가기 기능을 예시로 두었다. 첫번째 예시는 한개의 스택을 사용한 것이고 두번째 예시는 스택을 두개 사용한 것이다.

Queue(큐)

큐는 컴퓨터의 기본적인 자료 구조의 한가지다, 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 위에 설명한 스택과 반대되는 개념이다.

큐는 put(insert)와 get(delete)을 이용하여 구현된다. put은 자료를 넣고, get은 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가르킨다. front는 데이터를 get 할 수 있는 위치, rear은 데이터를 put 할 수 있는 위치를 의미한다. 큐가 꽉 차서 자료를 넣을 없는 경우를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우를 언더플로우(Underflow)라고 한다.

이것도 예를 찾아보면 사람이 줄서서 기다리는 것만 생각난다. 공항에서의 출입국심사, 맛집에서 대기표 뽑고 기다리는 거...

코드스테이츠도 그렇고 대부분 큐의 예시를 컴퓨터에서 프린터로 인쇄하는 것을 예로 많이 봤다. 하지만 새로운 걸 찾고 싶었지만 생각이 안난다.

---

무려 8~10년전에 대학교에서 배운 내용을 지금보니까 조금씩 떠오르고 '아직 잊지않았구나' 하고 있는 내가 기특하다.

내일은 Graph와 Tree, BST(Binary Search Tree)로 오겠다.

짜잔~ 알고보니까 오후에 Graph와 Tree, BST(Binary Search Tree)가 있었다.

정리를 시작하자.

 

Graph

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

vertext(정점)와 edge(간선)로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.

자료를 더 찾아봐야할 것들이 있다.

• 무(방)향 그래프(undirected graph)
• 진입차수(in-degree) / 진출차수(out-degree)
• 인접(adjacency)
• 자기 루프(self loop)
• 사이클(cycle)

인접 행렬

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형대로 나타낸다.

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며 자신과 인접한 다른 정점을 담고 있다.

Tree

트리 구조는 나무의 형태를 가지고 있어서 트리 구조라고 부른다.

트리에서 최상위 노드를 루트 노드(root node)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf noㅇㄷ)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

 

깊이(depth)는 루트로부터 하위계층의 특정 노드까지를 말하고 루트 노드의 깊이는 0이다.

레벨(Level)은 같은 깊이를 가지고 있는 노드를 말한다. 같은 레벨에 있는 노드를 형제 노드(sibling Node)라고 한다.

높이(Height)는 리프 노드를 기준으로 루트까지를 말한다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.

서브 트리(Sub tree)는 트리의 내부에 트리 구조를 갖춘 노드를 말한다.

---

생각보다 자료가 너무 없다. 구글링을 해도 정리된 블로그만 많고 위키백과나 나무위키 같은 정리된 사이트가 없다.

나중에 찾게 되면 추가해야겠다.

내일은 페어뿐이라 다른 글을 써볼까...

---

시간이 없어 정리 못 했던 부분을 추가한다.

Tree traersal

특정 목정을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.

트리를 순회하는 방법은 세 가지가 있다.

• 전위 순회: 루트를 먼저 탐색하고 왼쪽의 노드를 순차적으로 탐색하고 끝이 나면 오른쪽 노드를 탐색한다.
• 중위 순회: 왼쪽 끝에 있는 노드를 먼저 탐색하고 부모 노드를 탐색하고 오른쪽 자식 노드를 탐색한다.
• 후위 순회: 왼쪽 끝에 있는 노드를 먼저 탐색하고 오른쪽 자식 노드를 탐색하고 부모 노드를 탐색한다.

BFS / DFS

BFS(Breadth First Search)는 너비를 우선적으로 탐색하는 방법이다. 주로 두 정점 사이의 최단경로를 찾을 때 사용한다. 만약 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴봐야 한다.

DFS(Depth First Search)는 깊이를 우선적으로 탐색하는 방법이다. 한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다. BFS보다 오래 걸릴지 모르지만 모든 노드를 완전히 탐색할 수 있다. 만약 BFS로 탐색을 했을 때, 해당 경로가 처음에 나와도 모든 경로를 탐색해야한다.