집합 (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

ArrayDeque는 성능이 우수하며, LinkedList는 동적 크기 조정이 가능하다.

문제

덱을 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시한다.

5
addFront 1
addRear 2
removeFront
addRear 3
removeRear

1
3

import java.util.Scanner;

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

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

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

        void addRear(int data) {
            if (size == capacity) return;
            rear = (rear + 1) % capacity;
            arr[rear] = data;
            if (size == 0) front = rear;
            size++;
        }

        int removeFront() {
            if (size == 0) return -1;
            int data = arr[front];
            front = (front + 1) % capacity;
            size--;
            return data;
        }

        int removeRear() {
            if (size == 0) return -1;
            int data = arr[rear];
            rear = (rear - 1 + capacity) % capacity;
            size--;
            return data;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        ArrayDeque deque = new ArrayDeque(N);
        sc.nextLine();

        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            if (operation.startsWith("addFront")) {
                int x = Integer.parseInt(operation.split(" ")[1]);
                deque.addFront(x);
            } else if (operation.startsWith("addRear")) {
                int x = Integer.parseInt(operation.split(" ")[1]);
                deque.addRear(x);
            } else if (operation.equals("removeFront")) {
                System.out.println(deque.removeFront());
            } else if (operation.equals("removeRear")) {
                System.out.println(deque.removeRear());
            }
        }
        sc.close();
    }
}

8 3
1 3 -1 -3 5 3 6 7

3 3 5 5 6 7

import java.util.Scanner;

public class SlidingWindowMax {
    static 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;

        LinkedDeque() {
            front = null;
            rear = null;
        }

        void addRear(int data) {
            Node newNode = new Node(data);
            if (rear == null) {
                front = rear = newNode;
            } else {
                newNode.prev = rear;
                rear.next = newNode;
                rear = newNode;
            }
        }

        int removeFront() {
            if (front == null) return -1;
            int data = front.data;
            front = front.next;
            if (front == null) rear = null;
            else front.prev = null;
            return data;
        }

        int removeRear() {
            if (rear == null) return -1;
            int data = rear.data;
            rear = rear.prev;
            if (rear == null) front = null;
            else rear.next = null;
            return data;
        }

        int peekFront() {
            if (front == null) return -1;
            return front.data;
        }

        int peekRear() {
            if (rear == null) return -1;
            return rear.data;
        }

        boolean isEmpty() {
            return front == null;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }

        int[] result = new int[N - k + 1];
        LinkedDeque deque = new LinkedDeque();

        for (int i = 0; i < N; 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()];
            }
        }

        for (int max : result) {
            System.out.print(max + " ");
        }
        System.out.println();
        sc.close();
    }
}

5 2
1 2 3 4 5
left
right

1 2 3 4 5

import java.util.Scanner;

public class RotateDeque {
    static 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;

        LinkedDeque() {
            front = null;
            rear = null;
        }

        void addRear(int data) {
            Node newNode = new Node(data);
            if (rear == null) {
                front = rear = newNode;
            } else {
                newNode.prev = rear;
                rear.next = newNode;
                rear = newNode;
            }
        }

        int removeFront() {
            if (front == null) return -1;
            int data = front.data;
            front = front.next;
            if (front == null) rear = null;
            else front.prev = null;
            return data;
        }

        int removeRear() {
            if (rear == null) return -1;
            int data = rear.data;
            rear = rear.prev;
            if (rear == null) front = null;
            else rear.next = null;
            return data;
        }

        void addFront(int data) {
            Node newNode = new Node(data);
            if (front == null) {
                front = rear = newNode;
            } else {
                newNode.next = front;
                front.prev = newNode;
                front = newNode;
            }
        }

        boolean isEmpty() {
            return front == null;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        LinkedDeque deque = new LinkedDeque();
        for (int i = 0; i < N; i++) {
            deque.addRear(sc.nextInt());
        }
        sc.nextLine();

        for (int i = 0; i < M; i++) {
            String operation = sc.nextLine();
            if (operation.equals("left")) {
                int front = deque.removeFront();
                deque.addRear(front);
            } else if (operation.equals("right")) {
                int rear = deque.removeRear();
                deque.addFront(rear);
            }
        }

        while (!deque.isEmpty()) {
            System.out.print(deque.removeFront() + " ");
        }
        System.out.println();
        sc.close();
    }
}

