스택, 큐, 트리, 그래프까지: 자료구조 정리

자료구조의 개념과 정의, 그리고 중요성

자료구조(Data Structure)란, 데이터를 효율적으로 저장하고, 조직하고, 관리하며, 접근하기 위한 구조적인 방법론을 의미합니다. 프로그램에서 데이터를 효과적으로 처리하기 위해서는 그에 맞는 자료구조를 선택하고 사용하는 것이 필수적이며, 알고리즘의 성능과 직결되는 요소입니다.

자료구조의 정의

• 자료구조는 데이터 간의 논리적 관계를 표현하고, 이를 통해 효율적인 탐색, 삽입, 삭제, 수정 등의 연산을 가능하게 합니다.
• 자료구조는 데이터의 형식(데이터 타입), 연산(삽입, 삭제, 검색 등), 그리고 **구조(선형, 비선형 등)**에 따라 분류됩니다.

자료구조가 중요한 이유

• 알고리즘과 함께 소프트웨어의 성능을 결정하는 핵심 요소입니다.
• 메모리 사용의 효율성, 연산 속도, 코드의 복잡성 등에 직접적인 영향을 미칩니다.
• 시스템 소프트웨어, 운영체제, 컴파일러, 데이터베이스 등 핵심 기술의 기반이 되는 이론입니다.
• 면접에서는 자료구조의 이론적 이해뿐 아니라, 구조 간 비교 분석 능력, 선택 이유 설명까지 요구되므로 깊이 있는 학습이 필요합니다.

---

선형 자료구조의 구조와 특징

선형 자료구조는 데이터가 직선 형태로 구성되며, 순차적으로 연결되는 구조입니다. 이는 메모리 상에서 논리적 순서를 가지며, 가장 기본적인 형태의 자료구조입니다.

배열(Array)의 개념과 특성

• 정의: 고정된 크기의 동일한 데이터 타입을 연속적으로 저장하는 자료구조입니다.
• 특성:
  • 인덱스를 통해 임의 접근(Random Access)이 가능하여 탐색이 빠름 (시간복잡도: O(1))
  • 삽입 및 삭제 시 자료의 이동이 필요하여 비효율적 (O(n))
  • 고정된 크기로 선언되기 때문에 메모리 낭비 또는 부족 가능성 존재

---

연결 리스트(Linked List)의 개념과 구성 원리

• 정의: 각 노드가 데이터와 다음 노드의 주소를 포함하며 연결되어 있는 구조입니다.
• 구성:
  • 단일 연결 리스트(Singly Linked List): 다음 노드로만 연결
  • 이중 연결 리스트(Doubly Linked List): 이전 노드와 다음 노드 모두 연결
  • 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 노드를 가리킴
• 특성:
  • 동적 메모리 할당으로 유연한 크기 조정 가능
  • 삽입, 삭제가 상대적으로 빠름 (O(1)) — 위치만 알면
  • 탐색은 선형 탐색 (O(n))

---

스택(Stack)의 개념과 작동 방식

• 정의: LIFO(Last In, First Out) 구조를 가지는 자료구조입니다.
• 연산:
  • push: 요소 추가
  • pop: 요소 제거
  • peek 또는 top: 가장 위에 있는 요소 확인
• 특성:
  • 재귀 호출, 괄호 검사, 함수 호출 스택 등에서 사용
  • 후입선출 구조이므로 순서 보존 및 역순 처리에 적합

---

큐(Queue)의 개념과 처리 순서

• 정의: FIFO(First In, First Out) 구조의 선형 자료구조입니다.
• 변형 구조:
  • 원형 큐(Circular Queue)
  • 우선순위 큐(Priority Queue)
  • 이중 큐(Deque: Double Ended Queue)
• 특성:
  • 먼저 들어온 데이터가 먼저 처리됨 (프린터 스풀, 작업 큐 등에 활용)
  • 삽입은 뒤(rear)에서, 삭제는 앞(front)에서 수행

---

비선형 자료구조의 구조와 동작 방식

비선형 자료구조는 데이터가 계층적(Tree), 네트워크적(Graph)으로 연결된 구조입니다. 데이터 간의 관계가 1:1이 아닌 1:N 혹은 N:N 형태로 표현됩니다.

