ฅ^._.^ฅ

해시맵

해시맵(HashMap) 이란?

키(Key) - 값(Value) 쌍으로 데이터를 저장하는 데이터 구조

해시 함수(Hash Function) 를 사용하여 데이터를 특정 위치(Bucket) 에 저장

해시맵 사용 예제

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("apple", 5);
        map.put("banana", 10);
        map.put("cherry", 7);
        
        System.out.println(map.get("banana")); // 출력: 10
    }
}

➡︎ O(1) 시간 복잡도로 빠른 데이터 조회 가능

➡︎ 키-값 저장 방식으로 중복 키 허용 안됨

트리

트리(Tree) 란?

계층적 데이터 구조로, 부모-자식 관계를 가짐

검색, 정렬, 계층적 데이터 저장에 유리

이진 탐색 트리

Binary Search Tree, BST

각 노드의 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가짐 (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)

O(logN) 시간 복잡도로 탐색 가능 (균형이 잡힌 경우)

예제

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right);
        return root;
    }
}

➡︎ 계층적 데이터 표현 가능, 정렬된 데이터 탐색에 유리: O(logN)

➡︎ 균형이 깨지면 성능이 O(N) 까지 저하될 수 있음

균형 트리

• AVL 트리: 삽입/삭제 시 균형 유지 ➔ 항상 O(logN) 보장
• 레드-블랙 트리: 균형을 어느 정도 유지하면서 삽입/삭제 성능 향상

레드-블랙 트리 기반 TreeMap

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> tree = new TreeMap<>();
        tree.put(2, "apple");
        tree.put(1, "banana");
        tree.put(3, "cherry");

        System.out.println(tree.firstKey()); // 출력: 1
    }
}

➡︎ TreeMap 은 정렬된 순서로 데이터 저장하며, O(logN) 탐색 속도 제공

해시맵 vs 트리

‼️ 빠른 검색이 필요하면 HashMap, 정렬된 데이터가 필요하면 Tree

배열과 리스트

배열(Array) 이란?

메모리 상에서 연속된 공간을 차지하는 데이터 구조

인덱스를 이용하여 O(1) 시간 복잡도로 접근 가능

배열 예제

 int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers[2]); // O(1) - 즉시 접근 가능

➡︎ 빠른 조회 가능

➡︎ 크기가 고정되어 있고, 삽입/삭제가 비효율적

연결 리스트(Linked List) 란?

노드(Node) 와 포인터(Pointer) 로 구성된 데이터 구조

시간 복잡도: 삽입/삭제는 O(1), 검색 속도는 O(N)

단일 연결 리스트 예제

class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;
    
    void append(int data) {
        if (head == null) {
            head = new Node(data);
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(data);
    }
}

➡︎ 동적 크기 조절 가능

➡︎ 연속된 메모리 공간 사용하지 않아도 되지만, 노드 탐색 속도가 느림

배열 vs 연결 리스트 비교

스택과 큐

스택(Stack) 이란?

후입선출(LIFO, Last In First Out) 구조

재귀 함수 호출, 되돌리기(Undo), 괄호 검사 등에 활용

스택 예제

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 출력: 3 (후입선출)

➡︎ 마지막에 넣은 데이터가 가장 먼저 제거

큐(Queue) 란?

선입선출(FIFO, First In First Out) 구조

작업 대기열, 너비 우선 탐색(BFS) 등에 활용

큐 예제

import java.util.LinkedList;
import java.util.Queue;

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 출력: 1 (선입선출)

➡︎ 먼저 들어온 데이터가 먼저 제거

스택 vs 큐