마무리

덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 큐와 스택의 기능을 모두 제공한다. 배열 기반과 연결 리스트 기반의 구현, 기본 연산, 시간 복잡도, 활용 알고리즘, 최적화 기법을 다뤘다. 자바의 ArrayDeque와 LinkedList를 통해 대안을 살펴봤다.

큐 (Queue)

프로그래밍에서 큐(Queue)는 데이터를 순서대로 처리하는 자료구조로, FIFO(First In, First Out) 방식으로 동작한다. 즉, 먼저 추가된 데이터가 가장 먼저 제거된다. 큐는 작업 스케줄링, BFS(너비 우선 탐색), 대기열 관리 등에서 사용된다. 이번 포스팅은 큐의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.

큐를 이해하면 데이터를 순차적으로 처리하고 복잡한 문제를 효율적으로 해결할 수 있다. 하나씩 알아보자.

큐의 정의와 특징

큐는 데이터를 한쪽 끝에서 추가하고 반대쪽 끝에서 제거하는 자료구조이다. 데이터를 추가하는 연산을 인큐(enqueue), 제거하는 연산을 디큐(dequeue)라고 한다. 큐의 앞쪽은 프론트(front), 뒤쪽은 리어(rear)라 부른다.

큐의 장점은 다음과 같다:

• 순차 처리: FIFO 방식으로 데이터 처리 순서를 보장한다.
• 빠른 연산: 인큐와 디큐가 O(1) 시간에 수행된다.
• 다양한 활용: 작업 대기열, BFS, 캐시 구현 등에 유용하다.

단점은 다음과 같다:

• 제한된 접근: 프론트와 리어만 접근 가능하며, 중간 데이터 접근은 불가능하다.
• 고정 크기 배열 사용 시 제한: 동적 크기 조정이 필요하다.
• 비연속적 메모리: 연결 리스트 기반 구현 시 캐시 활용도가 낮다.

큐의 종류

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

1. 배열 기반 큐(Array-based Queue)

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

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

2. 연결 리스트 기반 큐(Linked List-based Queue)

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

[Front] → [Node|data:1|next] → [Node|data:2|next] → [Node|data:3|null]
        

3. 원형 큐(Circular Queue)

배열의 끝과 처음을 연결해 공간을 효율적으로 사용한다.

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

이 포스팅에서는 배열 기반 큐와 원형 큐를 중심으로 설명하며, 필요 시 연결 리스트 기반을 다룬다.

자바에서 원형 큐 구현

원형 큐는 배열 기반 큐의 공간 낭비를 줄인다. 아래는 원형 큐의 자바 구현이다.

class CircularQueue {
    private int[] arr;
    private int front;
    private int rear;
    private int capacity;
    private int size;
    
    public CircularQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        size = 0;
    }
    
    // 인큐: 큐에 데이터 추가
    public void enqueue(int data) {
        if (size == capacity) {
            System.out.println("Queue is Full");
            return;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = data;
        size++;
    }
    
    // 디큐: 큐에서 데이터 제거
    public int dequeue() {
        if (size == 0) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int data = arr[front];
        front = (front + 1) % capacity;
        size--;
        return data;
    }
    
    // 프론트 데이터 확인
    public int peek() {
        if (size == 0) {
            System.out.println("Queue is Empty");
            return -1;
        }
        return arr[front];
    }
    
    // 비어 있는지 확인
    public boolean isEmpty() {
        return size == 0;
    }
}

이 코드는 원형 큐로, 인큐, 디큐, 피크, 비어 있음 확인 기능을 포함한다.

큐의 기본 연산

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

1. 인큐(Enqueue)

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

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

2. 디큐(Dequeue)

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

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

3. 피크(Peek)

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

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

4. 비어 있음 확인(IsEmpty)

큐가 비어 있는지 확인한다.

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

큐의 시간 복잡도

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

• 인큐(Enqueue): O(1)
• 디큐(Dequeue): O(1)
• 피크(Peek): O(1)
• 비어 있음 확인(IsEmpty): O(1)

