자료 구조 책 추천 - 초보자를 위한 2021년 Best 책 선정

1. 배열 (Array)

 

 

• 배열 (Array)

요즘 많은 초보 개발자들이 자료 구조 중 배열에 대해 알아야 한다. 배열은 순차적인 데이터 요소를 저장하는 데 유용하며, 메모리 상에서 연속된 공간에 할당됩니다.

배열의 주요 특징은 데이터를 인덱스를 통해 접근할 수 있다는 점입니다. 이것은 데이터 요소를 빠르게 찾을 수 있다는 장점을 가지고 있습니다. 또한, 배열은 크기를 미리 정해야 한다는 제약이 있습니다.

배열은 동일한 데이터 유형을 저장하는 데 적합하며, 순서가 중요한 경우에 사용됩니다. 하지만, 데이터를 추가하거나 삭제할 때에는 비효율적일 수 있으니 주의해야 합니다.

 

 

2. 연결 리스트 (Linked List)

 

 

• 연결 리스트 (Linked List): 데이터 요소들을 순서대로 저장하는 자료 구조
• 노드 (Node): 각각의 데이터 요소를 담고 있는 단위
• 헤드 노드 (Head Node): 연결 리스트의 시작 노드를 가리키는 포인터
• 테일 노드 (Tail Node): 연결 리스트의 끝 노드를 가리키는 포인터
• 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드를 가리키는 방식
• 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 가리키는 방식
• 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 방식

 

 

3. 스택 (Stack)

 

 

• 스택(Stack)

스택(Stack)은 후입선출(LIFO, Last In First Out) 방식의 자료 구조로, 데이터를 넣고(push) 꺼내는(pop) 동작을 할 수 있다. 주요 메소드:

• push(): 스택에 데이터를 넣는 메소드
• pop(): 스택에서 데이터를 꺼내는 메소드
• peek(): 스택의 맨 위 데이터를 조회하는 메소드
• isEmpty(): 스택이 비어있는지 확인하는 메소드

스택은 함수 호출, 역추적, 균형잡힌 괄호 등 다양한 알고리즘에서 활용되는 중요한 자료 구조이다. 기본적인 동작 원리와 각 메소드 활용법을 익히면 프로그래밍 실력 향상에 도움이 될 것이다.

 

 

4. 큐 (Queue)

 

 

• 큐 (Queue)란?
  큐 (Queue)는 선입선출(FIFO) 구조를 가지는 자료 구조로, 요소들이 순차적으로 삽입되고 삭제되는 형태를 갖고 있어.
• 큐 (Queue)의 주요 특징
  - enqueue: 요소를 큐에 삽입하는 연산
  - dequeue: 요소를 큐에서 삭제하는 연산
  - front: 큐의 맨 앞 요소에 접근하는 연산
  - rear: 큐의 맨 뒤 요소에 접근하는 연산
• 큐 (Queue)의 활용 예시
  - 너비 우선 탐색(BFS) 알고리즘 구현 시 사용되어
  - 작업 대기열, 프린터 대기열 등 다양한 상황에서 활용 가능해

 

 

5. 해시 테이블 (Hash Table)

 

 

• 해시 테이블 (Hash Table): 해시 테이블은 키(Key)와 값(Value) 쌍을 저장하는 자료 구조이다.
• 해싱 (Hashing): 해시 함수를 사용하여 키를 해시 값으로 변환한다.
• 충돌 (Collision): 서로 다른 키가 같은 해시 값으로 해시되는 경우를 의미한다.
• 개별 체이닝 (Separate Chaining): 충돌 시 각 버킷에 연결 리스트를 이용하여 데이터를 저장하는 방식이다.
• 개방 주소법 (Open Addressing): 충돌 시 다른 빈 버킷을 찾아 재해시하는 방식이다.

 

 

6. 트리 (Tree)

 

 

