1️⃣ 자료구조(Data Structure)

자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하며, 이를 통해 데이터를 효율적으로 접근하고 수정할 수 있도록 하는 체계적인 방법입니다.

자료구조는 알고리즘의 성능을 최적화하고 프로그램의 효율성을 향상시키는 데 중요한 역할을 합니다.

기본 개념.

자료구조는 데이터를 저장하는 방식과 데이터를 조작하는 방법을 정의합니다.

이는 데이터를 어떻게 배열하고, 접근하고, 수정하고, 삭제할지를 규정하는 규칙과 방법의 집합입니다.

주요 목적.

1. 효율적인 데이터 저장 및 접근.
   • 데이터를 효율적으로 저장하여 빠르게 접근하고 검색할 수 있도록 합니다.
2. 데이터 수정 및 삭제 용이.
   • 데이터를 쉽게 수정하고 삭제할 수 있도록 합니다.
3. 알고리즘 최적화.
   • 알고리즘의 성능을 최적화하고 실행 시간을 단축시킵니다.

주요 종류.

1. 배열(Array)
   • 고정된 크기의 연속된 메모리 공간에 데이터를 저장합니다.
   • 인덱스를 사용하여 데이터에 빠르게 접근할 수 있습니다.
2. 연결 리스트(Linked List)
   • 각 요소가 데이터와 다음 요소를 가리키는 포인터를 포함합니다.
   • 동적 크기 조절이 가능하며 삽입과 삭제가 용이합니다.
3. 스택(Stack)
   • 후입선출(LIFO, Last In First Out) 방식으로 동작합니다.
   • 데이터를 삽입하는 push와 삭제하는 pop 연산을 가집니다.
4. 큐(Queue)
   • 선입선출(FIFO, First In First Out) 방식으로 동작합니다.
   • 데이터를 삽입하는 enqueue와 삭제하는 dequeue 연산을 가집니다.
5. 트리(Tree)
   • 계층적 구조를 가지며, 노드와 에지로 구성됩니다.
   • 이진 트리, 이진 탐색 트리, AVL 트리 등 다양한 형태가 있습니다.
6. 그래프(Graph)
   • 노드(정점)와 에지(간선)로 구성된 자료구조로, 다양한 관계를 표현할 수 있습니다.
   • 방향 그래프, 무방향 그래프 등이 있습니다.
7. 해시 테이블(Hash Table)
   • 키-값 쌍을 저장하며, 해시 함수를 사용하여 데이터에 빠르게 접근할 수 있습니다.
   • 충돌 해결 방법으로 체이닝과 개방 주소법이 있습니다.

응용 사례.

자료구조는 데이터베이스, 운영체제, 네트워크, 인공지능, 게임 개발 등 다양한 분야에서 중요한 역할을 합니다.
적절한 자료구조의 선택은 프로그램의 성능과 효율성을 크게 향상시킬 수 있습니다.

2️⃣ 자료구조의 분류

1️⃣ 선형 자료구조(Linear Data Structure)

선형 자료구조(Linear Data Structure)는 데이터 요소들이 순차적으로 배열된 구조를 의미합니다.

이 자료구조에서는 데이터 요소들이 직선 형태로 연결되어 있으며, 각 요소는 한 다음 요소나 이전 요소와 연결되어 있습니다.

선형 자료구조의 주요 특징인 데이터 요소들이 한 줄로 배열되어 있다는 점 입니다.

주요 선형 자료구조르는 배열, 연결 리스트, 스택, 큐 등이 있습니다.

주요 선형 자료구조.

1. 배열(Array)
   • 정의 : 동일한 타입의 데이터 요소들이 연속된 메모리 공간에 저장되는 자료구조입니다.
   • 특징 : 고정된 크기를 가지며 인덱스를 통해 데이터에 빠르게 접근할 수 있습니다.
   • 예시 : 정수형 배열, 문자열 배열 등.
2. 연결 리스트(Linked List)
   • 정의 : 각 데이터 요소가 노드로 구성되고, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하는 자료구조입니다.
   • 특징 : 동적 크기 조절이 가능하며 삽입과 삭제가 용이하지만, 인덱스를 통한 접근은 배열보다 느립니다.
   • 종류 : 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등.
3. 스택(Stack)
   • 정의 : 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다.
   • 특징 : 데이터 삽입(push)과 삭제(pop)이 한쪽 끝에서만 이루어집니다.
   • 사용 사례 : 함수 호출 스택, 역순 문자열 처리 등.
