트리 (Tree)

프로그래밍에서 트리(Tree)는 계층적 구조를 나타내는 자료구조로, 노드와 노드를 연결하는 간선으로 구성된다. 트리는 파일 시스템, 조직도, 의사결정 트리, 검색 트리 등 다양한 분야에서 활용된다.

트리를 이해하면 계층적 데이터를 효율적으로 관리하고 복잡한 문제를 체계적으로 해결할 수 있다. 하나씩 살펴보자.

트리의 정의와 특징

트리는 노드(Node)와 간선(Edge)으로 구성된 비선형 자료구조로, 하나의 루트 노드(Root Node)에서 시작해 계층적으로 연결된다. 트리는 사이클(Cycle)이 없는 연결 그래프이며, 각 노드는 부모 노드와 자식 노드로 계층적 관계를 형성한다.

트리의 주요 특징은 다음과 같다:

• 계층 구조: 루트에서 시작해 부모-자식 관계로 데이터를 조직화한다.
• 단일 경로: 두 노드 간에는 유일한 경로가 존재한다.
• 효율적 탐색: 이진 검색 트리 같은 경우 O(log n) 시간에 탐색이 가능하다.

단점은 다음과 같다:

• 복잡한 구현: 노드 간 연결 관리와 균형 조정이 필요하다.
• 메모리 사용: 포인터나 참조를 사용해 메모리 소모가 크다.
• 불균형 문제: 트리가 한쪽으로 치우치면 성능이 저하된다.

트리의 종류

트리는 구조와 특성에 따라 여러 가지로 나뉜다. 아래는 주요 트리 종류와 도식이다.

1. 이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가지는 트리다.

        [Root]
       /      \
    [Left]  [Right]
        

2. 이진 검색 트리(Binary Search Tree, BST)

왼쪽 서브트리의 값은 부모보다 작고, 오른쪽 서브트리의 값은 부모보다 크다.

         [5]
        /   \
      [3]   [7]
     /  \
   [1]  [4]
        

3. AVL 트리

각 노드의 좌우 서브트리 높이 차가 1 이하인 균형 이진 검색 트리다.

4. 레드-블랙 트리(Red-Black Tree)

노드에 색상(빨강/검정)을 추가해 균형을 유지하는 트리다.

5. 힙(Heap)

완전 이진 트리로, 부모 노드가 자식 노드보다 크거나(최대 힙) 작다(최소 힙).

         [10]
        /   \
      [5]   [7]
     /  \
   [2]  [3]
        

본 포스팅은 이진 트리와 이진 검색 트리를 중심으로 다룬다.

자바에서 이진 트리 구현

이진 트리는 노드와 좌우 자식 노드로 구성된다. 아래는 자바로 구현한 이진 트리다.

class BinaryTree {
    class Node {
        int data;
        Node left;
        Node right;
        
        Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
    
    private Node root;
    
    public BinaryTree() {
        root = null;
    }
    
    // 노드 삽입 (이진 검색 트리 기준)
    public void insert(int data) {
        root = insertRec(root, data);
    }
    
    private Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }
    
    // 전위 순회 (Preorder Traversal)
    public void preorder() {
        preorderRec(root);
        System.out.println();
    }
    
    private void preorderRec(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preorderRec(root.left);
            preorderRec(root.right);
        }
    }
}

이 코드는 이진 검색 트리로, 삽입과 전위 순회 기능을 포함한다.

트리의 기본 연산

트리의 주요 연산은 다음과 같다:

1. 삽입(Insert)

새로운 노드를 적절한 위치에 추가한다.

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

2. 삭제(Delete)

노드를 제거하고 트리의 구조를 유지한다.

private Node deleteRec(Node root, int data) {
    if (root == null) return root;
    if (data < root.data) {
        root.left = deleteRec(root.left, data);
    } else if (data > root.data) {
        root.right = deleteRec(root.right, data);
    } else {
        if (root.left == null) return root.right;
        else if (root.right == null) return root.left;
        root.data = minValue(root.right);
        root.right = deleteRec(root.right, root.data);
    }
    return root;
}

private int minValue(Node root) {
    int min = root.data;
    while (root.left != null) {
        min = root.left.data;
        root = root.left;
    }
    return min;
}

3. 순회(Traversal)

트리를 순회하는 방법은 전위, 중위, 후위 순회가 있다.

public void inorder() {
    inorderRec(root);
    System.out.println();
}

private void inorderRec(Node root) {
    if (root != null) {
        inorderRec(root.left);
        System.out.print(root.data + " ");
        inorderRec(root.right);
    }
}

4. 검색(Search)

특정 값을 가진 노드를 찾는다.

public boolean search(int data) {
    return searchRec(root, data);
}

private boolean searchRec(Node root, int data) {
    if (root == null || root.data == data) return root != null;
    if (data < root.data) return searchRec(root.left, data);
    return searchRec(root.right, data);
}

트리의 시간 복잡도

이진 검색 트리의 주요 연산 시간 복잡도는 다음과 같다:

• 삽입(Insert): 평균 O(log n), 최악 O(n)
• 삭제(Delete): 평균 O(log n), 최악 O(n)
• 검색(Search): 평균 O(log n), 최악 O(n)
• 순회(Traversal): O(n)

불균형 트리에서는 최악의 경우 O(n)이 되므로 AVL 트리나 레드-블랙 트리로 균형을 유지해야 한다.

트리를 활용한 알고리즘

트리는 다양한 알고리즘에 활용된다.

1. 이진 검색 트리 탐색

값을 빠르게 검색한다.

public boolean bstSearch(int data) {
    Node current = root;
    while (current != null) {
        if (current.data == data) return true;
        if (data < current.data) current = current.left;
        else current = current.right;
    }
    return false;
}

2. 트리 순회

전위, 중위, 후위 순회로 노드를 방문한다.

public void postorder() {
    postorderRec(root);
    System.out.println();
}

private void postorderRec(Node root) {
    if (root != null) {
        postorderRec(root.left);
        postorderRec(root.right);
        System.out.print(root.data + " ");
    }
}

3. 트리의 높이 계산

트리의 최대 깊이를 계산한다.

public int height() {
    return heightRec(root);
}

private int heightRec(Node root) {
    if (root == null) return 0;
    int leftHeight = heightRec(root.left);
    int rightHeight = heightRec(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

심화 주제: 트리 균형과 최적화

트리의 효율성을 높이려면 균형과 최적화 기법을 적용해야 한다.

1. AVL 트리 균형

노드 삽입/삭제 후 좌우 서브트리 높이 차를 1 이하로 유지한다.

class AVLTree {
    class Node {
        int data, height;
        Node left, right;
        
        Node(int data) {
            this.data = data;
            height = 1;
            left = right = null;
        }
    }
    
    private int height(Node node) {
        if (node == null) return 0;
        return node.height;
    }
    
    private int balanceFactor(Node node) {
        if (node == null) return 0;
        return height(node.left) - height(node.right);
    }
    
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        return x;
    }
}

2. 레드-블랙 트리

색상과 규칙을 통해 균형을 유지한다.

3. 세그먼트 트리

구간 쿼리를 효율적으로 처리한다.

class SegmentTree {
    private int[] tree;
    private int n;
    
    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 0, 0, n - 1);
    }
    
    private void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
}

트리의 한계와 대안

트리는 불균형 문제와 메모리 소모가 크다. 자바에서는 java.util.TreeMap과 java.util.TreeSet을 제공한다.

import java.util.TreeMap;

TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(1, 100);
map.put(2, 200);
int value = map.get(1); // 100

TreeMap은 레드-블랙 트리로 구현되어 균형을 유지한다.

문제

트리를 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고, 자바 코드로 해답을 제공한다.

5
3
1
4
2
5

1 2 3 4 5

import java.util.Scanner;

public class BSTTraversal {
    static class BinaryTree {
        static class Node {
            int data;
            Node left, right;
            
            Node(int data) {
                this.data = data;
                left = right = null;
            }
        }
        
        Node root;
        
        void insert(int data) {
            root = insertRec(root, data);
        }
        
        Node insertRec(Node root, int data) {
            if (root == null) {
                root = new Node(data);
                return root;
            }
            if (data < root.data) {
                root.left = insertRec(root.left, data);
            } else if (data > root.data) {
                root.right = insertRec(root.right, data);
            }
            return root;
        }
        
        void inorder() {
            inorderRec(root);
            System.out.println();
        }
        
        void inorderRec(Node root) {
            if (root != null) {
                inorderRec(root.left);
                System.out.print(root.data + " ");
                inorderRec(root.right);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        BinaryTree bst = new BinaryTree();
        
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            bst.insert(x);
        }
        
        bst.inorder();
        sc.close();
    }
}

5
1 2 3
2 4 -1
3 -1 5
4 -1 -1
5 -1 -1

3

import java.util.Scanner;

public class TreeHeight {
    static class Node {
        int data, leftIdx, rightIdx;
        
        Node(int data, int leftIdx, int rightIdx) {
            this.data = data;
            leftIdx = leftIdx;
            rightIdx = rightIdx;
        }
    }
    
    static int height(Node[] nodes, int idx) {
        if (idx == -1) return 0;
        int leftHeight = height(nodes, nodes[idx].leftIdx);
        int rightHeight = height(nodes, nodes[idx].rightIdx);
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Node[] nodes = new Node[N];
        
        for (int i = 0; i < N; i++) {
            int data = sc.nextInt();
            int left = sc.nextInt();
            int right = sc.nextInt();
            nodes[i] = new Node(data, left, right);
        }
        
        System.out.println(height(nodes, 0));
        sc.close();
    }
}

5 3
1 2 3 4 5
1 1 3
0 2 10
1 1 3

6
14

import java.util.Scanner;

public class SegmentTreeSum {
    static class SegmentTree {
        long[] tree;
        int n;
        