• 트리(Tree)는 계층적인 구조를 가지고 있는 자료 구조로, 부모와 자식 관계를 나타내는 트리 구성 요소를 노드라고 부릅니다.
• 트리(Tree)는 하나의 루트 노드를 가지며, 각 노드는 0개 이상의 자식 노드를 갖을 수 있습니다.
• 트리(Tree)의 주요 용어로는 루트, 노드, 에지, 부모 노드, 자식 노드, 리프 노드 등이 있습니다.
• 트리(Tree)는 그래프의 한 종류로, 그래프가 사이클을 가지지 않고 연결되어 있는 것이 중요한데, 트리(Tree)는 그래프의 특수한 형태입니다.
• 트리(Tree)는 이진 트리, 이진 탐색 트리, AVL 트리, 레드-블랙 트리, B-트리, B+트리 등 다양한 종류가 있습니다.

 

 

7. 그래프 (Graph)

 

 

• 그래프(Graph)
  그래프(Graph)는 많은 문제를 해결하는 데 유용한 자료 구조이다.
• 그래프(Graph)란?
  노드(Node)와 이를 연결하는 간선(Edge)으로 이루어진 자료 구조이다.
• 그래프(Graph)의 종류
  - 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프
  - 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프
• 그래프(Graph)의 표현 방법
  - 인접 행렬(Adjacency Matrix): 2차원 배열로 노드 간 연결 관계를 표현
  - 인접 리스트(Adjacency List): 리스트로 각 노드에 인접한 노드들을 표현
• 그래프(Graph)의 탐색
  - 깊이 우선 탐색(Depth First Search): 스택(Stack)을 활용한 탐색 방법
  - 너비 우선 탐색(Breadth First Search): 큐(Queue)를 활용한 탐색 방법

 

 

8. 힙 (Heap)

 

 

• 힙 (Heap): 힙은 완전 이진 트리로 구현되는 자료 구조로, 최대 힙과 최소 힙으로 나뉘어져 있습니다. 여기서 최대 힙은 각 노드의 값이 그 자식 노드의 값보다 크거나 같고, 최소 힙은 각 노드의 값이 그 자식 노드의 값보다 작거나 같습니다.
• 힙 구조: 힙은 주로 배열을 사용하여 구현되며, 노드의 삽입과 삭제 시 시간 복잡도는 O(logN)입니다. 이러한 특성으로 힙은 우선순위 큐와 정렬 알고리즘 등 다양한 분야에서 활용되고 있습니다.
• 힙의 활용: 힙은 다익스트라 알고리즘과 힙 정렬 등과 같이 다양한 알고리즘에서 사용되는데, 특히 대량의 데이터 중에서 최댓값이나 최솟값을 빠르게 찾고자 할 때 매우 유용하게 활용됩니다.

 

 

9. 정렬 알고리즘 (Sorting Algorithms)

 

 

• 선택 정렬 (Selection Sort): 가장 작은 항목을 선택하여 배열의 처음으로 이동시키는 방식
• 삽입 정렬 (Insertion Sort): 각 항목을 이미 정렬된 부분 배열에 삽입하는 방식
• 버블 정렬 (Bubble Sort): 인접한 항목을 비교하여 필요에 따라 서로 교환하는 방식
• 합병 정렬 (Merge Sort): 분할 정복 전략을 사용하여 배열을 반으로 나눈 후 합병하는 방식
• 퀵 정렬 (Quick Sort): 피벗 값을 중심으로 작거나 큰 항목들을 나누고 정렬하는 방식

 

 

10. 탐색 알고리즘 (Searching Algorithms)

 

 

• 선형 탐색 (Linear Search): 데이터 구조를 처음부터 끝까지 하나씩 비교하며 찾아가는 간단한 방식의 탐색 알고리즘
• 이진 탐색 (Binary Search): 정렬된 데이터에서 중간 값을 기준으로 찾고자 하는 값을 탐색하는 효율적인 알고리즘
• 이진 탐색 트리 (Binary Search Tree): 각 노드가 최대 두 개의 자식 노드를 가지며 왼쪽 자식은 작은 값, 오른쪽 자식은 큰 값이 위치하도록 구성된 트리
• 보간 탐색 (Interpolation Search): 정렬된 데이터에서 이진 탐색을 보완하여 찾고자 하는 값을 예측하여 찾아가는 탐색 알고리즘