2강. 기본 데이터 구조

2. 기본 데이터 구조

---

2.1 배열과 연결 리스트

배열(Array)
배열은 동일한 타입의 요소들이 연속적으로 저장되는 데이터 구조입니다. 배열은 인덱스를 이용해 요소에 접근할 수 있으며, 고정된 크기를 가집니다.

 

배열의 시간 복잡도:
- 접근: \(O(1)\)
배열은 인덱스를 통해 직접 접근할 수 있어, 접근 시간은 배열의 크기에 상관없이 일정합니다.

- 탐색: \(O(n)\)
배열에서 특정 값을 찾기 위해서는 배열의 모든 요소를 확인해야 하므로, 최악의 경우 모든 요소를 확인해야 합니다.

- 삽입/삭제: \(O(n)\)
배열에서 요소를 삽입하거나 삭제하려면 해당 위치 이후의 모든 요소를 이동시켜야 하기 때문에, 최악의 경우 배열의 모든 요소를 이동시켜야 합니다.

연결 리스트(Linked List)
연결 리스트는 각 요소가 노드로 구성되어 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가집니다. 연결 리스트는 동적으로 크기가 변할 수 있습니다.

연결 리스트의 시간 복잡도:
- 접근: \(O(n)\)
연결 리스트는 순차적으로 노드를 탐색해야 하므로, 특정 위치에 접근하기 위해서는 최악의 경우 리스트의 모든 노드를 확인해야 합니다.

- 탐색: \(O(n)\)
특정 값을 찾기 위해서도 모든 노드를 순차적으로 확인해야 합니다.

- 삽입/삭제: \(O(1)\)
노드를 삽입하거나 삭제할 때 포인터만 변경하면 되므로, 특정 위치에 대한 참조를 알고 있는 경우에는 삽입과 삭제가 빠릅니다.

// 배열 예시
public class ArrayExample {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5}; // 배열 선언 및 초기화
        System.out.println("배열의 첫 번째 요소: " + array[0]); // 배열 요소 접근
    }
}

// 연결 리스트 예시
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListExample {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        System.out.println("연결 리스트의 첫 번째 요소: " + head.data); // 연결 리스트 요소 접근
    }
}

2.2 스택과 큐

스택(Stack)
스택은 후입선출(LIFO) 구조를 가지는 데이터 구조로, 요소의 삽입과 삭제가 한쪽 끝에서만 일어납니다.

스택의 시간 복잡도:
- 접근: \(O(n)\)
특정 위치의 요소에 접근하기 위해서는 스택의 모든 요소를 확인해야 하므로, 최악의 경우 모든 요소를 확인해야 합니다.

- 탐색: \(O(n)\)
특정 값을 찾기 위해서도 스택의 모든 요소를 확인해야 합니다.

- 삽입/삭제: \(O(1)\)
삽입과 삭제는 스택의 맨 위에서만 일어나므로, 항상 일정한 시간이 소요됩니다.

큐(Queue)
큐는 선입선출(FIFO) 구조를 가지는 데이터 구조로, 요소의 삽입은 한쪽 끝에서, 삭제는 다른 쪽 끝에서 일어납니다.

큐의 시간 복잡도:
- 접근: \(O(n)\)
특정 위치의 요소에 접근하기 위해서는 큐의 모든 요소를 확인해야 하므로, 최악의 경우 모든 요소를 확인해야 합니다.

- 탐색: \(O(n)\)
특정 값을 찾기 위해서도 큐의 모든 요소를 확인해야 합니다.

- 삽입/삭제: \(O(1)\)
삽입과 삭제는 큐의 양 끝에서 일어나므로, 항상 일정한 시간이 소요됩니다.

// 스택 예시
import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("스택의 최상단 요소: " + stack.peek()); // 스택 최상단 요소 접근
    }
}

// 큐 예시
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println("큐의 첫 번째 요소: " + queue.peek()); // 큐 첫 번째 요소 접근
    }
}

2.3 해시 테이블

해시 테이블(Hash Table)
해시 테이블은 키-값 쌍을 저장하는 데이터 구조로, 해시 함수를 이용해 키를 해시 값으로 변환하여 저장합니다. 해시 테이블은 평균적으로 빠른 검색, 삽입, 삭제가 가능합니다.

해시 테이블의 시간 복잡도:
- 접근: \(O(1)\)
해시 함수를 통해 바로 접근할 수 있기 때문에, 접근 시간은 일정합니다.

- 탐색: \(O(1)\)
해시 값을 통해 해당 위치에 바로 접근할 수 있기 때문에, 탐색 시간도 일정합니다.

- 삽입/삭제: \(O(1)\)
해시 값을 통해 해당 위치에 바로 삽입하거나 삭제할 수 있기 때문에, 삽입과 삭제 시간도 일정합니다.

import java.util.HashMap;

public class HashTableExample {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        hashMap.put("one", 1);
        hashMap.put("two", 2);
        hashMap.put("three", 3);
        System.out.println("해시 테이블에서 'two'의 값: " + hashMap.get("two")); // 해시 테이블 요소 접근
    }
}

2.4 트리와 이진 트리

트리(Tree)
트리는 계층적인 데이터 구조로, 루트 노드와 자식 노드들로 구성됩니다. 각 노드는 자식 노드로의 포인터를 가집니다.

이진 트리(Binary Tree)
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 이진 트리는 검색, 삽입, 삭제가 비교적 효율적입니다.

이진 트리의 시간 복잡도:
- 접근: \(O(\log n)\)
트리의 높이에 따라 접근 시간이 결정되며, 이진 트리의 높이는 로그 스케일로 증가합니다.

- 탐색: \(O(\log n)\)
특정 값을 찾기 위해서는 트리의 높이만큼 탐색해야 하며, 이진 트리의 높이는 로그 스케일로 증가합니다.

- 삽입/삭제: \(O(\log n)\)
삽입과 삭제 역시 트리의 높이에 따라 결정되며, 이진 트리의 높이는 로그 스케일로 증가합니다.

// 이진 트리 예시
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class BinaryTreeExample {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println("이진 트리의 루트 노드 값: " + root.data); // 이진 트리 요소 접근
    }
}

2.5 그래프와 그래프 표현

그래프(Graph)
그래프는 노드(정점)와 노드 간의 연결(간선)으로 구성된 데이터 구조입니다. 그래프는 방향 그래프와 무방향 그래프로 나뉩니다.

그래프 표현
그래프를 표현하는 방법에는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있습니다.
- 인접 행렬: 노드 간의 연결 관계를 이차원 배열로 표현
- 인접 리스트: 노드의 인접 노드를 리스트로 표현

// 인접 리스트를 사용한 그래프 예시
import java.util.ArrayList;
import java.util.LinkedList;

class Graph {
    private int V; // 노드의 수
    private LinkedList adj[]; // 인접 리스트

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w); // 노드 v에 w를 추가
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        System.out.println("그래프의 노드 2의 인접 리스트: " + g.adj[2]); // 그래프 요소 접근
    }
}