        SegmentTree(int[] arr) {
            n = arr.length;
            tree = new long[4 * n];
            build(arr, 0, 0, n - 1);
        }
        
        void build(int[] arr, int node, int start, int end) {
            if (start == end) {
                tree[node] = arr[start];
            } else {
                int mid = (start + end) / 2;
                build(arr, 2 * node + 1, start, mid);
                build(arr, 2 * node + 2, mid + 1, end);
                tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
            }
        }
        
        void update(int idx, int val, int node, int start, int end) {
            if (start == end) {
                tree[node] = val;
            } else {
                int mid = (start + end) / 2;
                if (start <= idx && idx <= mid) {
                    update(idx, val, 2 * node + 1, start, mid);
                } else {
                    update(idx, val, 2 * node + 2, mid + 1, end);
                }
                tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
            }
        }
        
        long query(int l, int r, int node, int start, int end) {
            if (r < start || end < l) return 0;
            if (l <= start && end <= r) return tree[node];
            int mid = (start + end) / 2;
            long leftSum = query(l, r, 2 * node + 1, start, mid);
            long rightSum = query(l, r, 2 * node + 2, mid + 1, end);
            return leftSum + rightSum;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N];
        
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        
        SegmentTree segTree = new SegmentTree(arr);
        
        for (int i = 0; i < M; i++) {
            int type = sc.nextInt();
            if (type == 0) {
                int idx = sc.nextInt() - 1;
                int val = sc.nextInt();
                segTree.update(idx, val, 0, 0, N - 1);
            } else {
                int l = sc.nextInt() - 1;
                int r = sc.nextInt() - 1;
                System.out.println(segTree.query(l, r, 0, 0, N - 1));
            }
        }
        sc.close();
    }
}

마무리

트리는 계층적 데이터를 관리하는 강력한 자료구조로, 이진 트리, 이진 검색 트리, AVL 트리, 세그먼트 트리 등을 다뤘다. 삽입, 삭제, 순회, 검색 등의 연산과 시간 복잡도, 최적화 기법, 활용 사례를 살펴봤다. 자바의 TreeMap과 TreeSet을 통해 구현의 편리함을 확인했다. 문제를 통해 트리의 동작을 익혔으니, 이를 바탕으로 더 복잡한 문제를 해결해보자.

우선순위 큐 (Priority Queue)

프로그래밍에서 우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 처리되는 자료구조이다. 일반적인 큐가 FIFO(First In, First Out) 방식으로 동작하는 반면, 우선순위 큐는 요소의 우선순위에 따라 순서를 결정한다. 우선순위 큐는 다익스트라 알고리즘, 프림 알고리즘, 허프만 코딩 등에서 사용된다.

우선순위 큐를 이해하면 데이터를 우선순위에 따라 효율적으로 처리할 수 있다. 하나씩 살펴보자.

우선순위 큐의 정의와 특징

우선순위 큐는 각 요소에 우선순위가 부여된 자료구조로, 가장 높은(또는 낮은) 우선순위를 가진 요소가 먼저 제거된다. 일반적으로 최소 힙(Min Heap) 또는 최대 힙(Max Heap)을 사용해 구현된다. 요소를 추가하는 연산은 삽입(insert), 제거하는 연산은 삭제(delete)라고 부른다.

우선순위 큐의 장점은 다음과 같다:

• 우선순위 기반 처리: 요소를 우선순위 순으로 처리한다.
• 효율적인 연산: 힙 기반 구현 시 삽입과 삭제가 O(log n) 시간에 수행된다.
• 다양한 활용: 최단 경로, 최소 신장 트리, 스케줄링 등에 적합하다.

단점은 다음과 같다:

• 제한된 접근: 가장 높은 우선순위 요소만 접근 가능하다.
• 복잡한 구현: 힙 구조를 유지하기 위한 추가 작업이 필요하다.
• 메모리 사용: 힙 구현 시 추가 메모리가 필요할 수 있다.

우선순위 큐의 종류

우선순위 큐는 구현 방식에 따라 여러 가지로 나뉜다. 아래는 주요 형태와 구조를 도식화한 그림이다.

1. 최소 힙 기반 우선순위 큐(Min Heap-based Priority Queue)

가장 작은 값을 우선순위로 처리한다.

       1
      / \
     3   5
    / \
   7   9
        

2. 최대 힙 기반 우선순위 큐(Max Heap-based Priority Queue)

가장 큰 값을 우선순위로 처리한다.

       9
      / \
     7   5
    / \
   3   1
        

3. 배열 기반 우선순위 큐(Array-based Priority Queue)

정렬된 배열을 사용해 구현한다. 삽입은 O(n)이지만, 삭제는 O(1)이다.

[1][3][5][7][9]
 ↑
Front (최소값)
        

이 포스팅에서는 힙 기반 우선순위 큐를 중심으로 설명하며, 필요 시 다른 구현을 다룬다.

자바에서 최소 힙 기반 우선순위 큐 구현

최소 힙 기반 우선순위 큐는 배열을 사용해 구현하며, 부모 노드가 자식 노드보다 작거나 같은 힙 속성을 유지한다.

class MinHeapPriorityQueue {
    private int[] heap;
    private int size;
    private int capacity;
    
    public MinHeapPriorityQueue(int capacity) {
        heap = new int[capacity];
        size = 0;
        this.capacity = capacity;
    }
    
    private int parent(int index) {
        return (index - 1) / 2;
    }
    
    private int leftChild(int index) {
        return 2 * index + 1;
    }
    
    private int rightChild(int index) {
        return 2 * index + 2;
    }
    
    public void insert(int value) {
        if (size >= capacity) {
            System.out.println("Priority Queue is Full");
            return;
        }
        heap[size] = value;
        int current = size;
        size++;
        
        while (current > 0 && heap[current] < heap[parent(current)] ) {
            int temp = heap[current];
            heap[current] = heap[parent(current)];
            heap[parent(current)] = temp;
            current = parent(current);
        }
    }
    
    private void heapify(int index) {
        int smallest = index;
        int left = leftChild(index);
        int right = rightChild(index);
        
        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }
        
        if (smallest != index) {
            int temp = heap[index];
            heap[index] = heap[smallest];
            heap[smallest] = temp;
            heapify(smallest);
        }
    }
    
    public int deleteMin() {
        if (size == 0) {
            System.out.println("Priority Queue is Empty");
            return -1;
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        if (size > 0) {
            heapify(0);
        }
        return min;
    }
    
    public int peek() {
        if (size == 0) {
            System.out.println("Priority Queue is Empty");
            return -1;
        }
        return heap[0];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

이 코드는 최소 힙 기반 우선순위 큐로, 삽입, 최소값 삭제, 피크, 비어 있음 확인 기능을 포함한다.

우선순위 큐의 기본 연산

우선순위 큐의 주요 연산은 다음과 같다:

1. 삽입(Insert)

새로운 요소를 힙의 끝에 추가하고, 힙 속성을 유지하기 위해 상향 조정한다.

public void insert(int value) {
    if (size >= capacity) {
        System.out.println("Priority Queue is Full");
        return;
    }
    heap[size] = value;
    int current = size;
    size++;
    
    while (current > 0 && heap[current] < heap[parent(current)] ) {
        int temp = heap[current];
        heap[current] = heap[parent(current)];
        heap[parent(current)] = temp;
        current = parent(current);
    }
}

2. 최소값 삭제(Delete Min)

루트(최소값)를 제거하고, 힙의 마지막 요소를 루트로 이동시킨 후 힙 속성을 유지한다.

public int deleteMin() {
    if (size == 0) {
        System.out.println("Priority Queue is Empty");
        return -1;
    }
    int min = heap[0];
    heap[0] = heap[size - 1];
    size--;
    if (size > 0) {
        heapify(0);
    }
    return min;
}

3. 피크(Peek)

최소값을 제거하지 않고 반환한다.

public int peek() {
    if (size == 0) {
        System.out.println("Priority Queue is Empty");
        return -1;
    }
    return heap[0];
}

4. 비어 있음 확인(IsEmpty)

우선순위 큐가 비어 있는지 확인한다.

public boolean isEmpty() {
    return size == 0;
}

우선순위 큐의 시간 복잡도

힙 기반 우선순위 큐의 주요 연산의 시간 복잡도는 다음과 같다:

• 삽입(Insert): O(log n)
• 최소값 삭제(Delete Min): O(log n)
• 피크(Peek): O(1)
• 비어 있음 확인(IsEmpty): O(1)

배열 기반 우선순위 큐는 삽입이 O(n), 삭제가 O(1)이다. 힙 기반이 일반적으로 더 효율적이다.

연결 리스트 기반 우선순위 큐 구현

연결 리스트를 사용한 우선순위 큐는 동적 크기 조정이 가능하지만, 삽입 시 정렬이 필요하다.

class LinkedPriorityQueue {
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node head;
    
    public LinkedPriorityQueue() {
        head = null;
    }
    
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null || head.data > data) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null && current.next.data < data) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
    }
    
    public int deleteMin() {
        if (head == null) {
            System.out.println("Priority Queue is Empty");
            return -1;
        }
        int min = head.data;
        head = head.next;
        return min;
    }
    
    public int peek() {
        if (head == null) {
            System.out.println("Priority Queue is Empty");
            return -1;
        }
        return head.data;
    }
    
    public boolean isEmpty() {
        return head == null;
    }
}

연결 리스트 기반 우선순위 큐는 삽입이 O(n)이지만, 삭제는 O(1)이다.

우선순위 큐를 활용한 알고리즘

우선순위 큐는 다익스트라 알고리즘, 프림 알고리즘, 허프만 코딩 등에서 사용된다.

1. 다익스트라 알고리즘(Dijkstra’s Algorithm)

그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는다.

import java.util.*;

class Dijkstra {
    static class Edge {
        int dest, weight;
        Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
    
