비록 시작은 코딩일기지만, 그 끝은 창대하게
어엿한 개발자 블로그로 성장할 수 있도록.

---

Interview :: 자료구조

기본적인 자료구조에 대해서 내용을 간단히 정리해보자

---

Arrays & Linked List

Arrays

가장 기본이라 할 수 있는 자료구조 배열 이다.
배열은 논리적인 저장 순서와 물리적인 저장 순서가 동일하다. 때문에 우리는 Index 라는 개념으로 원하는 원소에 바로 접근할 수 있다(조회). 이때 시간 복잡도는 O(1) 이다.

하지만, 조회가 아닌 삽입 or 삭제 의 경우 얘기가 달라진다. 삽입 or 삭제하려는 원소에 먼저 접근(조회) 하고 (O(1)) 삽입 or 삭제의 행위를 한 다음 추가적인 행동을 더 해줘야한다.

삭제의 경우 특정 원소를 삭제하게 되면 빈 공간이 생겨 배열의 연속성이 깨지게 된다. 따라서 원소들을 Shift 해줘야하는 cost가 발생한다. 이때 시간 복잡도는 O(N) 이다. 따라서 삭제의 상황에서 최악의 경우 시간 복잡도는 O(N) 이 된다.

삽입의 경우도 마찬가지로 삽입 이후 원소들을 원소들을 Shift 해줘야하는 cost가 발생하게 되고 이때 또한 시간 복잡도는 O(N) 이다.

---

Linked List

이런 Arrays의 문제를 해결하기 위한 자료구조가 Linked List 이다.

Linked List 는 기본적인 자료구조 중의 하나로 각각의 Element 들이 자기 자신 다음이 어떤 Element 인지만을 알고있다. 이러한 특성으로 앞서 삽입 or 삭제 에 있어서 원소들을 Shfit 할 필요가 없어지기 때문에 O(1) 의 시간 복잡도로 수행할 수 있다.

하지만, Linked List 역시 한 가지 문제가 있는데, 삽입 or 삭제 를 하기 위한 탐색에 있어서 index 로 바로 접근할 수 있는 Arrays와 달리 처음 원소부터 다 확인해봐야 하기 때문에 최악의 경우 O(N) 의 시간 복잡도를 갖게 된다.

결과적으로 Linked List 도 Arrays 와 마찬가지로 최악의 경우 시간 복잡도가 O(N) 이 된다. 하지만, Tree 구조에서 유용하여 근간이 되는 자료구조이다.

---

Stack & Queue

Stack

선형 자료구조의 하나로 먼저 들어간 원소가 나중에 나오는 First In Last Out, FILO (나중에 들어간 원소가 먼저 나오는 Last In First Out, LIFO) 의 특징을 갖는다. 박스를 쌓는 것을 생각하면 쉽게 이해 될것이다.

Queue

선형 자료구조의 하나로 먼저 들어간 원소가 먼저 나오는 First In First Out, FIFO (나중에 들어간 원소가 나중에 나오는 Last In Last Out, LILO) 의 특징을 갖는다. 터널, 통로를 생각하면 쉽게 이해 될것이다.

---

Tree

Tree 는 Stack 이나 Queue 와 달리 비선형 자료구조 이다. Tree 는 계층적 관계(Hierarchical Relationship) 를 나타내는 자료구조이다. 무언가를 저장하고 꺼내는 것 보다는 표현 하는 데에 집중한다.

Tree 구조에 쓰이는 기본적인 용어들

• Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
• Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
• Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

Binary Tree

Root Node 를 중심으로 두 개의 Sub Tree 로 나뉘어진다. 또한 나뉘어진 Sub Tree 또한 Binary Tree 이다.

Tree 에서는 각 층별로 숫자를 매겨서 이를 tree의 Level 이라고 한다. Level 의 값은 0 부터 시작하고 따라서 루트 노드의 Level은 0 이다. 그리고 트리의 최고 Level을 가리켜 해당 트리의 height 라고 한다.

Binary Tree 에는 다음과 같은 종류가 있다.

• Perfect Binary Tree (포화 이진 트리)
  모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다.

• Complete Binary Tree (완전 이진 트리)
  위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다.

• Full Binary Tree (정 이진 트리)
  모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.

---

Graph

정점과 간선으로 이루어져 있으며, Tree 또한 Graph 이다.
연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph 라고 하고, 방향성이 있는 그래프를 Directed Graph 라고 한다.

Undirected Graph 에서 각 정점에 연결된 Edge 의 개수를 Degree 라 한다. Directed Graph 에서는 간선에 방향성이 존재하기 때문에 Degree 가 두 개로 나뉘게 된다. 각 정점으로부터 나가는 간선의 개수를 Outdegree 라 하고, 들어오는 간선의 개수를 Indegree 라 한다.

이 간선에 가중치를 부여하면 가중치 그래프(Weight Graph) 가 되는 것이다.

Graph를 구현하는 방법에는 두 가지가 있다.

• 인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법
  해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다. Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다. Dense graph 를 표현할 때 적절할 방법이다.

• 인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법
  vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다. Space Complexity 는 O(E + V)이다. Sparse graph 를 표현하는데 적당한 방법이다.

Graph 는 다른 자료구조와 달리 알고리즘을 기반으로 모든 정점을 탐색한다. 그 알고리즘은 다음의 두 가지가 있다.

• 깊이 우선 탐색 (Depth First Search: DFS)
  그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 계속 나아가는 방법으로 탐색한다. 일단 연결된 정점으로 탐색하는 것이다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다. 갔던 길을 되돌아 오는 상황이 존재하는 미로찾기처럼 구성하면 되는 것이다. 어떤 자료구조를 사용해야할까? 바로 Stack 이다. (물론 구현할때는 재귀함수로 구현하는 방식이 있는데 이 편이 코드가 더 간결하다.)
  Time Complexity : O(V+E) … vertex 개수 + edge 개수

• 너비 우선 탐색 (Breadth First Search: BFS)
  그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아가는 방법으로 탐색한다. Tree 에서의 Level Order Traversal 형식으로 진행되는 것이다. BFS 에서는 자료구조로 Queue 를 사용한다. 연락을 취할 정점의 순서를 기록하기 위한 것이다. 우선, 탐색을 시작하는 정점을 Queue 에 넣는다.(enqueue) 그리고 dequeue 를 하면서 dequeue 하는 정점과 간선으로 연결되어 있는 정점들을 enqueue 한다. 즉, vertex 들을 방문한 순서대로 queue 에 저장하는 방법을 사용하는 것이다.
  Time Complexity : O(V+E) … vertex 개수 + edge 개수
  (참고로 BFS 로 구한 경로는 최단 경로이다.)

---

Reference

• Interview Question GitHub