---

트리(Tree)의 개념과 구성 요소

• 정의: 계층적인 구조를 가진 비선형 자료구조로, 노드들이 부모-자식 관계로 구성됩니다.
• 용어 정리:
  • 루트 노드(Root): 최상위 노드
  • 리프 노드(Leaf): 자식이 없는 노드
  • 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리
  • 깊이(Depth), 높이(Height), 차수(Degree)
• 종류:
  • 이진 트리(Binary Tree): 노드 당 자식이 최대 2개
  • 이진 탐색 트리(BST): 왼쪽 < 부모 < 오른쪽 구조
  • 힙(Heap): 완전 이진 트리 기반으로, 최소값 또는 최대값이 루트
  • 균형 트리(AVL, Red-Black Tree): 트리 높이 균형을 맞춘 구조

---

그래프(Graph)의 개념과 표현 방법

• 정의: 정점(Vertex)과 간선(Edge)으로 구성되며, 복잡한 관계를 표현할 수 있는 자료구조입니다.
• 분류:
  • 방향 그래프 / 무방향 그래프
  • 가중치 그래프(Weighted) / 비가중치 그래프
  • 인접 리스트 / 인접 행렬로 표현 가능
• 탐색 알고리즘:
  • DFS(Depth-First Search): 깊이 우선 탐색
  • BFS(Breadth-First Search): 너비 우선 탐색

---

추상 자료형(Abstract Data Type, ADT)의 개념과 중요성

추상 자료형이란, 자료구조를 수학적 개념으로 정의하고, 외부에서의 접근 방식(연산)을 정의하는 방식입니다. 내부 구현은 숨기고, 동작만 명세하는 것이 특징입니다.

• 예시:
  • 스택(ADT): push, pop, top, isEmpty 등의 연산만 공개
  • 큐(ADT): enqueue, dequeue, front, isEmpty 등의 연산만 사용

중요성:

• 모듈화, 캡슐화, 인터페이스 분리 설계에 유리
• 구현 변경 시 외부 시스템에 영향 없음
• 추상화를 통해 고수준 알고리즘 설계에 집중 가능

---

자료구조 선택의 기준과 면접에서 자주 묻는 질문

면접에서는 단순히 자료구조의 정의만 아는 것이 아니라, "왜 이 자료구조를 선택했는가?", "이 자료구조의 시간복잡도는 어떻게 되는가?", 그리고 "다른 자료구조와 비교해서 어떤 장점이 있는가?" 등의 질문이 빈번하게 출제됩니다.

자료구조 선택 시 고려 요소

• 데이터 접근 방식 (순차 vs 비순차)
• 삽입, 삭제, 탐색의 빈도
• 메모리 제약 조건
• 데이터 크기의 변동성
• 연산의 시간복잡도 (최악, 평균, 최선)

자주 나오는 면접 질문 예시

• 스택과 큐의 차이를 설명해보세요.
• 연결 리스트와 배열의 차이점은 무엇인가요?
• 이진 탐색 트리는 어떤 조건에서 유리한가요?
• DFS와 BFS의 차이와 각각의 장단점을 설명해보세요.
• 해시 테이블의 시간복잡도와 충돌 해결 방식은?

---

요약

• 자료구조는 데이터를 효율적으로 저장하고, 탐색 및 처리하는 방법론으로, 알고리즘의 성능에 직결되는 핵심 이론입니다.
• 선형 자료구조(배열, 리스트, 스택, 큐)는 데이터가 순차적으로 연결되는 구조이며, 각 구조별 특성과 연산 방식에 주목해야 합니다.
• 비선형 자료구조(트리, 그래프)는 데이터 간 계층적, 네트워크적 관계를 표현하며, 검색, 탐색 등의 고급 연산이 가능하게 합니다.
• 추상 자료형(ADT)은 내부 구현을 숨기고 동작만 명시하여 모듈화 및 유지보수성 향상에 기여합니다.
• 면접에서는 자료구조의 정의, 장단점, 시간복잡도, 활용 상황, 선택 이유까지 설명할 수 있어야 하며, 단편적인 암기보다는 구조 간 비교와 이해가 중요합니다.