    public int[] dijkstra(List<Edge>[] graph, int start, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[] {start, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int d = current[1];
            
            if (d > dist[u]) continue;
            
            for (Edge e : graph[u]) {
                int v = e.dest;
                int weight = e.weight;
                
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[] {v, dist[v]});
                }
            }
        }
        return dist;
    }
}

2. 프림 알고리즘(Prim’s Algorithm)

그래프에서 최소 신장 트리를 구성한다.

import java.util.*;

class Prim {
    static class Edge {
        int dest, weight;
        Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
    
    public long prim(List<Edge>[] graph, int n) {
        boolean[] visited = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        long totalWeight = 0;
        
        pq.offer(new int[] {0, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int weight = current[1];
            
            if (visited[u]) continue;
            visited[u] = true;
            totalWeight += weight;
            
            for (Edge e : graph[u]) {
                if (!visited[e.dest]) {
                    pq.offer(new int[] {e.dest, e.weight});
                }
            }
        }
        return totalWeight;
    }
}

3. 허프만 코딩(Huffman Coding)

빈도 기반으로 최적의 이진 코드를 생성한다.

import java.util.*;

class Huffman {
    static class Node {
        char ch;
        int freq;
        Node left, right;
        Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
    }
    
    public Node buildHuffmanTree(char[] chars, int[] freq) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
        
        for (int i = 0; i < chars.length; i++) {
            pq.offer(new Node(chars[i], freq[i], null, null));
        }
        
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            pq.offer(new Node('\0', left.freq + right.freq, left, right));
        }
        return pq.poll();
    }
}

심화 주제: 우선순위 큐 최적화

우선순위 큐를 효율적으로 사용하려면 몇 가지 기법을 고려해야 한다.

1. 동적 배열 확장

힙 기반 우선순위 큐에서 배열 크기를 동적으로 확장한다.

public void insert(int value) {
    if (size >= capacity) {
        int[] newHeap = new int[capacity * 2];
        for (int i = 0; i < size; i++) {
            newHeap[i] = heap[i];
        }
        heap = newHeap;
        capacity *= 2;
    }
    heap[size] = value;
    int current = size;
    size++;
    
    while (current > 0 && heap[current] < heap[parent(current)] ) {
        int temp = heap[current];
        heap[current] = heap[parent(current)];
        heap[parent(current)] = temp;
        current = parent(current);
    }
}

2. 피보나치 힙(Fibonacci Heap)

삽입과 키 감소 연산을 O(1) 상각 시간에 처리한다. 복잡한 구현이 필요하다.

3. 쌍대 우선순위 큐(Dual Priority Queue)

최소값과 최대값을 모두 처리할 수 있는 구조로, 두 개의 힙을 조합해 구현한다.

우선순위 큐의 한계와 대안

우선순위 큐는 접근이 제한적이며, 힙 유지 비용이 있다. 자바에서는 java.util.PriorityQueue를 제공한다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
int min = pq.poll(); // 1

PriorityQueue는 최소 힙 기반이며, 최대 힙은 비교자를 반대로 설정해 구현한다.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
pq.offer(3);
pq.offer(1);
int max = pq.poll(); // 3

문제

우선순위 큐를 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고, 자바 코드로 해답을 제공한다.

5
insert 3
insert 1
deleteMin
insert 2
deleteMin

1
2

import java.util.Scanner;

public class PriorityQueueOperations {
    static class MinHeapPriorityQueue {
        private int[] heap;
        private int size;
        private int capacity;
        
        MinHeapPriorityQueue(int capacity) {
            heap = new int[capacity];
            size = 0;
            this.capacity = capacity;
        }
        
        private int parent(int index) {
            return (index - 1) / 2;
        }
        
        private int leftChild(int index) {
            return 2 * index + 1;
        }
        
        private int rightChild(int index) {
            return 2 * index + 2;
        }
        
        void insert(int value) {
            heap[size] = value;
            int current = size;
            size++;
            
            while (current > 0 && heap[current] < heap[parent(current)] ) {
                int temp = heap[current];
                heap[current] = heap[parent(current)];
                heap[parent(current)] = temp;
                current = parent(current);
            }
        }
        
        private void heapify(int index) {
            int smallest = index;
            int left = leftChild(index);
            int right = rightChild(index);
            
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
            
            if (smallest != index) {
                int temp = heap[index];
                heap[index] = heap[smallest];
                heap[smallest] = temp;
                heapify(smallest);
            }
        }
        
        int deleteMin() {
            if (size == 0) return -1;
            int min = heap[0];
            heap[0] = heap[size - 1];
            size--;
            if (size > 0) {
                heapify(0);
            }
            return min;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        MinHeapPriorityQueue pq = new MinHeapPriorityQueue(N);
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            if (operation.startsWith("insert")) {
                int x = Integer.parseInt(operation.split(" ")[1]);
                pq.insert(x);
            } else {
                System.out.println(pq.deleteMin());
            }
        }
        sc.close();
    }
}

5 3
4 2 5 1 3

3

import java.util.Scanner;

public class KthSmallest {
    static class MinHeapPriorityQueue {
        private int[] heap;
        private int size;
        private int capacity;
        
        MinHeapPriorityQueue(int capacity) {
            heap = new int[capacity];
            size = 0;
            this.capacity = capacity;
        }
        
        private int parent(int index) {
            return (index - 1) / 2;
        }
        
        private int leftChild(int index) {
            return 2 * index + 1;
        }
        
        private int rightChild(int index) {
            return 2 * index + 2;
        }
        
        void insert(int value) {
            heap[size] = value;
            int current = size;
            size++;
            
            while (current > 0 && heap[current] < heap[parent(current)] ) {
                int temp = heap[current];
                heap[current] = heap[parent(current)];
                heap[parent(current)] = temp;
                current = parent(current);
            }
        }
        
        private void heapify(int index) {
            int smallest = index;
            int left = leftChild(index);
            int right = rightChild(index);
            
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
            
            if (smallest != index) {
                int temp = heap[index];
                heap[index] = heap[smallest];
                heap[smallest] = temp;
                heapify(smallest);
            }
        }
        
        int deleteMin() {
            if (size == 0) return -1;
            int min = heap[0];
            heap[0] = heap[size - 1];
            size--;
            if (size > 0) {
                heapify(0);
            }
            return min;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        MinHeapPriorityQueue pq = new MinHeapPriorityQueue(N);
        
        for (int i = 0; i < N; i++) {
            pq.insert(sc.nextInt());
        }
        
        int result = 0;
        for (int i = 0; i < K; i++) {
            result = pq.deleteMin();
        }
        
        System.out.println(result);
        sc.close();
    }
}

맵 (Map)

프로그래밍에서 맵(Map)은 키-값 쌍을 저장하고 관리하는 자료구조이다. 키를 통해 값을 빠르게 검색할 수 있다. 자바에서는 java.util.Map 인터페이스를 통해 다양한 맵 구현체를 제공한다. 맵은 데이터베이스 인덱스, 캐싱, 빈도수 계산 등에서 사용된다. 이 글은 맵의 기본 개념, 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.

맵을 이해하면 데이터를 효율적으로 관리하고 검색할 수 있다. 순서대로 살펴본다.

맵의 정의와 특징

맵은 키-값 쌍을 저장하는 자료구조로, 각 키는 유일해야 한다. 키를 통해 값을 빠르게 검색할 수 있다. 맵의 주요 연산은 다음과 같다:

• put(key, value): 키-값 쌍을 추가한다.
• get(key): 키에 해당하는 값을 반환한다.
• remove(key): 키에 해당하는 키-값 쌍을 제거한다.
• containsKey(key): 키가 존재하는지 확인한다.
• size(): 맵의 크기를 반환한다.

맵의 장점은 다음과 같다:

• 빠른 검색: 키를 통해 값을 O(1) 시간에 검색할 수 있다 (HashMap 기준).
• 유연한 관리: 키-값 쌍을 통해 다양한 데이터를 관리할 수 있다.
• 다양한 활용: 데이터베이스 인덱스, 캐싱, 빈도수 계산 등에 유용하다.

단점은 다음과 같다:

• 메모리 사용량: 해시 테이블 등으로 인해 메모리 사용량이 많을 수 있다.
• 키의 유일성: 키가 중복되면 안 된다.
• 순서 보장: 일부 맵은 삽입 순서를 보장하지 않는다.

맵의 종류

맵은 구현 방식에 따라 여러 가지로 나뉜다. 자바에서는 주로 HashMap, TreeMap, LinkedHashMap을 사용한다.

1. HashMap

해시 테이블을 기반으로 하여 빠른 검색 속도를 제공한다. 키의 순서를 보장하지 않는다.

[Key: "apple", Value: 1000] → [Key: "banana", Value: 2000]
        

2. TreeMap

이진 검색 트리를 기반으로 하여 키를 정렬된 순서로 관리한다.

[Key: "apple", Value: 1000] ← [Key: "banana", Value: 2000] → [Key: "orange", Value: 1500]
        

3. LinkedHashMap

해시 테이블과 연결 리스트를 결합하여 삽입 순서를 유지한다.

[Key: "apple", Value: 1000] → [Key: "banana", Value: 2000] → [Key: "orange", Value: 1500]
        

자바에서 맵 구현

자바에서는 java.util.Map 인터페이스를 구현한 클래스를 제공한다. 아래는 HashMap, TreeMap, LinkedHashMap의 특징과 사용 방법을 설명한다.

1. HashMap

HashMap은 해시 테이블을 기반으로 하여 키-값 쌍을 저장한다. 키의 해시 코드를 사용하여 값을 빠르게 검색한다.

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("사과", 1000);
        map.put("바나나", 2000);
        map.put("오렌지", 1500);
        
        System.out.println(map.get("사과"));   // 1000
        System.out.println(map.get("바나나")); // 2000
        System.out.println(map.get("오렌지")); // 1500
    }
}

2. TreeMap