연결 리스트 기반 큐도 동일한 시간 복잡도를 가지지만, 메모리 할당/해제 비용이 추가된다.

연결 리스트 기반 큐 구현

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

class LinkedQueue {
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node front;
    private Node rear;
    
    public LinkedQueue() {
        front = rear = null;
    }
    
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }
    
    public int dequeue() {
        if (front == null) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int data = front.data;
        front = front.next;
        if (front == null) rear = null;
        return data;
    }
    
    public int peek() {
        if (front == null) {
            System.out.println("Queue is Empty");
            return -1;
        }
        return front.data;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
}

연결 리스트 기반 큐는 배열 기반 큐와 달리 크기 제한이 없지만, 노드 생성 비용이 추가된다.

큐를 활용한 알고리즘

큐는 BFS, 작업 스케줄링, 슬라이딩 윈도우 등에서 사용된다.

1. BFS(너비 우선 탐색)

그래프에서 노드를 레벨 순서로 탐색한다.

import java.util.LinkedList;

public void bfs(int start, int[][] graph, boolean[] visited) {
    LinkedQueue queue = new LinkedQueue();
    queue.enqueue(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int v = queue.dequeue();
        System.out.print(v + " ");
        for (int u : graph[v]) {
            if (!visited[u]) {
                queue.enqueue(u);
                visited[u] = true;
            }
        }
    }
}

2. 슬라이딩 윈도우 최대값

배열에서 크기 k의 슬라이딩 윈도우의 최대값을 찾는다.

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    LinkedQueue deque = new LinkedQueue();
    
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peek() < i - k + 1) {
            deque.dequeue();
        }
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.dequeueLast();
        }
        deque.enqueue(i);
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peek()];
        }
    }
    return result;
}

3. 작업 스케줄링

작업 대기열을 큐로 관리한다.

public void processTasks(int[] tasks) {
    LinkedQueue queue = new LinkedQueue();
    for (int task : tasks) {
        queue.enqueue(task);
    }
    while (!queue.isEmpty()) {
        int task = queue.dequeue();
        System.out.println("Processing task: " + task);
    }
}

심화 주제: 큐 최적화

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

1. 원형 큐 사용

배열 기반 큐에서 공간 낭비를 줄이기 위해 원형 큐를 사용한다.

2. 동적 배열 사용

배열 기반 큐에서 크기를 동적으로 확장한다.

public void enqueue(int data) {
    if (size == capacity) {
        int[] newArr = new int[capacity * 2];
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[(front + i) % capacity];
        }
        arr = newArr;
        front = 0;
        rear = size - 1;
        capacity *= 2;
    }
    rear = (rear + 1) % capacity;
    arr[rear] = data;
    size++;
}

3. 메모리 관리

연결 리스트 기반 큐에서 노드를 재사용하거나 가비지 컬렉션에 도움을 준다.

큐의 한계와 대안

큐는 접근이 제한적이며, 중간 데이터 조작이 불가능하다. 자바에서는 java.util.LinkedList와 java.util.ArrayDeque를 제공한다.

import java.util.LinkedList;

LinkedList<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll(); // 1

ArrayDeque는 큐와 덱으로 사용 가능하며, 성능이 더 우수하다.

import java.util.ArrayDeque;

ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll(); // 1

문제

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

5
enqueue 1
enqueue 2
dequeue
enqueue 3
dequeue

1
2

import java.util.Scanner;

public class QueueOperations {
    static class CircularQueue {
        private int[] arr;
        private int front;
        private int rear;
        private int capacity;
        private int size;
        
        CircularQueue(int size) {
            arr = new int[size];
            capacity = size;
            front = 0;
            rear = -1;
            size = 0;
        }
        
        void enqueue(int data) {
            rear = (rear + 1) % capacity;
            arr[rear] = data;
            size++;
        }
        
        int dequeue() {
            if (size == 0) return -1;
            int data = arr[front];
            front = (front + 1) % capacity;
            size--;
            return data;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        CircularQueue queue = new CircularQueue(N);
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            if (operation.startsWith("enqueue")) {
                int x = Integer.parseInt(operation.split(" ")[1]);
                queue.enqueue(x);
            } else {
                System.out.println(queue.dequeue());
            }
        }
        sc.close();
    }
}