4. 큐(Queue)
   • 정의 : 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조입니다.
   • 특징 : 데이터의 삽입(enqueue)은 한쪽 끝(후단)에서, 삭제(dequeue)는 반대쪽 끝(전단)에서 이루어집니다.
   • 종류 : 원형 큐, 우선순위 큐, 덱(Deque) 등.
   • 사용 사례 : 운영 체제의 작업 스케줄링, 프린터 대기열 등.

선형 자료구조의 특징 및 장단점.

• 특징.
  • 순차적 접근이 가능하며, 데이터를 차례대로 처리할 때 유리합니다.
  • 메모리에서 연속적으로 배치되므로 인덱스를 통해 직접 접근할 수 있습니다.(배열의 경우)
• 장점.
  • 간단하고 구현이 용이합니다.
  • 데이터의 삽입과 삭제가 특정 조건 하에 효율적일 수 있습니다(예: 스택, 큐)
• 단점
  • 데이터 크기에 따라 메모리 낭비가 발생할 수 있습니다(배열의 경우).
  • 특정 요소 접근이나 삽입/삭제 시 성능이 저하될 수 있습니다(연결 리스트의 경우)

마무리.

선형 자료구조는 데이터가 순차적으로 연결되어 있어 순차적 처리에 적합하며, 프로그램의 다양한 부분에서 사용되는 기초적인 자료구조입니다.

2️⃣ 비선형 자료구조(Non-linear Data Structure)

비선형 자료구조(Non-linear Data Structure)는 데이터 요소들이 계층적 또는 그물 형태로 배열된 구조를 의미합니다.

이 자료구조에서는 데이터 요소들이 순차적으로 배열되지 않고, 하나의 요소가 여러 요소들과 연결될 수 있습니다.

주요 비선형 자료구조로는 트리(Tree)와 그래프(Graph)가 있습니다.

주요 비선형 자료구조.

1. 트리(Tree)
   • 정의 : 노드와 그 노드들을 연결하는 간선으로 구성된 계층적 자료구조입니다. 트리는 루트 노드에서 시작하여 자식 노드로 분기하며, 사이클이 없습니다.
   • 특징 : 트리는 계층적 관계를 나타내며, 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
   • 종류 :
     • 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
     • 이진 탐색 트리(Binary Search Tree) : 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리입니다.
     • 균형 이진 트리(Balanced Binary Tree) : AVL 트리, 레드-블랙 트리 등과 같이 높이가 균형을 이루도록 유지되는 트리입니다.
     • 힙(Heap) : 완전 이진 트리의 일종으로, 최대 힙과 최소 힙이 있습니다.
     • 트라이(Trie) : 문자열을 저장하고 빠르게 검색하기 위해 사용되는 트리입니다.
2. 그래프(Graph)
   • 정의 : 정점(Vertex)들과 이 정점들을 연결하는 간선(Edge)들로 구성된 자료구조입니다.
   • 특징 : 그래프는 방향 그래프(Directed Graph)와 무방향 그래프(Undirceted Graph)로 나눌 수 있으며, 사이클이 존재할 수 있습니다.
   • 종류 :
     • 방향 그래프(Directed Graph) : 간선에 방향성이 있는 그래프입니다.
     • 무방향 그래프(Undirected Graph) : 간선에 방향성이 없는 그래프입니다.
     • 가중치 그래프(Weighted Graph) : 간선에 가중치가 부여된 그래프입니다.
     • 비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프입니다.

비선형 자료구조의 특징 및 장단점.

• 특징 :
  • 계층적 또는 네트워크 구조를 나태내는 데 적합합니다.
  • 복잡한 관계를 표현할 수 있으며, 데이터 요소 간의 다대다 관계를 처리할 수 있습니다.
• 장점 :
  • 데이터의 계층적 구조를 쉽게 표현할 수 있습니다(트리).
  • 복잡한 연결 관계를 효과적으로 모델링할 수 있습니다(그래프).
  • 특정 유형의 탐색, 정렬, 데이터 압축, 네트워크 라우팅 등에 유용합니다.
• 단점 :
  • 구현과 관리가 선형 자료구조보다 복잡할 수 있습니다.
  • 특정 작업(예: 트리의 균형 유지, 그래프 탐색 등)에서 추가적인 알고리즘이 필요합니다.

마무리.