TreeMap은 이진 검색 트리를 기반으로 하여 키를 정렬된 순서로 관리한다. 키는 Comparable 인터페이스를 구현하거나 Comparator를 제공해야 한다.

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("사과", 1000);
        map.put("바나나", 2000);
        map.put("오렌지", 1500);
        
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        // 출력: 바나나: 2000, 사과: 1000, 오렌지: 1500
    }
}

3. LinkedHashMap

LinkedHashMap은 해시 테이블과 연결 리스트를 결합하여 삽입 순서를 유지한다.

import java.util.LinkedHashMap;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        map.put("사과", 1000);
        map.put("바나나", 2000);
        map.put("오렌지", 1500);
        
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        // 출력: 사과: 1000, 바나나: 2000, 오렌지: 1500
    }
}

맵의 기본 연산

맵의 주요 연산은 다음과 같다:

• put(key, value): 키-값 쌍을 추가한다. 이미 키가 존재하면 값을 업데이트한다.
• get(key): 키에 해당하는 값을 반환한다. 키가 없으면 null을 반환한다.
• remove(key): 키에 해당하는 키-값 쌍을 제거한다.
• containsKey(key): 키가 존재하는지 확인한다.
• size(): 맵의 크기를 반환한다.

맵의 시간 복잡도

맵의 주요 연산의 시간 복잡도는 다음과 같다:

• put(key, value): O(1) (HashMap), O(log n) (TreeMap)
• get(key): O(1) (HashMap), O(log n) (TreeMap)
• remove(key): O(1) (HashMap), O(log n) (TreeMap)
• containsKey(key): O(1) (HashMap), O(log n) (TreeMap)
• size(): O(1)

HashMap은 평균적으로 O(1) 시간을 제공하지만, 해시 충돌이 심할 경우 O(n)으로 악화될 수 있다. TreeMap은 항상 O(log n)을 보장한다.

맵을 활용한 알고리즘

맵은 다양한 알고리즘에서 활용된다. 아래는 대표적인 사례이다.

1. 빈도수 계산

배열에서 각 요소의 빈도수를 계산한다.

import java.util.HashMap;

public class FrequencyCounter {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 1, 4, 5, 4};
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        for (int key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

2. 캐싱

캐싱을 통해 자주 사용되는 데이터를 빠르게 접근한다.

import java.util.HashMap;

public class CacheExample {
    private HashMap<String, String> cache = new HashMap<>();
    
    public String getData(String key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        String data = fetchDataFromDatabase(key);
        cache.put(key, data);
        return data;
    }
    
    private String fetchDataFromDatabase(String key) {
        return "data for " + key;
    }
}

3. 데이터베이스 인덱스

키를 통해 레코드를 빠르게 검색한다.

import java.util.HashMap;

public class DatabaseIndex {
    static class Record {
        String data;
        Record(String data) {
            this.data = data;
        }
    }
    
    private HashMap<String, Record> index = new HashMap<>();
    
    public void addRecord(String key, Record record) {
        index.put(key, record);
    }
    
    public Record getRecord(String key) {
        return index.get(key);
    }
}

심화 주제: 맵의 내부 구현

맵의 내부 구현을 이해하면 맵을 효율적으로 사용할 수 있다.

1. HashMap의 내부 구현

HashMap은 해시 테이블을 기반으로 하여 키-값 쌍을 저장한다. 해시 테이블은 배열과 연결 리스트를 결합한 구조이다. 각 배열의 인덱스는 키의 해시 코드를 통해 계산된다. 해시 충돌이 발생할 경우, 동일한 인덱스에 연결 리스트를 사용하여 키-값 쌍을 저장한다. 자바 8 이후로는 충돌이 심할 경우 연결 리스트 대신 레드-블랙 트리로 전환된다.

해시 함수는 다음과 같이 동작한다:

• 키의 hashCode()를 호출하여 해시 코드를 얻는다.
• 해시 코드를 배열 크기로 나눈 나머지를 인덱스로 사용한다.

해시 충돌 처리 방법은 다음과 같다:

• 체이닝(Chaining): 연결 리스트로 충돌을 해결한다.
• 오픈 어드레싱(Open Addressing): 다른 빈 슬롯을 탐색한다.

2. TreeMap의 내부 구현

TreeMap은 레드-블랙 트리를 기반으로 하여 키를 정렬된 순서로 관리한다. 레드-블랙 트리는 자가 균형 이진 검색 트리로, 삽입, 삭제, 검색 연산을 O(log n) 시간에 수행한다. 주요 속성은 다음과 같다:

• 각 노드는 빨간색 또는 검은색이다.
• 루트는 항상 검은색이다.
• 모든 리프 노드는 검은색이다.
• 빨간색 노드의 자식은 검은색이다.
• 모든 경로에서 리프까지의 검은색 노드 수는 동일하다.

맵의 한계와 대안

맵은 키-값 쌍을 관리하는 데 유용하지만 한계가 존재한다:

• 메모리 사용량: 해시 테이블 등으로 인해 메모리 사용량이 많다.
• 키의 유일성: 키가 중복되면 안 된다.
• 순서 보장: 일부 맵은 삽입 순서를 보장하지 않는다.

대안으로는 다음과 같은 자료구조를 사용할 수 있다:

• 배열: 키가 정수일 경우 값을 저장한다.
• 리스트: 키-값 쌍을 순차적으로 검색한다.
• 트리: 이진 검색 트리로 키를 정렬한다.

문제

맵을 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고 자바 코드로 해답을 제공한다.

5
put apple 1000
put banana 2000
get apple
put orange 1500
get orange

1000
1500

import java.util.HashMap;
import java.util.Scanner;

public class MapOperations {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashMap<String, Integer> map = new HashMap<>();
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            String[] parts = operation.split(" ");
            if (parts[0].equals("put")) {
                String key = parts[1];
                int value = Integer.parseInt(parts[2]);
                map.put(key, value);
            } else {
                String key = parts[1];
                System.out.println(map.getOrDefault(key, -1));
            }
        }
        sc.close();
    }
}

8
1 2 3 2 1 4 5 4

1: 2
2: 2
3: 1
4: 2
5: 1

import java.util.Scanner;
import java.util.TreeMap;

public class FrequencyCounter {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        for (int key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        sc.close();
    }
}

5
fetch apple
fetch banana
fetch apple
fetch orange
fetch banana

data for apple (from database)
data for banana (from database)
data for apple (from cache)
data for orange (from database)
data for banana (from cache)

import java.util.HashMap;
import java.util.Scanner;

public class CacheExample {
    private HashMap<String, String> cache = new HashMap<>();
    
    public String fetch(String key) {
        if (cache.containsKey(key)) {
            return cache.get(key) + " (from cache)";
        }
        String data = fetchDataFromDatabase(key);
        cache.put(key, data);
        return data + " (from database)";
    }
    
    private String fetchDataFromDatabase(String key) {
        return "data for " + key;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        CacheExample cacheExample = new CacheExample();
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            String[] parts = operation.split(" ");
            String key = parts[1];
            System.out.println(cacheExample.fetch(key));
        }
        sc.close();
    }
}

마무리

맵은 키-값 쌍을 관리하는 자료구조로, 빠른 검색 속도와 유연한 데이터 관리를 제공한다. 자바에서는 HashMap, TreeMap, LinkedHashMap 등 다양한 구현체를 제공한다. 맵을 활용한 알고리즘으로는 빈도수 계산, 캐싱, 데이터베이스 인덱스가 있다. 내부 구현을 이해하면 맵을 더 효율적으로 사용할 수 있다. 문제를 통해 맵을 조작하는 방법을 익혔으니, 이를 바탕으로 복잡한 문제를 해결할 수 있다.

집합 (Set)

프로그래밍에서 집합(Set)은 중복되지 않는 고유한 요소들의 모음으로, 수학적 집합 개념을 기반으로 한다. 집합은 요소의 순서가 없으며, 동일한 요소가 두 번 이상 포함될 수 없다. 집합은 데이터 중복 제거, 멤버십 테스트, 교집합, 합집합 등의 연산에서 사용된다. 본 포스팅은 집합의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.

집합의 정의와 특징

집합은 고유한 요소들로 구성된 자료구조로, 각 요소는 단 한 번만 나타난다. 집합은 중복 제거, 멤버십 테스트, 집합 연산을 효율적으로 수행한다. 집합의 주요 특징은 다음과 같다:

• 중복 없음: 동일한 요소는 한 번만 저장된다.
• 순서 없음: 요소 간 순서가 정의되지 않는다.
• 빠른 조회: 요소 존재 여부를 O(1) 또는 O(log n) 시간에 확인한다.

집합의 장점은 다음과 같다:

• 효율적인 중복 제거: 중복 데이터를 자동으로 처리한다.
• 빠른 멤버십 테스트: 요소 포함 여부를 신속히 확인한다.
• 집합 연산 지원: 교집합, 합집합, 차집합 등을 수행한다.

단점은 다음과 같다:

• 순서 정보 부재: 인덱스나 순서를 통해 요소에 접근할 수 없다.
• 메모리 사용: 해시 기반 집합은 메모리를 더 사용할 수 있다.
• 복잡한 구현: 트리 기반 집합은 구현이 복잡할 수 있다.

집합의 종류

집합은 구현 방식에 따라 여러 형태로 나뉜다. 아래는 주요 구현 방식이다.

1. 해시 기반 집합(Hash-based Set)

해시 테이블을 사용해 요소를 저장한다. 평균적으로 O(1) 시간에 삽입, 삭제, 조회를 수행한다.

[Hash Table]
  [0] → [Element1]
  [1] → [Element2] → [Element3]
  ...
        

2. 트리 기반 집합(Tree-based Set)

이진 검색 트리(예: 레드-블랙 트리)를 사용해 요소를 정렬된 상태로 유지한다. O(log n) 시간에 연산을 수행하며, 정렬된 순회 가능.

       [Element2]
      /         \