3
2 3 1

6

import java.util.Scanner;

public class TaskScheduling {
    static class LinkedQueue {
        static class Node {
            int data;
            Node next;
            Node(int data) {
                this.data = data;
                this.next = null;
            }
        }
        
        private Node front;
        private Node rear;
        
        LinkedQueue() {
            front = rear = null;
        }
        
        void enqueue(int data) {
            Node newNode = new Node(data);
            if (rear == null) {
                front = rear = newNode;
                return;
            }
            rear.next = newNode;
            rear = newNode;
        }
        
        int dequeue() {
            if (front == null) return -1;
            int data = front.data;
            front = front.next;
            if (front == null) rear = null;
            return data;
        }
        
        boolean isEmpty() {
            return front == null;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        LinkedQueue queue = new LinkedQueue();
        int totalTime = 0;
        
        for (int i = 0; i < N; i++) {
            int time = sc.nextInt();
            queue.enqueue(time);
        }
        
        while (!queue.isEmpty()) {
            totalTime += queue.dequeue();
        }
        
        System.out.println(totalTime);
        sc.close();
    }
}

8 3
1 3 -1 -3 5 3 6 7

3 3 5 5 6 7

import java.util.Scanner;

public class SlidingWindowMax {
    static class Deque {
        static class Node {
            int data;
            Node next;
            Node prev;
            Node(int data) {
                this.data = data;
                this.next = null;
                this.prev = null;
            }
        }
        
        private Node front;
        private Node rear;
        
        Deque() {
            front = rear = null;
        }
        
        void addLast(int data) {
            Node newNode = new Node(data);
            if (rear == null) {
                front = rear = newNode;
                return;
            }
            newNode.prev = rear;
            rear.next = newNode;
            rear = newNode;
        }
        
        void removeFirst() {
            if (front == null) return;
            front = front.next;
            if (front == null) rear = null;
            else front.prev = null;
        }
        
        void removeLast() {
            if (rear == null) return;
            rear = rear.prev;
            if (rear == null) front = null;
            else rear.next = null;
        }
        
        int getFirst() {
            if (front == null) return -1;
            return front.data;
        }
        
        int getLast() {
            if (rear == null) return -1;
            return rear.data;
        }
        
        boolean isEmpty() {
            return front == null;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        
        int[] result = new int[N - k + 1];
        Deque deque = new Deque();
        
        for (int i = 0; i < N; i++) {
            while (!deque.isEmpty() && deque.getFirst() < i - k + 1) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.getFirst()];
            }
        }
        
        for (int max : result) {
            System.out.print(max + " ");
        }
        System.out.println();
        sc.close();
    }
}

마무리

큐는 FIFO 방식으로 데이터를 관리하는 자료구조로, 인큐와 디큐 연산이 빠르다. 배열 기반, 연결 리스트 기반, 원형 큐의 구현, 기본 연산, 시간 복잡도, 활용 알고리즘, 최적화 기법을 다뤘다. 자바의 LinkedList와 ArrayDeque와의 비교를 통해 한계와 대안을 살펴봤다. 문제를 통해 큐를 조작하는 방법을 익혔으니, 이를 바탕으로 더 복잡한 문제를 해결해보자.

스택 (Stack)

프로그래밍에서 스택(Stack)은 데이터를 쌓아 올리는 자료구조로, LIFO(Last In, First Out) 방식으로 동작한다. 즉, 마지막에 추가된 데이터가 가장 먼저 제거된다. 스택은 함수 호출, 괄호 검사, 역순 처리 등 다양한 알고리즘에서 사용된다. 이번 포스팅은 스택의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.

스택을 이해하면 데이터를 순서대로 관리하고 복잡한 문제를 간단히 해결할 수 있다. 하나씩 알아보자.

스택의 정의와 특징

스택은 데이터를 한 방향으로만 추가하고 제거하는 자료구조이다. 데이터를 추가하는 연산을 푸시(push), 제거하는 연산을 팝(pop)이라고 한다. 스택의 최상단은 탑(top)이라 부르며, 이곳에서 데이터가 추가되거나 제거된다.

