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 메소드를 사용하여 스택이 비어 있는지 확인한다.

1. 반에서 가장 키 큰 사람을 찾는 방법

• 한 명씩 물어보면서 키가 제일 큰 사람을 기억하고 다음 사람이 이전에 제일 큰 사람보다 크다면 그 사람을 기억한다. 이 과정을 끝까지 진행하면 가장 큰 사람을 찾을 수 있다.

2. 상황이 복잡해 진다면?

• 가장 키 큰 사람이 두명이라면?
• 가장 같은 키를 많이 가진 수의 사람들을 구한다면?

3. 자료구조의 중요성

• 이 로그에서는 자세히 설명해주지는 않지만 보다 빠르고 편리하게 계산하기 위해서는 적절한 자료구조를 선택해야 한다.
• 배열, 리스트, 맵, 셋 등등 자료구조의 특성과 장단점을 이해하고 사용해야 한다.

4. 예외 처리(멍청한 컴퓨터 말썽 못부리게 하기)

• 평균 값을 구하는 알고리즘을 만들 때 sum이라는 변수에 모든 값을 더한다.
• N이라는 변수에 개수를 구한다.
• 하지만 N이 0개라면? > 컴퓨터는 sum/N을 진행해버리고 0으로 나누는 참사(에러)가 발생할 것이다.
• 따라서 N이 0일 때는 계산을 하지 말라는 예외 처리가 필요하다.

5. 선형 알고리즘

• 처리 시간이 데이터양에 정비례 하는 알고리즘을 의미한다.
• 이 로그에서는 선형 알고리즘만 딱 말했지만 정비례하지 않는 알고리즘이 있을 것이다.
  • for 문을 n만큼 2번 돌면 n의 제곱만큼 계산된다. 이것은 정비례가 아닌 제곱에 비례하는 것이다.

6. 빅-오 표기법

• 책에서는 안알려주는 것 같지만 자주 사용하는 용어이다.
• 가장 높은 차수의 항만 표기하는 것이다.
  • for문을 n+1만큼 2번 돌면 n^2+2n+1만큼 돈다.
  • 이것을 O(n^2)으로 아주 쉽게 표현해주는 것이다.
  • 수학적으로 접근한다면 n이 3일때는 n^2=9, 2n+1=7이다 . 거의 반반씩 비율을 차지하고있다.
  • 하지만 n이 10000이라면? n^2=100000000, 2n+1=20001이다. 0.02% 비율이다.
  • 숫자가 커질 수록 가장 높은 차수의 항만 의미를 가지며 빅-오 표기법을 통해 시간 복잡도의 경향성만 표기하는 것이다.
• O(1) : 데이터 양에 상관없이 처리 시간이 일정함
• O(n) : 데이터 양에 비례하여 처리 시간이 증가
• NLogN, n^2, n^3, 2^n 등등 이 있다.
• 참고로 시간 복잡도를 구하는 방법은 최악의 경우를 생각하는 것이다.
  • n명의 사람 중 유재석를 찾으라고 했을 때 마지막(n) 번째 사람이 유재석인 경우

이진 검색 트리(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 트리, 레드-블랙 트리)가 존재한다.