[Element1]  [Element3]
        

3. 비트 집합(Bit Set)

비트 벡터를 사용해 정수 집합을 효율적으로 표현한다. 메모리 효율이 높다.

[Bit Vector]
[0 1 1 0 1 ...]  ← 1은 요소 존재, 0은 부재
        

본 포스팅에서는 해시 기반 집합과 트리 기반 집합을 중심으로 설명한다.

자바에서 해시 집합 구현

해시 집합은 해시 테이블을 기반으로 빠른 연산을 제공한다. 아래는 간단한 해시 집합의 자바 구현이다.

class HashSet {
    private int capacity;
    private Node[] buckets;
    private int size;
    
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    public HashSet(int capacity) {
        this.capacity = capacity;
        buckets = new Node[capacity];
        size = 0;
    }
    
    private int hash(int data) {
        return Math.abs(data % capacity);
    }
    
    // 요소 추가
    public boolean add(int data) {
        int index = hash(data);
        Node current = buckets[index];
        
        while (current != null) {
            if (current.data == data) return false;
            current = current.next;
        }
        
        Node newNode = new Node(data);
        newNode.next = buckets[index];
        buckets[index] = newNode;
        size++;
        return true;
    }
    
    // 요소 제거
    public boolean remove(int data) {
        int index = hash(data);
        Node current = buckets[index];
        Node prev = null;
        
        while (current != null) {
            if (current.data == data) {
                if (prev == null) {
                    buckets[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return true;
            }
            prev = current;
            current = current.next;
        }
        return false;
    }
    
    // 요소 존재 확인
    public boolean contains(int data) {
        int index = hash(data);
        Node current = buckets[index];
        
        while (current != null) {
            if (current.data == data) return true;
            current = current.next;
        }
        return false;
    }
    
    // 집합 크기
    public int size() {
        return size;
    }
    
    // 비어 있음 확인
    public boolean isEmpty() {
        return size == 0;
    }
}

이 코드는 해시 테이블 기반 집합으로, 추가, 제거, 포함 여부 확인 기능을 제공한다.

집합의 기본 연산

집합의 주요 연산은 다음과 같다:

1. 추가(Add)

집합에 요소를 추가한다. 이미 존재하면 추가하지 않는다.

public boolean add(int data) {
    int index = hash(data);
    Node current = buckets[index];
    
    while (current != null) {
        if (current.data == data) return false;
        current = current.next;
    }
    
    Node newNode = new Node(data);
    newNode.next = buckets[index];
    buckets[index] = newNode;
    size++;
    return true;
}

2. 제거(Remove)

집합에서 요소를 제거한다.

public boolean remove(int data) {
    int index = hash(data);
    Node current = buckets[index];
    Node prev = null;
    
    while (current != null) {
        if (current.data == data) {
            if (prev == null) {
                buckets[index] = current.next;
            } else {
                prev.next = current.next;
            }
            size--;
            return true;
        }
        prev = current;
        current = current.next;
    }
    return false;
}

3. 포함 여부 확인(Contains)

집합에 요소가 있는지 확인한다.

public boolean contains(int data) {
    int index = hash(data);
    Node current = buckets[index];
    
    while (current != null) {
        if (current.data == data)  high>return true;
        current = current.next;
    }
    return false;
}

4. 집합 연산

교집합, 합집합, 차집합 등은 두 집합을 비교해 수행한다.

public HashSet union(HashSet other) {
    HashSet result = new HashSet(capacity);
    for (Node bucket : buckets) {
        Node current = bucket;
        while (current != null) {
            result.add(current.data);
            current = current.next;
        }
    }
    for (Node bucket : other.buckets) {
        Node current = bucket;
        while (current != null) {
            result.add(current.data);
            current = current.next;
        }
    }
    return result;
}

집합의 시간 복잡도

해시 기반 집합의 주요 연산 시간 복잡도는 다음과 같다:

• 추가(Add): 평균 O(1), 최악 O(n)
• 제거(Remove): 평균 O(1), 최악 O(n)
• 포함 여부 확인(Contains): 평균 O(1), 최악 O(n)
• 집합 연산(Union, Intersection): O(n + m), n과 m은 두 집합의 크기

트리 기반 집합은 삽입, 삭제, 조회가 O(log n)이며, 정렬된 순회가 가능하다.

트리 기반 집합 구현

트리 기반 집합은 정렬된 상태를 유지하며, 자바의 TreeSet과 유사하다. 아래는 간단한 이진 검색 트리 기반 집합이다.

class TreeSet {
    private Node root;
    private int size;
    
    static class Node {
        int data;
        Node left, right;
        Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
    
    public TreeSet() {
        root = null;
        size = 0;
    }
    
    public boolean add(int data) {
        if (root == null) {
            root = new Node(data);
            size++;
            return true;
        }
        Node current = root, parent = null;
        while (current != null) {
            if (data == current.data) return false;
            parent = current;
            current = data < current.data ? current.left : current.right;
        }
        if (data < parent.data) parent.left = new Node(data);
        else parent.right = new Node(data);
        size++;
        return true;
    }
    
    public boolean contains(int data) {
        Node current = root;
        while (current != null) {
            if (data == current.data) return true;
            current = data < current.data ? current.left : current.right;
        }
        return false;
    }
    
    public int size() {
        return size;
    }
}

트리 기반 집합은 정렬된 순회를 지원하며, 균형 트리로 확장 가능하다.

집합을 활용한 알고리즘

집합은 중복 제거, 멤버십 테스트, 집합 연산에서 사용된다.

1. 중복 제거

배열에서 중복된 요소를 제거한다.

public int[] removeDuplicates(int[] nums) {
    HashSet set = new HashSet(nums.length);
    for (int num : nums) {
        set.add(num);
    }
    int[] result = new int[set.size()];
    int i = 0;
    for (Node bucket : set.buckets) {
        Node current = bucket;
        while (current != null) {
            result[i++] = current.data;
            current = current.next;
        }
    }
    return result;
}

2. 교집합 계산

두 배열의 공통 요소를 찾 교집합을 계산한다.

public int[] intersection(int[] nums1, int[] nums2) {
    HashSet set = new HashSet(nums1.length);
    for (int num : nums1) {
        set.add(num);
    }
    HashSet result = new HashSet(nums2.length);
    for (int num : nums2) {
        if (set.contains(num)) {
            result.add(num);
        }
    }
    int[] arr = new int[result.size()];
    int i = 0;
    for (Node bucket : result.buckets) {
        Node current = bucket;
        while (current != null) {
            arr[i++] = current.data;
            current = current.next;
        }
    }
    return arr;
}

3. 고유 요소 세기

배열에서 고유한 요소의 개수를 계산한다.

public int countUnique(int[] nums) {
    HashSet set = new HashSet(nums.length);
    for (int num : nums) {
        set.add(num);
    }
    return set.size();
}

심화 주제: 집합 최적화

집합을 효율적으로 사용하려면 몇 가지 기법을 고려한다.

1. 해시 충돌 최소화

해시 함수를 개선하고, 적절한 로드 팩터를 유지한다.

private int hash(int data) {
    int hash = data;
    hash ^= (hash >>> 20) ^ (hash >>> 12);
    return hash ^ (hash >>> 7) ^ (hash >>> 4);
}

2. 동적 크기 조정

해시 집합의 크기를 동적으로 확장한다.

private void resize() {
    if ((double)size / capacity < 0.75) return;
    Node[] oldBuckets = buckets;
    capacity *= 2;
    buckets = new Node[capacity];
    size = 0;
    for (Node bucket : oldBuckets) {
        Node current = bucket;
        while (current != null) {
            add(current.data);
            current = current.next;
        }
    }
}

3. 트리 기반 최적화

AVL 트리나 레드-블랙 트리를 사용해 균형을 유지한다.

집합의 한계와 대안

집합은 순서 정보가 없고, 중복을 허용하지 않는다. 자바에서는 java.util.HashSet와 java.util.TreeSet을 제공한다.

import java.util.HashSet;

HashSet<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.remove(1);

TreeSet은 정렬된 집합을 제공한다.

import java.util.TreeSet;

TreeSet<Integer> set = new TreeSet<>();
set.add(1);
set.add(2);
int first = set.first(); // 1

문제

집합을 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고, 자바 코드로 해답을 제공한다.

5
add 1
add 2
contains 1
remove 2
contains 2

YES
NO

import java.util.Scanner;

public class SetOperations {
    static class HashSet {
        private int capacity;
        private Node[] buckets;
        private int size;
        
        static class Node {
            int data;
            Node next;
            Node(int data) {
                this.data = data;
                this.next = null;
            }
        }
        
        HashSet(int capacity) {
            this.capacity = capacity;
            buckets = new Node[capacity];
            size = 0;
        }
        
        private int hash(int data) {
            return Math.abs(data % capacity);
        }
        
        boolean add(int data) {
            int index = hash(data);
            Node current = buckets[index];
            
            while (current != null) {
                if (current.data == data) return false;
                current = current.next;
            }
            
            Node newNode = new Node(data);
            newNode.next = buckets[index];
            buckets[index] = newNode;
            size++;
            return true;
        }
        
        boolean remove(int data) {
            int index = hash(data);
            Node current = buckets[index];
            Node prev = null;
            
            while (current != null) {
                if (current.data == data) {
                    if (prev == null) {
                        buckets[index] = current.next;
                    } else {
                        prev.next = current.next;
                    }
                    size--;
                    return true;
                }
                prev = current;
                current = current.next;
            }
            return false;
        }
        
        boolean contains(int data) {
            int index = hash(data);
            Node current = buckets[index];
            
            while (current != null) {
                if (current.data == data) return true;
                current = current.next;
            }
            return false;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashSet set = new HashSet(N);
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            String[] parts = operation.split(" ");
            int x = Integer.parseInt(parts[1]);
            if (parts[0].equals("add")) {
                set.add(x);
            } else if (parts[0].equals("remove")) {
                set.remove(x);
            } else {
                System.out.println(set.contains(x) ? "YES" : "NO");
            }
        }
        sc.close();
    }
}

6
1 2 2 3 3 3

3

import java.util.Scanner;

public class CountUnique {
    static class HashSet {
        private int capacity;
        private Node[] buckets;
        private int size;
        
        static class Node {
            int data;
            Node next;
            Node(int data) {
                this.data = data;
                this.next = null;
            }
        }
        
        HashSet(int capacity) {
            this.capacity = capacity;
            buckets = new Node[capacity];
            size = 0;
        }
        
        private int hash(int data) {
            return Math.abs(data % capacity);
        }
        
        boolean add(int data) {
            int index = hash(data);
            Node current = buckets[index];
            
            while (current != null) {
                if (current.data == data) return false;
                current = current.next;
            }
            
            Node newNode = new Node(data);
            newNode.next = buckets[index];
            buckets[index] = newNode;
            size++;
            return true;
        }
        
        int size() {
            return size;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashSet set = new HashSet(N);
        
        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            set.add(num);
        }
        
        System.out.println(set.size());
        sc.close();
    }
}

4 3
1 2 3 4
2 3 5

2 3

import java.util.Scanner;

public class Intersection {
    static class HashSet {
        private int capacity;
        private Node[] buckets;
        private int size;
        
        static class Node {
            int data;
            Node next;
            Node(int data) {
                this.data = data;
                this.next = null;
            }
        }
        
        HashSet(int capacity) {
            this.capacity = capacity;
            buckets = new Node[capacity];
            size = 0;
        }
        
        private int hash(int data) {
            return Math.abs(data % capacity);
        }
        
        boolean add(int data) {
            int index = hash(data);
            Node current = buckets[index];
            
            while (current != null) {
                if (current.data == data) return false;
                current = current.next;
            }
            
            Node newNode = new Node(data);
            newNode.next = buckets[index];
            buckets[index] = newNode;
            size++;
            return true;
        }
        
        boolean contains(int data) {
            int index = hash(data);
            Node current = buckets[index];
            
            while (current != null) {
                if (current.data == data) return true;
                current = current.next;
            }
            return false;
        }
        
        int size() {
            return size;
        }
        
        int[] toArray() {
            int[] result = new int[size];
            int i = 0;
            for (Node bucket : buckets) {
                Node current = bucket;
                while (current != null) {
                    result[i++] = current.data;
                    current = current.next;
                }
            }
            return result;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        HashSet set = new HashSet(N);
        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            set.add(num);
        }
        
        HashSet result = new HashSet(M);
        for (int i = 0; i < M; i++) {
            int num = sc.nextInt();
            if (set.contains(num)) {
                result.add(num);
            }
        }
        
        int[] intersection = result.toArray();
        for (int i = 0; i < intersection.length; i++) {
            System.out.print(intersection[i]);
            if (i < intersection.length - 1) {
                System.out.print(" ");
            }
        }
        System.out.println();
        sc.close();
    }
}

마무리

집합은 프로그래밍에서 중복 제거, 멤버십 테스트, 집합 연산을 효율적으로 수행하는 강력한 자료구조이다. 자바에서 HashSet은 빠른 연산을, TreeSet은 정렬된 순회를 제공한다. 본 포스팅에서 다룬 구현과 알고리즘을 통해 집합의 동작 원리를 이해하고, 실제 문제 해결에 적용할 수 있다.

집합은 단순하지만 강력하다. 중복을 제거하거나 공통 요소를 찾는 문제를 풀 때, 집합을 떠올리자. 연습 문제들을 풀어보며 집합의 활용법을 익히고, 더 복잡한 문제에 도전해보자.

궁금한 점이나 추가로 알고 싶은 주제가 있다면 언제든 질문하자. 집합을 마스터하면 데이터 처리와 알고리즘 풀이가 한결 수월해진다!

해시 테이블 (Hash Table)

프로그래밍에서 해시 테이블(Hash Table)은 키-값 쌍을 저장하고 빠르게 검색할 수 있는 자료구조이다. 해시 함수(Hash Function)를 사용해 키를 배열 인덱스로 변환하며, 평균적으로 O(1) 시간에 삽입, 삭제, 검색을 수행한다. 해시 테이블은 캐시, 데이터베이스 인덱싱, 집합 연산 등에서 널리 사용된다. 이 포스팅은 해시 테이블의 기본 개념부터 자바 구현, 충돌 처리, 심화 주제, 활용 사례까지 다룬다.

해시 테이블을 이해하면 데이터를 효율적으로 관리하고 복잡한 문제를 빠르게 해결할 수 있다. 하나씩 살펴보자.

해시 테이블의 정의와 특징

해시 테이블은 키-값 쌍을 저장하는 자료구조로, 키를 해시 함수에 입력해 얻은 해시 값을 배열 인덱스로 사용한다. 이를 통해 특정 키에 대응하는 값을 빠르게 찾는다. 해시 테이블의 핵심 구성 요소는 해시 함수, 배열, 충돌 처리 메커니즘이다.

해시 테이블의 장점은 다음과 같다:

• 빠른 연산: 평균적으로 삽입, 삭제, 검색이 O(1) 시간에 수행된다.
• 유연한 키 사용: 문자열, 정수 등 다양한 키를 사용할 수 있다.
• 광범위한 활용: 데이터 조회, 캐싱, 집합 연산 등에 유용하다.

단점은 다음과 같다:

• 충돌 가능성: 서로 다른 키가 동일한 해시 값을 가질 수 있다.
• 메모리 사용: 배열 크기가 클 경우 메모리 효율이 낮아질 수 있다.
• 순서 보장 없음: 데이터의 입력 순서나 정렬 순서를 유지하지 않는다.

해시 테이블의 동작 원리

해시 테이블은 다음과 같은 과정을 거쳐 동작한다:

1. 해시 함수 적용: 키를 해시 함수에 입력해 해시 값을 계산한다. 예: hash(key) % tableSize.
2. 인덱스 매핑: 해시 값을 배열 크기로 나눈 나머지를 인덱스로 사용한다.
3. 데이터 저장/검색: 해당 인덱스에 키-값 쌍을 저장하거나 값을 검색한다.
4. 충돌 처리: 동일 인덱스에 여러 키가 매핑되면 충돌을 해결한다.

아래는 해시 테이블의 구조를 도식화한 그림이다:

[0] → [key1:value1]
[1] → [key2:value2] → [key3:value3]
[2] → [ ]
[3] → [key4:value4]
        

해시 함수

해시 함수는 키를 고정된 크기의 해시 값으로 변환하는 함수이다. 좋은 해시 함수는 다음 조건을 만족한다:

• 균일성: 키를 고르게 분포시켜 충돌을 최소화한다.
• 효율성: 계산이 빠르다.
• 결정적: 동일한 키에 대해 항상 동일한 해시 값을 반환한다.

일반적인 해시 함수 예시는 다음과 같다:

• 나머지 연산: hash(key) = key % tableSize (정수 키).
• 문자열 해시: 문자열의 각 문자를 ASCII 값으로 변환 후 결합. 예: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1].
• 중간 제곱: 키를 제곱한 후 중간 비트를 사용.

충돌 처리

충돌은 서로 다른 키가 동일한 해시 값을 가질 때 발생한다. 주요 충돌 처리 기법은 다음과 같다:

1. 개별 체이닝(Separate Chaining)

각 배열 인덱스에 연결 리스트를 두어 동일 인덱스의 키-값 쌍을 저장한다.

[0] → [key1:value1] → [key5:value5]
[1] → [key2:value2]
[2] → [ ]
        

2. 오픈 어드레싱(Open Addressing)

충돌 시 다른 빈 슬롯을 찾아 데이터를 저장한다. 탐사 기법에는 선형 탐사, 이차 탐사, 이중 해싱 등이 있다.

[0] → [key1:value1]
[1] → [key2:value2]
[2] → [key3:value3]
        

3. 이중 해싱(Double Hashing)

두 번째 해시 함수를 사용해 충돌 시 이동 간격을 계산한다.

자바에서 해시 테이블 구현 (개별 체이닝)

개별 체이닝을 사용한 해시 테이블을 자바로 구현한다.

class HashTable {
    static class Node {
        String key;
        Integer value;
        Node next;
        Node(String key, Integer value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    
    private Node[] table;
    private int size;
    private int capacity;
    
    public HashTable(int capacity) {
        this.capacity = capacity;
        table = new Node[capacity];
        size = 0;
    }
    
    private int hash(String key) {
        int hash = 0;
        for (char c : key.toCharArray()) {
            hash = hash * 31 + c;
        }
        return Math.abs(hash) % capacity;
    }
    
    public void put(String key, Integer value) {
        int index = hash(key);
        Node current = table[index];
        
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            current = current.next;
        }
        
        Node newNode = new Node(key, value);
        newNode.next = table[index];
        table[index] = newNode;
        size++;
        
        if ((double)size / capacity > 0.75) {
            resize();
        }
    }
    
    public Integer get(String key) {
        int index = hash(key);
        Node current = table[index];
        
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }
    
    public Integer remove(String key) {
        int index = hash(key);
        Node current = table[index];
        Node prev = null;
        
        while (current != null) {
            if (current.key.equals(key)) {
                if (prev == null) {
                    table[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return current.value;
            }
            prev = current;
            current = current.next;
        }
        return null;
    }
    
    private void resize() {
        Node[] oldTable = table;
        capacity *= 2;
        table = new Node[capacity];
        size = 0;
        
        for (Node head : oldTable) {
            Node current = head;
            while (current != null) {
                put(current.key, current.value);
                current = current.next;
            }
        }
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size() {
        return size;
    }
}

이 구현은 문자열 키와 정수 값을 저장하며, 개별 체이닝으로 충돌을 처리한다. 로드 팩터가 0.75를 초과하면 테이블 크기를 두 배로 늘린다.

해시 테이블의 기본 연산

해시 테이블의 주요 연산은 다음과 같다:

1. 삽입(Put)

키-값 쌍을 해시 테이블에 추가한다.

public void put(String key, Integer value) {
    int index = hash(key);
    Node current = table[index];
    
    while (current != null) {
        if (current.key.equals(key)) {
            current.value = value;
            return;
        }
        current = current.next;
    }
    
    Node newNode = new Node(key, value);
    newNode.next = table[index];
    table[index] = newNode;
    size++;
}

2. 검색(Get)

키에 대응하는 값을 반환한다.

public Integer get(String key) {
    int index = hash(key);
    Node current = table[index];
    
    while (current != null) {
        if (current.key.equals(key)) {
            return current.value;
        }
        current = current.next;
    }
    return null;
}

3. 삭제(Remove)

키에 대응하는 키-값 쌍을 제거한다.

public Integer remove(String key) {
    int index = hash(key);
    Node current = table[index];
    Node prev = null;
    
    while (current != null) {
        if (current.key.equals(key)) {
            if (prev == null) {
                table[index] = current.next;
            } else {
                prev.next = current.next;
            }
            size--;
            return current.value;
        }
        prev = current;
        current = current.next;
    }
    return null;
}

시간 복잡도

해시 테이블의 연산 시간 복잡도는 충돌 처리 방식에 따라 달라진다:

• 개별 체이닝:
  • 평균: 삽입, 삭제, 검색이 O(1).
  • 최악: 충돌이 많으면 O(n) (연결 리스트 길이).
• 오픈 어드레싱:
  • 평균: O(1).
  • 최악: O(n) (클러스터링).

로드 팩터(데이터 수 / 테이블 크기)가 낮을수록 충돌이 적어 평균 성능이 향상된다.

오픈 어드레싱 구현 (선형 탐사)

오픈 어드레싱 중 선형 탐사를 사용한 해시 테이블을 구현한다.

class LinearProbeHashTable {
    static class Entry {
        String key;
        Integer value;
        boolean isDeleted;
        Entry(String key, Integer value) {
            this.key = key;
            this.value = value;
            this.isDeleted = false;
        }
    }
    
    private Entry[] table;
    private int size;
    private int capacity;
    
    public LinearProbeHashTable(int capacity) {
        this.capacity = capacity;
        table = new Entry[capacity];
        size = 0;
    }
    
    private int hash(String key) {
        int hash = 0;
        for (char c : key.toCharArray()) {
            hash = hash * 31 + c;
        }
        return Math.abs(hash) % capacity;
    }
    
    public void put(String key, Integer value) {
        if ((double)size / capacity > 0.75) {
            resize();
        }
        
        int index = hash(key);
        int i = 0;
        
        while (true) {
            int probe = (index + i) % capacity;
            if (table[probe] == null || table[probe].isDeleted) {
                table[probe] = new Entry(key, value);
                size++;
                return;
            } else if (table[probe].key.equals(key)) {
                table[probe].value = value;
                return;
            }
            i++;
        }
    }
    
    public Integer get(String key) {
        int index = hash(key);
        int i = 0;
        
        while (true) {
            int probe = (index + i) % capacity;
            if (table[probe] == null) {
                return null;
            } else if (!table[probe].isDeleted && table[probe].key.equals(key)) {
                return table[probe].value;
            }
            i++;
            if (i == capacity) return null;
        }
    }
    
    public Integer remove(String key) {
        int index = hash(key);
        int i = 0;
        
        while (true) {
            int probe = (index + i) % capacity;
            if (table[probe] == null) {
                return null;
            } else if (!table[probe].isDeleted && table[probe].key.equals(key)) {
                Integer value = table[probe].value;
                table[probe].isDeleted = true;
                size--;
                return value;
            }
            i++;
            if (i == capacity) return null;
        }
    }
    
    private void resize() {
        Entry[] oldTable = table;
        capacity *= 2;
        table = new Entry[capacity];
        size = 0;
        
        for (Entry entry : oldTable) {
            if (entry != null && !entry.isDeleted) {
                put(entry.key, entry.value);
            }
        }
    }
}

선형 탐사는 간단하지만 클러스터링(연속된 슬롯 점유) 문제가 발생할 수 있다.

해시 테이블을 활용한 알고리즘

해시 테이블은 다양한 알고리즘에서 사용된다.

1. 빈도 계산

배열의 각 원소 빈도를 계산한다.

import java.util.HashMap;

public int[] frequencyCount(int[] nums) {
    HashMap<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    int[] result = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        result[i] = freq.getOrDefault(nums[i], 0);
    }
    return result;
}

2. 두 수의 합

배열에서 합이 목표 값이 되는 두 수의 인덱스를 찾는다.

import java.util.HashMap;

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}

3. 중복 문자 없는 가장 긴 부분 문자열

문자열에서 중복 문자가 없는 가장 긴 부분 문자열의 길이를 찾는다.

import java.util.HashMap;

public int lengthOfLongestSubstring(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    int maxLen = 0, start = 0;
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c) && map.get(c) >= start) {
            start = map.get(c) + 1;
        }
        map.put(c, i);
        maxLen = Math.max(maxLen, i - start + 1);
    }
    return maxLen;
}

심화 주제: 해시 테이블 최적화

해시 테이블의 성능을 높이기 위한 기법은 다음과 같다:

1. 로드 팩터 관리

로드 팩터가 높아지면 충돌이 증가하므로, 적절히 테이블 크기를 조정한다.

2. 고품질 해시 함수

충돌을 최소화하는 해시 함수를 선택한다. 예: MurmurHash, FNV-1a.

3. 캐시 친화적 설계

개별 체이닝 대신 오픈 어드레싱을 사용해 메모리 지역성을 높인다.

4. 병렬 처리

다중 스레드 환경에서 ConcurrentHashMap과 같은 동시성 지원 자료구조를 사용한다.

해시 테이블의 한계와 대안

해시 테이블은 순서 보장이 없고, 최악의 경우 O(n) 성능을 보인다. 자바에서는 HashMap, HashSet, ConcurrentHashMap 등을 제공한다.

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
Integer value = map.get("key1"); // 1

TreeMap은 키를 정렬된 순서로 유지하며, LinkedHashMap은 삽입 순서를 보존한다.

문제

해시 테이블을 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고, 자바 코드로 해답을 제공한다.

5
put apple 10
put banana 20
get apple
put apple 30
get banana

10
20

import java.util.Scanner;

public class KeyValueStore {
    static class HashTable {
        static class Node {
            String key;
            Integer value;
            Node next;
            Node(String key, Integer value) {
                this.key = key;
                this.value = value;
                this.next = null;
            }
        }
        