비선형 자료구조는 데이터가 단순히 순차적으로 배열되지 않고, 복잡한 관계를 나타내는 경우에 사용됩니다.

예를 들어, 파일 시스템의 디렉터리 구조, 데이터베이스 인덱스, 소셜 네트워크의 사용자 관계 등이 비선형 자료구조를 활용하는 사례입니다.

2️⃣ 자료구조의 구현.

1️⃣ 추상 자료형(Abstract Data Type, ADT)

자바 프로그래밍에서의 추상 자료형(Abstract Data Type, ADT)은 데이터의 논리적 구조와 이를 조작하는 연산들을 명확하게 정의한 개념입니다.

ADT는 구현 세부 사항을 숨기고, 데이터와 연산의 인터페이스를 통해 사용자에게 추상적인 수준에서 데이터 조작을 제공합니다.

즉, ADT는 데이터가 어떻게 저장되고 구현되는지에 대한 정보는 감추고, 데이터와 상호작용하는 방법만을 정의합니다.

주요 개념

1. 추상화(Abstraction)
   • ADT는 데이터를 추상화하여 데이터의 실제 구현과 독립적으로 사용될 수 있도록 합니다.
   • 사용자는 데이터의 저장 방식이나 연산의 구현 방법을 알 필요 없이, ADT가 제공하는 인터페이스를 통해 데이터를 조작할 수 있습니다.
2. 인터페이스(Interface)
   • ADT는 데이터 타입과 이를 다루는 연산들을 인터페이스를 통해 정의합니다.
   • 자바에서는 인터페이스(Interface) 키워드를 사용하여 ADT의 연산을 정의할 수 있습니다.
3. 캡슐화(Encapsulation)
   • ADT는 데이터와 연산을 하나의 단위로 묶어 캡슐화합니다.
   • 데이터를 직접 접근하지 않고, 정의된 연산을 통해서만 접근할 수 있도록 하여 데이터 무결성을 보장합니다.

자바에서의 ADT 예시

다음은 자바에서 스택(Stack) ADT를 정의하고 구현하는 예시입니다.

스택 인터페이스 정의

public interface Stack<T> {
    void push(T item); // 스택에 아이템을 추가
    T pop(); // 스택에서 아이템을 제거하고 반환
    T peek(); // 스택의 맨 위 아이템을 반환(제거하지 않음)
    boolean isEmpty(); // 스택이 비어 있는지 확인
    int size(); // 스택의 크기 반환
}

스택 구현

import java.util.ArrayList;
import java.util.List;

public class ArrayListStack<T> implements Stack<T> {
    private List<T> list = new ArrayList<>();
    
    @Override
    public void push(T item) {
        list.add(item);
    }
    
    @Override
    public T pop() {
        if (isEmpty()) {
            throw new RuntimException("Stack is empty");
        }
        return list.remove(list.size() - 1);
    }
    
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return list.get(list.size() - 1);
    }
    
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    @Override
    public int size() {
        return list.size();
    }
}

설명

• ‘Stack<T>‘ 인터페이스는 스택 ADT의 연산을 정의합니다. 이 인터페이스는 ‘push’, ‘pop’, ‘peek’, ‘isEmpty’, ‘size’ 메서드를 포함합니다.

• ‘ArrayListStack<T>‘ 클래스는 ‘Stack<T>‘ 인터페이스를 구현합니다. 이 클래스는 ‘ArrayList’ 를 내부 데이터 구조로 사용하여 스택 연산을 구현합니다.
• ‘push’ 메서드는 스택에 아이템을 추가합니다.
• ‘pop’ 메서드는 스택에서 맨 위의 아이템을 제거하고 반환합니다.
• ‘peek’ 메서드는 스택의 맨 위 아이템을 제거하지 않고 반환합니다.
• ‘isEmpty’ 메서드는 스택이 비어 있는지 확인합니다.
• ‘size’ 메서드는 스택의 크기를 반환합니다.

이 예시에서 ‘Stack<T>‘ 인터페이스는 스택 ADT를 정의하고, ‘ArrayListStack<T>‘ 클래스는 이 ADT를 구현한 것입니다.

사용자는 ‘ArrayListStack’ 의 내부 구현을 알 필요 없이 ‘Stack’ 인터페이스를 통해 스택 연산을 사용할 수 있습니다.

이는 ADT의 주요 장점 중 하나인 구현의 독립성을 잘 보여줍니다.