Part of your World

스택(Stack)은 컴퓨터 과학에서 중요한 자료 구조 중 하나이다. 스택은 항목들이 추가되고 삭제되는 끝이 한 개만 있는 '한정적 접근'의 선형 자료 구조이다. 이러한 특성 때문에 스택은 '후입선출'(LIFO, Last-In-First-Out) 원칙을 따르는 것으로 알려져 있다. 즉, 가장 최근에 스택에 추가된 항목이 가장 먼저 제거되는 순서를 따른다.

스택에서는 주로 다음 네 가지 기본 연산이 사용된다.

1. Push: 스택의 상단에 항목을 추가한다.
2. Pop: 스택의 상단에 있는 항목을 제거하고 반환한다. 이 연산을 수행하면, 스택에서 항목이 제거된다.
3. Peek/Top: 스택의 상단에 있는 항목을 반환하지만 제거하지는 않는다.
4. isEmpty: 스택이 비어 있는지 확인한다.

스택은 다양한 애플리케이션에서 사용된다. 함수 호출 스택, 실행 취소 스택, 브라우저의 이전 페이지/다음 페이지 구현 등 여러 분야에서 스택의 개념이 활용된다. 또한, 스택은 다른 복잡한 알고리즘, 예를 들어 깊이 우선 탐색(DFS)에서도 중요한 역할을 한다.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Stack: " + stack);

        int removedElement = stack.pop();
        System.out.println("Popped element: " + removedElement);
        System.out.println("Stack after pop operation: " + stack);

        int peekedElement = stack.peek();
        System.out.println("Peeked element: " + peekedElement);
        System.out.println("Stack after peek operation: " + stack);

        boolean isEmpty = stack.isEmpty();
        System.out.println("Is stack empty? " + isEmpty);
    }
}

Integer 타입의 Stack 객체를 생성하고, push 메소드를 사용하여 스택에 원소를 추가하고, pop 메소드를 사용하여 가장 위의 원소를 제거하고, peek 메소드를 사용하여 가장 위의 원소를 확인하며, isEmpty 메소드를 사용하여 스택이 비어 있는지 확인한다.

이진 검색 트리(Binary Search Tree, BST)는 이진 트리의 한 종류로, 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들을, 오른쪽 서브트리에는 해당 노드의 값보다 큰 값들을 저장하는 특징을 가진다.

다음은 이진 검색 트리의 특징이다:

1. 각 노드는 하나의 키(데이터)를 가지며, 이 키는 고유한 값을 가진다.
2. 왼쪽 서브트리 (하위 트리)의 모든 키는 루트의 키보다 작다.
3. 오른쪽 서브트리의 모든 키는 루트의 키보다 크다.
4. 왼쪽과 오른쪽 서브트리 각각이 이진 검색 트리여야 한다.

이러한 속성 덕분에 이진 검색 트리에서는 데이터 검색, 삽입, 삭제 등의 연산을 효율적으로 처리할 수 있다. 이진 검색 트리에서의 검색 연산은 트리의 높이에 비례하는 시간 복잡도를 가지므로, 균형 잡힌 트리에서는 로그 시간 복잡도를 가지게 된다. 하지만 트리가 한쪽으로 치우쳐져 있는 경우(즉, 균형이 잘 잡혀있지 않은 경우) 검색 성능이 저하될 수 있다. 이런 문제를 해결하기 위해 AVL 트리, 레드-블랙 트리 등의 자가 균형 이진 검색 트리가 개발되었다.

예를 들어, 아래의 숫자들을 이진 검색 트리에 넣으면, 8, 3, 10, 1, 6, 14, 4, 7, 13

이것을 이진 검색 트리로 구성하면 다음과 같다.

        8
       / \\
      3  10
     / \\   \\
    1   6   14
       / \\  /
      4   7 13

이 트리는 다음의 성질을 만족한다:

• 모든 노드는 유일한 값이다.
• 왼쪽 서브트리의 모든 노드의 값은 루트의 값보다 작다.
• 오른쪽 서브트리의 모든 노드의 값은 루트의 값보다 크다.
• 모든 서브트리도 이진 검색 트리이다.

이 이진 검색 트리에서 어떤 노드를 찾으려면 어떻게 해야 할까? 예를 들어 7을 찾는다고 가정해 보면.

• 먼저 루트에서 시작한다. 현재 노드가 8이고, 7은 8보다 작으므로 왼쪽 자식으로 이동한다.
• 현재 노드는 3이다. 7은 3보다 크므로 오른쪽 자식으로 이동한다.
• 현재 노드는 6이다. 7은 6보다 크므로 다시 오른쪽 자식으로 이동한다.
• 이제 현재 노드는 7입니다. 원하는 값을 찾았으므로 검색을 종료한다.

이진 검색 트리는 데이터를 효율적으로 관리하고 검색하는 데 매우 유용하다. 그러나 트리가 균형을 잃어버릴 경우 검색 성능이 떨어질 수 있으므로 이를 보완하기 위한 다양한 이진 검색 트리(예: AVL 트리, 레드-블랙 트리)가 존재한다.

해싱(Hashing)은 키-값 쌍을 저장하고 검색하는 데 사용되는 방법이다. 해싱은 데이터 구조인 해시 테이블을 사용하여 데이터를 저장하고 검색한다.

해싱의 핵심 개념은 해시 함수이다. 해시 함수는 키를 입력으로 받아 정수인 해시 코드를 반환한다. 이 해시 코드는 저장된 데이터의 인덱스로 사용된다. 따라서 해시 함수는 키-값 쌍을 해시 테이블의 특정 위치에 연결한다.

해싱은 일반적으로 다음과 같은 시나리오에서 매우 효과적이다:

1. 데이터의 크기가 매우 큰 경우: 해싱은 키에 대한 고정 크기의 해시 코드를 생성하므로, 데이터의 크기에 관계없이 데이터를 저장하고 검색하는 데 매우 효율적이다.
2. 빠른 검색이 필요한 경우: 해싱은 평균적으로 O(1)의 시간 복잡도를 가진다. 즉, 데이터의 크기에 관계없이 일정한 검색 시간을 보장한다.

그러나 해싱에는 몇 가지 단점도 있습니다. 먼저, 해시 충돌이 발생할 수 있다. 이는 두 개 이상의 키가 동일한 해시 코드를 가질 때 발생하는데, 이 문제를 해결하기 위한 여러 전략이 있다. 또한 해시 테이블은 메모리를 많이 사용하는 경향이 있으며, 이는 메모리가 제한적인 시스템에서 문제가 될 수 있다.

Java에서는 HashMap이라는 내장된 클래스를 사용하여 해싱을 구현할 수 있다. HashMap 클래스는 키와 값을 저장하는 데이터 구조로서, 키는 고유한 값이어야 한다.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // HashMap 객체 생성
        HashMap<String, Integer> map = new HashMap<>();

        // 키-값 쌍 추가
        map.put("Apple", 10);
        map.put("Banana", 20);
        map.put("Cherry", 30);

        // 키를 사용하여 값을 검색
        int value = map.get("Banana");
        System.out.println("Banana의 값: " + value);

        // 키를 사용하여 값 수정
        map.put("Banana", 25);

        value = map.get("Banana");
        System.out.println("수정된 Banana의 값: " + value);
    }
}

HashMap 객체인 **map**은 문자열 키와 정수 값 쌍을 저장한다. put 메소드를 사용하여 키-값 쌍을 추가하고, get 메소드를 사용하여 키에 해당하는 값을 검색한다. 해시맵에서는 키를 사용하여 값을 직접 접근할 수 있으므로, 검색 작업은 빠르게 수행된다.