        private Node[] table;
        private int capacity;
        
        HashTable(int capacity) {
            this.capacity = capacity;
            table = new Node[capacity];
        }
        
        private int hash(String key) {
            int hash = 0;
            for (char c : key.toCharArray()) {
                hash = hash * 31 + c;
            }
            return Math.abs(hash) % capacity;
        }
        
        void put(String key, Integer value) {
            int index = hash(key);
            Node current = table[index];
            
            while (current != null) {
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            
            Node newNode = new Node(key, value);
            newNode.next = table[index];
            table[index] = newNode;
        }
        
        Integer get(String key) {
            int index = hash(key);
            Node current = table[index];
            
            while (current != null) {
                if (current.key.equals(key)) {
                    return current.value;
                }
                current = current.next;
            }
            return -1;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        HashTable ht = new HashTable(N);
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            String[] parts = operation.split(" ");
            if (parts[0].equals("put")) {
                String key = parts[1];
                int value = Integer.parseInt(parts[2]);
                ht.put(key, value);
            } else {
                String key = parts[1];
                System.out.println(ht.get(key));
            }
        }
        sc.close();
    }
}

5
1 2 1 3 2

2 2 2 1 0

import java.util.Scanner;
import java.util.HashMap;

public class FrequencyCount {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];
        
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        for (int i = 0; i < N; i++) {
            System.out.print(freq.getOrDefault(nums[i], 0) + " ");
        }
        System.out.println();
        sc.close();
    }
}

