1. 효율적 알고리즘의 토대, 데이터 구조(Data Structure)의 개요
정의: 컴퓨터 내에서 데이터를 효율적으로 사용할 수 있도록 데이터 간의 관계를 조직화하고 저장하는 방법.
중요성: 데이터 구조의 선택에 따라 프로그램의 **실행 속도(시간 복잡도)**와 **메모리 효율(공간 복잡도)**이 결정됨.
분류: 데이터의 연결 형태에 따라 선형 구조와 비선형 구조로 대별됨.
2. 선형 구조(Linear Structure)의 개념 및 유형
가. 선형 구조의 개념
데이터 요소들이 **일렬(Sequence)**로 나열되어 있으며, 자료들 간의 관계가 1:1인 구조.
데이터의 전후 관계가 명확하여 순차적인 접근이 용이함.
나. 선형 구조의 주요 유형
| 유형 | 특징 및 동작 원리 | 주요 용도 |
| 배열 (Array) | 연속된 메모리 공간에 동일 타입 저장. 인덱스로 접근($O(1)$) | 고정 크기 데이터 관리 |
| 연결 리스트 (Linked List) | 노드가 포인터로 연결됨. 삽입/삭제 시 오버헤드 적음 | 동적 크기 데이터 관리 |
| 스택 (Stack) | LIFO (Last-In-First-Out) 구조. 한쪽 끝에서만 데이터 처리 | 복귀 주소 저장, 재귀 호출 |
| 큐 (Queue) | FIFO (First-In-First-Out) 구조. 한쪽(Rear) 삽입, 한쪽(Front) 삭제 | 프로세스 스케줄링, 버퍼 |
| 데크 (Deque) | 양쪽 끝에서 모두 삽입과 삭제가 가능한 구조 | 스택과 큐의 혼합 형태 |
3. 비선형 구조(Non-Linear Structure)의 개념 및 유형
가. 비선형 구조의 개념
데이터 요소들이 일렬로 나열되지 않고 **계층적(Hierarchy)**이거나 망(Mesh) 형태를 이루는 구조.
자료들 간의 관계가 1:N 또는 N:N으로 복잡한 관계를 표현함.
나. 비선형 구조의 주요 유형
| 유형 | 특징 및 동작 원리 | 주요 용도 |
| 트리 (Tree) | 부모-자식 관계의 계층적 구조. 사이클이 없는 그래프 | 파일 시스템, 조직도, 이진 탐색 |
| 그래프 (Graph) | 정점(Vertex)과 간선(Edge)의 집합. 방향/무방향성 존재 | 지도 서비스, 소셜 네트워크(SNS) |
| 힙 (Heap) | 완전 이진 트리의 일종으로 우선순위 큐 구현에 최적화 | 우선순위 스케줄링 |
4. 선형 구조와 비선형 구조의 비교
| 구분 | 선형 구조 (Linear Structure) | 비선형 구조 (Non-Linear Structure) |
| 자료 관계 | 1 : 1 관계 | 1 : N 또는 N : N 관계 |
| 연결 형태 | 직선형, 연속적 | 분기형, 망형, 계층형 |
| 탐색 방법 | 순차 탐색 (Sequential Search) | 깊이 우선(DFS), 너비 우선(BFS) 탐색 |
| 구현 난이도 | 상대적으로 쉬움 | 상대적으로 복잡함 |
| 데이터 활용 | 단순 데이터 리스트 관리 | 복잡한 관계 표현 및 최적 경로 탐색 |
5. 데이터 구조 선택을 위한 기술적 제언
데이터 특성 파악: 데이터의 양, 데이터 간의 관계, 삽입/삭제 빈도에 따라 적절한 자료구조 선택이 필수적임. (예: 잦은 삽입/삭제 시 배열보다 연결 리스트가 유리)
알고리즘과의 연계: 자료구조는 알고리즘의 성능을 결정짓는 핵심 요소이므로, **시간 복잡도($O$-notation)**를 고려한 최적화된 설계가 요구됨.
결언: 인공지능, 빅데이터 등 대규모 데이터 처리 환경에서는 데이터 구조의 효율성이 시스템 전체의 성능(Throughput)과 직결되므로, 기초 자료구조에 대한 명확한 이해와 실무 적용 능력이 기술사의 핵심 역량임.
댓글 없음:
댓글 쓰기