스택의 장점은 다음과 같다:

• 단순한 구조: LIFO 방식으로 직관적이고 구현이 간단하다.
• 빠른 연산: 푸시와 팝 연산이 O(1) 시간에 수행된다.
• 다양한 활용: 함수 호출 스택, Undo 기능, 괄호 매칭 등에 유용하다.

단점은 다음과 같다:

• 제한된 접근: 최상단 데이터만 접근 가능하며, 중간 데이터 접근은 불가능하다.
• 고정 크기 배열 사용 시 오버플로우: 동적 크기 조정이 필요하다.
• 비연속적 메모리: 연결 리스트 기반 구현 시 캐시 활용도가 낮다.

스택의 종류

스택은 구현 방식에 따라 두 가지로 나뉜다. 아래는 구조를 도식화한 그림이다.

1. 배열 기반 스택(Array-based Stack)

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

[Bottom] [1] [2] [3] [Top]
         ↑           ↑
        Bottom       Top
        

2. 연결 리스트 기반 스택(Linked List-based Stack)

연결 리스트를 사용해 동적으로 크기를 조정한다. 메모리 사용량이 증가하지만 유연하다.

[Top] → [Node|data:3|next] → [Node|data:2|next] → [Node|data:1|null]
        

이 포스팅에서는 배열 기반 스택을 중심으로 설명하며, 필요 시 연결 리스트 기반을 다룬다.

자바에서 배열 기반 스택 구현

배열을 사용한 기본적인 스택 구현 코드를 살펴보자.

class Stack {
    private int[] arr;
    private int top;
    private int capacity;
    
    public Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }
    
    // 푸시: 스택에 데이터 추가
    public void push(int data) {
        if (top >= capacity - 1) {
            System.out.println("Stack Overflow");
            return;
        }
        arr[++top] = data;
    }
    
    // 팝: 스택에서 데이터 제거
    public int pop() {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return -1;
        }
        return arr[top--];
    }
    
    // 피크: 최상단 데이터 확인
    public int peek() {
        if (top < 0) {
            System.out.println("Stack is Empty");
            return -1;
        }
        return arr[top];
    }
    
    // 비어 있는지 확인
    public boolean isEmpty() {
        return top < 0;
    }
}

이 코드는 배열 기반 스택으로, 푸시, 팝, 피크, 비어 있음 확인 기능을 포함한다.

스택의 기본 연산

스택의 주요 연산은 다음과 같다:

1. 푸시(Push)

스택의 최상단에 데이터를 추가한다.

public void push(int data) {
    if (top >= capacity - 1) {
        System.out.println("Stack Overflow");
        return;
    }
    arr[++top] = data;
}

2. 팝(Pop)

스택의 최상단 데이터를 제거하고 반환한다.

public int pop() {
    if (top < 0) {
        System.out.println("Stack Underflow");
        return -1;
    }
    return arr[top--];
}

3. 피크(Peek)

최상단 데이터를 제거하지 않고 반환한다.

public int peek() {
    if (top < 0) {
        System.out.println("Stack is Empty");
        return -1;
    }
    return arr[top];
}

4. 비어 있음 확인(IsEmpty)

스택이 비어 있는지 확인한다.

public boolean isEmpty() {
    return top < 0;
}

스택의 시간 복잡도

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

• 푸시(Push): O(1)
• 팝(Pop): O(1)
• 피크(Peek): O(1)
• 비어 있음 확인(IsEmpty): O(1)

연결 리스트 기반 스택도 동일한 시간 복잡도를 가지지만, 메모리 할당/해제 비용이 추가된다.

연결 리스트 기반 스택 구현

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

class LinkedStack {
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node top;
    
    public LinkedStack() {
        top = null;
    }
    
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
    }
    
    public int pop() {
        if (top == null) {
            System.out.println("Stack is Empty");
            return -1;
        }
        int data = top.data;
        top = top.next;
        return data;
    }
    
    public int peek() {
        if (top == null) {
            System.out.println("Stack is Empty");
            return -1;
        }
        return top.data;
    }
    
    public boolean isEmpty() {
        return top == null;
    }
}