4 9
2 7 11 15
            

0 1
            

import java.util.Scanner;
import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int target = sc.nextInt();
        int[] nums = new int[N];
        
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                System.out.println(map.get(complement) + " " + i);
                sc.close();
                return;
            }
            map.put(nums[i], i);
        }
        
        System.out.println("-1 -1");
        sc.close();
    }
}

실제 활용 사례

해시 테이블은 다양한 실제 시나리오에서 사용된다:

• 캐싱: 웹 서버에서 자주 요청되는 데이터를 캐시에 저장해 응답 시간을 단축한다.
• 데이터베이스 인덱싱: 데이터베이스에서 키를 빠르게 검색하기 위해 해시 인덱스를 사용한다.
• 집합 연산: 두 집합의 교집합, 합집합 등을 효율적으로 계산한다.
• 빈도 테이블: 데이터 스트림에서 각 요소의 빈도를 실시간으로 계산한다.

결론

해시 테이블은 빠른 데이터 검색과 삽입을 가능하게 하는 강력한 자료구조이다. 해시 함수와 충돌 처리 기법을 이해하면 효율적인 구현이 가능하다. 자바의 HashMap과 같은 표준 라이브러리를 사용할 수도 있지만, 내부 동작을 이해하면 더 나은 최적화와 문제 해결이 가능하다.

이 문서에서는 해시 테이블의 활용 사례와 실제 문제를 풀어보며 해시 테이블의 유용성을 살펴보았다. 연습 문제와 코드를 통해 개념을 심화하고, 실제 코딩 테스트나 프로젝트에 적용해보길 바란다.

참고 자료

• Wikipedia: Hash Table
• Java HashMap Documentation
• LeetCode: Two Sum
• Cormen, Thomas H. et al. Introduction to Algorithms, 3rd Edition.