연결 리스트 기반 스택은 배열 기반 스택과 달리 오버플로우가 없지만, 노드 생성 비용이 추가된다.

스택을 활용한 알고리즘

스택은 다양한 알고리즘에서 사용된다. 괄호 검사, 수식 평가, DFS(깊이 우선 탐색) 등에서 핵심적인 역할을 한다.

1. 괄호 검사

문자열에 포함된 괄호가 올바르게 짝지어졌는지 확인한다.

public boolean isValidParentheses(String s) {
    Stack stack = new Stack(100);
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = (char) stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

2. 후위 표기법 평가

후위 표기법(Reverse Polish Notation) 수식을 계산한다.

public int evaluateRPN(String[] tokens) {
    Stack stack = new Stack(100);
    for (String token : tokens) {
        if (token.equals("+") || token.equals("-") ||
            token.equals("*") || token.equals("/")) {
            int b = stack.pop();
            int a = stack.pop();
            switch (token) {
                case "+": stack.push(a + b); break;
                case "-": stack.push(a - b); break;
                case "*": stack.push(a * b); break;
                case "/": stack.push(a / b); break;
            }
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

3. 다음 큰 요소 찾기

배열에서 각 요소의 다음 큰 요소를 찾는다.

public int[] nextGreaterElement(int[] nums) {
    int[] result = new int[nums.length];
    Stack stack = new Stack(nums.length);
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        result[stack.pop()] = -1;
    }
    return result;
}

심화 주제: 스택 최적화

스택을 효율적으로 사용하려면 몇 가지 기법을 고려해야 한다.

1. 동적 배열 사용

배열 기반 스택에서 오버플로우를 방지하기 위해 배열 크기를 동적으로 확장한다.

public void push(int data) {
    if (top >= capacity - 1) {
        int[] newArr = new int[capacity * 2];
        for (int i = 0; i < capacity; i++) {
            newArr[i] = arr[i];
        }
        arr = newArr;
        capacity *= 2;
    }
    arr[++top] = data;
}

2. 메모리 관리

연결 리스트 기반 스택에서 노드를 재사용하거나 가비지 컬렉션에 도움을 준다.

3. 스레드 안전성

다중 스레드 환경에서는 동기화를 고려해야 한다.

스택의 한계와 대안

스택은 접근이 제한적이며, 중간 데이터 조작이 불가능하다. 자바에서는 java.util.Stack과 java.util.ArrayDeque를 제공한다.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // 2

ArrayDeque는 스택과 큐로 모두 사용 가능하며, 성능이 더 우수하다.

import java.util.ArrayDeque;

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // 2

문제

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

5
push 1
push 2
pop
push 3
pop

2
3

import java.util.Scanner;

public class StackOperations {
    static class Stack {
        private int[] arr;
        private int top;
        private int capacity;
        
        Stack(int size) {
            arr = new int[size];
            capacity = size;
            top = -1;
        }
        
        void push(int data) {
            arr[++top] = data;
        }
        
        int pop() {
            if (top < 0) return -1;
            return arr[top--];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Stack stack = new Stack(N);
        sc.nextLine();
        
        for (int i = 0; i < N; i++) {
            String operation = sc.nextLine();
            if (operation.startsWith("push")) {
                int x = Integer.parseInt(operation.split(" ")[1]);
                stack.push(x);
            } else {
                System.out.println(stack.pop());
            }
        }
        sc.close();
    }
}

6
({[]})

YES

import java.util.Scanner;

public class ValidParentheses {
    static class Stack {
        private char[] arr;
        private int top;
        private int capacity;
        
        Stack(int size) {
            arr = new char[size];
            capacity = size;
            top = -1;
        }
        
        void push(char data) {
            arr[++top] = data;
        }
        
        char pop() {
            if (top < 0) return '\0';
            return arr[top--];
        }
        
        boolean isEmpty() {
            return top < 0;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        String s = sc.nextLine();
        Stack stack = new Stack(N);
        
        boolean isValid = true;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    isValid = false;
                    break;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    isValid = false;
                    break;
                }
            }
        }
        if (!stack.isEmpty()) isValid = false;
        
        System.out.println(isValid ? "YES" : "NO");
        sc.close();
    }
}

4
2 1 3 4

3 3 4 -1

import java.util.Scanner;

public class NextGreaterElement {
    static class Stack {
        private int[] arr;
        private int top;
        private int capacity;
        
        Stack(int size) {
            arr = new int[size];
            capacity = size;
            top = -1;
        }
        
        void push(int data) {
            arr[++top] = data;
        }
        
        int pop() {
            if (top < 0) return -1;
            return arr[top--];
        }
        
        int peek() {
            if (top < 0) return -1;
            return arr[top];
        }
        
        boolean isEmpty() {
            return top < 0;
        }
    }
    
    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();
        }
        
        int[] result = new int[N];
        Stack stack = new Stack(N);
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }
        
        for (int i = 0; i < N; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
        sc.close();
    }
}

마무리

스택은 LIFO 방식으로 데이터를 관리하는 자료구조로, 푸시와 팝 연산이 빠르다. 배열 기반과 연결 리스트 기반 스택의 구현, 기본 연산, 시간 복잡도, 활용 알고리즘, 최적화 기법을 다뤘다. 자바의 Stack과 ArrayDeque와의 비교를 통해 한계와 대안을 살펴봤다. 문제를 통해 스택을 조작하는 방법을 익혔으니, 이를 바탕으로 더 복잡한 문제를 해결해보자.

연결 리스트 (Linked List)

프로그래밍에서 연결 리스트(Linked List)는 데이터를 노드라는 단위로 저장하며, 각 노드가 다음 노드를 가리키는 포인터를 포함하는 자료구조이다. 배열과 달리 메모리가 연속적이지 않고, 동적으로 크기를 조정할 수 있다. 연결 리스트는 삽입과 삭제가 빈번한 상황에서 유용하며, 다양한 알고리즘의 기초가 된다. 이번 포스팅은 연결 리스트의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.

연결 리스트를 이해하면 데이터를 유연하게 관리하고 복잡한 문제를 효율적으로 해결할 수 있다. 하나씩 알아보자.

연결 리스트의 정의와 특징

연결 리스트는 데이터를 저장하는 노드와 다음 노드를 가리키는 포인터로 구성된다. 각 노드는 데이터와 다음 노드의 참조를 포함하며, 마지막 노드는 다음 노드가 없음을 나타내기 위해 null을 가리킨다. 연결 리스트는 배열과 달리 메모리 공간이 비연속적이며, 크기가 고정되지 않는다.

연결 리스트의 장점은 다음과 같다:

• 동적 크기 조정: 필요에 따라 노드를 추가하거나 제거할 수 있다.
• 효율적인 삽입/삭제: 특정 위치에서 삽입이나 삭제가 O(1) 시간에 가능하다(노드에 접근한 후).
• 유연한 메모리 사용: 메모리를 동적으로 할당하므로, 데이터 크기 변화에 적응적이다.

단점은 다음과 같다:

• 느린 접근 시간: 특정 노드에 접근하려면 리스트를 순회해야 하므로 O(n) 시간이 걸린다.
• 추가 메모리: 각 노드마다 포인터를 저장하므로 메모리 사용량이 증가한다.
• 캐시 비친화성: 메모리가 비연속적이어서 캐시 활용도가 낮다.

연결 리스트의 종류

연결 리스트는 구조에 따라 여러 종류로 나뉜다. 아래는 주요 형태와 구조를 도식화한 그림이다.

1. 단일 연결 리스트(Singly Linked List)

가장 기본적인 형태로, 각 노드가 다음 노드만 가리킨다.

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

단일 연결 리스트 도식

[Head] → [Node1|data:1|next] → [Node2|data:2|next] → [Node3|data:3|null]
        

2. 이중 연결 리스트(Doubly Linked List)

각 노드가 이전 노드와 다음 노드를 모두 가리킨다. 양방향 순회가 가능하다.

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

이중 연결 리스트 도식

[null] ↔ [Node1|prev|data:1|next] ↔ [Node2|prev|data:2|next] ↔ [Node3|prev|data:3|null]
        