덱 (Deque)

프로그래밍에서 덱(Deque)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다. Double-Ended Queue의 약자로, 큐와 스택의 기능을 모두 포함한다. 덱은 슬라이딩 윈도우, 회전 큐, 작업 스케줄링 등 다양한 상황에서 활용된다. 덱의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.

덱을 이해하면 양방향 데이터 처리가 가능해지고 복잡한 문제를 효율적으로 해결할 수 있다.

덱의 정의와 특징

덱은 양쪽 끝에서 데이터를 추가하고 제거할 수 있는 자료구조이다. 앞쪽 끝을 프론트(front), 뒤쪽 끝을 리어(rear)라고 부른다. 큐처럼 FIFO(First In, First Out) 방식으로 동작하거나, 스택처럼 LIFO(Last In, First Out) 방식으로 동작할 수 있다.

덱의 장점은 다음과 같다:

• 양방향 접근: 프론트와 리어에서 삽입과 삭제가 가능하다.
• 유연성: 큐와 스택의 기능을 모두 제공한다.
• 빠른 연산: 대부분의 연산이 O(1) 시간에 수행된다.

단점은 다음과 같다:

• 제한된 접근: 중간 요소에 직접 접근할 수 없다.
• 고정 크기 배열 사용 시 제한: 동적 크기 조정이 필요하다.
• 비연속적 메모리: 연결 리스트 기반 덱은 캐시 활용도가 낮다.

덱의 종류

덱은 구현 방식에 따라 두 가지로 나뉜다.

1. 배열 기반 덱(Array-based Deque)

고정 크기 배열을 사용한다. 메모리 효율이 높지만 크기 제한이 있다.

[Front] [1] [2] [3] [Rear]
        ↑           ↑
       Front       Rear
        

2. 연결 리스트 기반 덱(Linked List-based Deque)

이중 연결 리스트를 사용해 동적으로 크기를 조정한다.

[Front] ↔ [Node|data:1] ↔ [Node|data:2] ↔ [Node|data:3] ↔ [Rear]
        

배열 기반 덱과 연결 리스트 기반 덱을 중심으로 설명한다.

자바에서 덱 구현

덱은 배열과 연결 리스트로 구현할 수 있다. 두 가지 방법을 아래에 제시한다.

배열 기반 덱 구현

원형 배열을 사용해 공간을 효율적으로 관리한다.

class ArrayDeque {
    private int[] arr;
    private int front;
    private int rear;
    private int capacity;
    private int size;

    public ArrayDeque(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    // 앞에 삽입
    public void addFront(int data) {
        if (size == capacity) {
            System.out.println("Deque is Full");
            return;
        }
        front = (front - 1 + capacity) % capacity;
        arr[front] = data;
        if (size == 0) rear = front;
        size++;
    }

    // 뒤에 삽입
    public void addRear(int data) {
        if (size == capacity) {
            System.out.println("Deque is Full");
            return;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = data;
        if (size == 0) front = rear;
        size++;
    }

    // 앞에서 삭제
    public int removeFront() {
        if (size == 0) {
            System.out.println("Deque is Empty");
            return -1;
        }
        int data = arr[front];
        front = (front + 1) % capacity;
        size--;
        return data;
    }

    // 뒤에서 삭제
    public int removeRear() {
        if (size == 0) {
            System.out.println("Deque is Empty");
            return -1;
        }
        int data = arr[rear];
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return data;
    }

    // 앞 데이터 조회
    public int peekFront() {
        if (size == 0) {
            System.out.println("Deque is Empty");
            return -1;
        }
        return arr[front];
    }

    // 뒤 데이터 조회
    public int peekRear() {
        if (size == 0) {
            System.out.println("Deque is Empty");
            return -1;
        }
        return arr[rear];
    }

    // 비어 있는지 확인
    public boolean isEmpty() {
        return size == 0;
    }
}

연결 리스트 기반 덱 구현

이중 연결 리스트를 사용해 동적 크기 조정이 가능하다.

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

    private Node front;
    private Node rear;
    private int size;

    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }

    // 앞에 삽입
    public void addFront(int data) {
        Node newNode = new Node(data);
        if (front == null) {
            front = rear = newNode;
        } else {
            newNode.next = front;
            front.prev = newNode;
            front = newNode;
        }
        size++;
    }

    // 뒤에 삽입
    public void addRear(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
        } else {
            newNode.prev = rear;
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 앞에서 삭제
    public int removeFront() {
        if (front == null) {
            System.out.println("Deque is Empty");
            return -1;
        }
        int data = front.data;
        front = front.next;
        if (front == null) rear = null;
        else front.prev = null;
        size--;
        return data;
    }

    // 뒤에서 삭제
    public int removeRear() {
        if (rear == null) {
            System.out.println("Deque is Empty");
            return -1;
        }
        int data = rear.data;
        rear = rear.prev;
        if (rear == null) front = null;
        else rear.next = null;
        size--;
        return data;
    }

    // 앞 데이터 조회
    public int peekFront() {
        if (front == null) {
            System.out.println("Deque is Empty");
            return -1;
        }
        return front.data;
    }

    // 뒤 데이터 조회
    public int peekRear() {
        if (rear == null) {
            System.out.println("Deque is Empty");
            return -1;
        }
        return rear.data;
    }

    // 비어 있는지 확인
    public boolean isEmpty() {
        return size == 0;
    }
}

덱의 기본 연산

덱의 주요 연산은 다음과 같다:

1. 앞에 삽입(addFront)

덱의 프론트에 데이터를 추가한다.

public void addFront(int data) {
    if (size == capacity) {
        System.out.println("Deque is Full");
        return;
    }
    front = (front - 1 + capacity) % capacity;
    arr[front] = data;
    if (size == 0) rear = front;
    size++;
}

2. 뒤에 삽입(addRear)

덱의 리어에 데이터를 추가한다.

public void addRear(int data) {
    if (size == capacity) {
        System.out.println("Deque is Full");
        return;
    }
    rear = (rear + 1) % capacity;
    arr[rear] = data;
    if (size == 0) front = rear;
    size++;
}

3. 앞에서 삭제(removeFront)

덱의 프론트에서 데이터를 제거하고 반환한다.

public int removeFront() {
    if (size == 0) {
        System.out.println("Deque is Empty");
        return -1;
    }
    int data = arr[front];
    front = (front + 1) % capacity;
    size--;
    return data;
}

4. 뒤에서 삭제(removeRear)

덱의 리어에서 데이터를 제거하고 반환한다.

public int removeRear() {
    if (size == 0) {
        System.out.println("Deque is Empty");
        return -1;
    }
    int data = arr[rear];
    rear = (rear - 1 + capacity) % capacity;
    size--;
    return data;
}

5. 앞 데이터 조회(peekFront)

덱의 프론트 데이터를 제거하지 않고 반환한다.

public int peekFront() {
    if (size == 0) {
        System.out.println("Deque is Empty");
        return -1;
    }
    return arr[front];
}

6. 뒤 데이터 조회(peekRear)

덱의 리어 데이터를 제거하지 않고 반환한다.

public int peekRear() {
    if (size == 0) {
        System.out.println("Deque is Empty");
        return -1;
    }
    return arr[rear];
}

7. 비어 있음 확인(isEmpty)

덱이 비어 있는지 확인한다.

public boolean isEmpty() {
    return size == 0;
}

덱의 시간 복잡도

덱의 주요 연산의 시간 복잡도는 다음과 같다:

• 앞에 삽입(addFront): O(1)
• 뒤에 삽입(addRear): O(1)
• 앞에서 삭제(removeFront): O(1)
• 뒤에서 삭제(removeRear): O(1)
• 앞 데이터 조회(peekFront): O(1)
• 뒤 데이터 조회(peekRear): O(1)
• 비어 있음 확인(isEmpty): O(1)

연결 리스트 기반 덱도 동일한 시간 복잡도를 가지지만, 노드 생성/삭제 비용이 추가된다.

덱을 활용한 알고리즘

덱은 슬라이딩 윈도우, 회전 큐 등에서 사용된다.

슬라이딩 윈도우

고정 크기의 윈도우를 이동하며 윈도우 내 최대값이나 최소값을 찾는다.

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    LinkedDeque deque = new LinkedDeque();

    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peekFront() < i - k + 1) {
            deque.removeFront();
        }
        while (!deque.isEmpty() && nums[deque.peekRear()] < nums[i]) {
            deque.removeRear();
        }
        deque.addRear(i);
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFront()];
        }
    }
    return result;
}

회전 큐

덱의 요소를 회전시킨다.

public void rotateDeque(LinkedDeque deque, int k) {
    for (int i = 0; i < k; i++) {
        int front = deque.removeFront();
        deque.addRear(front);
    }
}

심화 주제: 덱 최적화

덱의 성능을 향상시키는 기법을 다룬다.

동적 배열 사용

배열 기반 덱에서 크기를 동적으로 조정한다.

public void addFront(int data) {
    if (size == capacity) {
        resize();
    }
    front = (front - 1 + capacity) % capacity;
    arr[front] = data;
    size++;
}

private void resize() {
    int newCapacity = capacity * 2;
    int[] newArr = new int[newCapacity];
    for (int i = 0; i < size; i++) {
        newArr[i] = arr[(front + i) % capacity];
    }
    arr = newArr;
    front = 0;
    rear = size - 1;
    capacity = newCapacity;
}

메모리 관리

연결 리스트 기반 덱에서 노드 재사용을 고려할 수 있다. 자바에서는 가비지 컬렉터가 이를 처리한다.

덱의 한계와 대안

덱은 중간 요소 접근이 불가능하다. 자바에서는 ArrayDeque와 LinkedList를 제공한다.

import java.util.ArrayDeque;

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
int front = deque.removeFirst(); // 1
int rear = deque.removeLast(); // 2