3. 원형 연결 리스트(Circular Linked List)

마지막 노드가 첫 번째 노드를 가리켜 순환 구조를 형성한다.

원형 연결 리스트 도식

[Head] → [Node1|data:1|next] → [Node2|data:2|next] → [Node3|data:3|next] ↺
        ↑______________________________________________________________|
        

이 포스팅에서는 주로 단일 연결 리스트를 중심으로 설명하며, 필요 시 다른 변형을 다룬다.

자바에서 단일 연결 리스트 구현

단일 연결 리스트를 자바로 구현하는 기본 코드를 살펴보자.

class LinkedList {
    Node head;
    
    class Node {
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    // 리스트 끝에 노드 추가
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
    
    // 리스트 출력
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

이 코드는 기본적인 단일 연결 리스트 구현으로, 노드 추가와 리스트 출력 기능을 포함한다.

연결 리스트의 기본 연산

연결 리스트를 사용하려면 주요 연산을 이해해야 한다. 삽입, 삭제, 순회, 검색 등이 핵심 연산이다.

1. 삽입

노드를 리스트의 처음, 끝, 또는 특정 위치에 추가한다.

// 리스트 처음에 노드 추가
public void prepend(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

// 특정 위치에 노드 추가 (index는 0부터 시작)
public void insertAt(int index, int data) {
    if (index == 0) {
        prepend(data);
        return;
    }
    Node newNode = new Node(data);
    Node current = head;
    for (int i = 0; i < index - 1 && current != null; i++) {
        current = current.next;
    }
    if (current != null) {
        newNode.next = current.next;
        current.next = newNode;
    }
}

2. 삭제

특정 노드를 제거한다.

// 첫 번째 노드 삭제
public void deleteFirst() {
    if (head != null) {
        head = head.next;
    }
}

// 특정 값의 노드 삭제 (첫 번째로 발견된 노드)
public void deleteValue(int data) {
    if (head == null) return;
    if (head.data == data) {
        head = head.next;
        return;
    }
    Node current = head;
    while (current.next != null && current.next.data != data) {
        current = current.next;
    }
    if (current.next != null) {
        current.next = current.next.next;
    }
}

3. 순회

리스트의 모든 노드를 방문한다.

public void traverse() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
    System.out.println();
}

4. 검색

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

public boolean search(int data) {
    Node current = head;
    while (current != null) {
        if (current.data == data) return true;
        current = current.next;
    }
    return false;
}

연결 리스트의 시간 복잡도

연결 리스트의 주요 연산의 시간 복잡도는 다음과 같다:

• 접근: O(n) - 특정 인덱스나 노드에 접근하려면 순회 필요.
• 삽입/삭제: O(1) - 노드에 이미 접근한 경우. 접근 시간이 포함되면 O(n).
• 검색: O(n) - 리스트를 순회하며 값을 찾는다.
• 순회: O(n) - 모든 노드를 방문한다.

배열과 비교하면, 접근은 느리지만 삽입과 삭제에서 유리하다.

이중 연결 리스트 구현

이중 연결 리스트는 양방향 순회가 가능해 특정 상황에서 유용하다.

class DoublyLinkedList {
    Node head;
    
    class Node {
        int data;
        Node prev;
        Node next;
        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }
    
    // 리스트 끝에 노드 추가
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }
    
    // 리스트 출력 (정방향)
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

이중 연결 리스트는 삭제나 역방향 순회에서 단일 연결 리스트보다 편리하다.

연결 리스트를 활용한 알고리즘

연결 리스트는 다양한 알고리즘에서 사용된다. 스택, 큐, 그래프 알고리즘 등에서 활용되며, 리스트 자체를 조작하는 문제도 많다.

1. 리스트 반전

연결 리스트의 노드 순서를 반대로 바꾼다.

public void reverse() {
    Node prev = null;
    Node current = head;
    while (current != null) {
        Node next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}

2. 사이클 탐지

연결 리스트에 사이클이 있는지 확인한다(플로이드의 토끼와 거북이 알고리즘).

public boolean hasCycle() {
    if (head == null) return false;
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}