2025-11-14

오늘 배운 것

  • 기본 개념
    • 자료구조란?
      • 데이터를 효율적으로 저장/관리/검색/수정하기 위한 구조
      • 목적 : 시간과 공간을 최소화해 문제를 더 빠르게 해결
      • 종류 : 선형, 비선형, 해시, 트리, 그래프 등
    • ADT(Abastract Data Type: 추상화된 데이터 타입)
      • 자료구조를 사용 관점에서 정의한 것으로 내부 구현이 어떻게 되어 있는지 숨기고 어떤 연산을 지원하는지만 정의
      • 예 : Stack ADT는 push, pop, peek, isEmpty만 정의 내부가 배열인지 리스트인지 관심 없음
    • 배열 VS 연결리스트
      • 배열
        • 개념
          • 메모리에 연속된 공간으로 저장
          • 인덱스 O(1) 접근 가능
        • 장점
          • 랜덤 접근 빠름 O(1)
          • 캐시 친화적 → 실제로도 빠름
        • 단점
          • 중간 삽입/삭제 O(n)
          • 크기 고정 (자바 배열은 불변)
      • 연결 리스트
        • 개념
          • 노드가 포인터로 연결된 구조
          • 메모리가 연속적일 필요 없음
        • 장점
          • 삽입/삭제 O(1) (단, 노드 참조를 알고 있을 때)
          • 크기 제약 없음
        • 단점
          • 랜덤 접근 O(n)
          • 캐시 비친화적 → 실제 성능 체감 낮음
          • 추가 메모리 사용(포인터)
  • 선형 자료구조
    • ArrayList vs LinkedList
      • ArrayList
        • 개념 : 동적 배열 기반, 연속된 메모리
        • 구조 : Object[] 배열
        • 장점
        • 단점
      • LinkedList
        • 개념 : Node + Pointer 기반, 비연속 메모리
        • 구조 : Node(prev, valaue, next)
        • 장점
        • 단점
      • 조회가 많을 때 → ArrayList
      • 삽입/삭제가 많을 때 → LinkedList
    • Stack
      • 개념
        • LIFO (Last In First Out)
        • 한쪽(top)에서만 삽입/삭제
      • 제공 연산
        • push
        • pop
        • peek
        • isEmpty
      • 시간 복잡도
        • push, pop, peek : O(1)
      • 특징
        • 함수 호출 스택, 괄호 검사, DFS 등에서 사용
    • Queue
      • 개념
        • FIFO (First In First Out)
        • 한쪽에서 넣고(front) 다른 쪽에서 뺌(back)
      • 제공 연산
        • offer
        • poll
        • peek
        • isEmpty
      • 시간 복잡도
        • offer, poll, peek : O(1)
      • 특징
        • BFS, 프로세스 스케줄러, 캐시, 작업 큐 등 사용
    • Deque(Double-ended Queue)
      • 개념
        • 양쪽에서 삽입/삭제 가능한 큐
      • 제공 연산
        • addFirst
        • addLast
        • removeFirst
        • removeLast
        • peekFirst
        • peekLast
      • 시간 복잡도 : O(1)
      • 특징 : 슬라이딩 윈도우, Monotonic Queue, BFS 최적화 등에 사용
    • stack → queue
      • 아이디어
        • 스택 2개를 사용
        • inStack : 입력
        • outStack : 출력
        • 출력시 outStack이 비어 있으면 inStack모든 값을 옮김
      • 시간 복잡도
        • 각 원소가 최대 1번만 이동 : 평균 O(1)
        • 최악 : O(n) (하지만 거의 없음! → amortized O(1))

      • 코드

          class MyQueue {
      Stack<Integer> inStack = new Stack<>();
      Stack<Integer> outStack = new Stack<>();
            
      // 큐에 데이터 넣기
      public void push(int x) {
          inStack.push(x);
      }
            
      // 큐에서 데이터 꺼내기
      public int pop() {
          shift();
          return outStack.pop();
      }
            
      // 큐의 front 확인
      public int peek() {
          shift();
          return outStack.peek();
      }
            
      // 요소가 없을 때 true
      public boolean empty() {
          return inStack.isEmpty() && outStack.isEmpty();
      }
            
      // 필요한 순간에만 in → out으로 옮김 (역순)
      private void shift() {
          if (outStack.isEmpty()) {
              while (!inStack.isEmpty()) {
                  outStack.push(inStack.pop());
              }
          }
      }
  }
    • queue → stack
      • 아이디어
        • 큐 2개를 사용
        • push 할 때 q2에 새 원소를 넣고
        • q1의 원소를 q2에 다 넣어서 새원소가 front에 오게 함
        • 이후 swap(q1, q2)
      • 시간 복잡도
        • push: O(n)
        • pop: O(1)

      • 코드

          class MyStack {
      Queue<Integer> q1 = new LinkedList<>();
      Queue<Integer> q2 = new LinkedList<>();
            
      // 스택 push
      public void push(int x) {
          q2.offer(x);  // 새 값 우선 넣고
          while (!q1.isEmpty()) {  // q1 요소를 전부 q2 뒤로 이동
              q2.offer(q1.poll());
          }
          // swap
          Queue<Integer> temp = q1;
          q1 = q2;
          q2 = temp;
      }
            
      // pop : q1의 front가 top
      public int pop() {
          return q1.poll();
      }
            
      // top
      public int top() {
          return q1.peek();
      }
            
      // empty
      public boolean empty() {
          return q1.isEmpty();
      }
  }
    • Monotonic Stack / Monotonic Queue
      • Monotonic Stack
        • 개념
        • 사용처
        • 시간 복잡도
      • Monotonic Queue
        • 개념
        • 사용처
        • 시간 복잡도
  • 우선순위 큐/힙
    • 우선 순위 큐
      • 개념
        • 들어온 순서와 상관 없이 가장 작은/큰 값이 먼저 나오는 큐
      • 특징
        • 내부적으로 Binary Heap
        • 자바 기본은 min-heap
      • 제공 연산
        • offer, poll, peek
      • 시간 복잡도
        • offer/poll : O(logn)
        • peek : O(1)
    • 힙
      • 개념
        • 완전 이진 트리 형태
        • 최소 힙 기준, 부모 ≤ 자식
        • 가장 큰/작은 값을 O(1)로 조회 가능
      • 구조적 특징
        • 완전 이진 트리
        • 배열로 표현되는 이유
      • 힙의 종류
        • 최소/최대 힙
        • indexed heap (인덱스 업데이트 가능한 힙)
        • d-ary heap (자식이 여러개)
      • Heapify : 힙 재정렬 과정
        • down-heapify (힙이 깨졌을 때 아래로 내려가며 정렬)
        • up-heapify (삽입 시 위로 올라가며 정렬)
        • 시간 복잡도 : 항상 트리의 높이만큼 이동
      • 시간 복잡도
        • 삽입/삭제 : O(log n)
        • heapify 전체 구성 : O(n)
        • 최대/최소 조회 : O(1)

      • 코드

          class MinHeap {
      List<Integer> heap = new ArrayList<>();
            
      public void add(int x) {
          heap.add(x);
          up(heap.size() - 1);
      }
            
      public int poll() {
          int root = heap.get(0);
          int last = heap.remove(heap.size() - 1);
            
          if (!heap.isEmpty()) {
              heap.set(0, last);
              down(0);
          }
          return root;
      }
            
      private void up(int i) {
          while (i > 0) {
              int p = (i - 1) / 2;
              if (heap.get(p) <= heap.get(i)) break;
              swap(p, i);
              i = p;
          }
      }
            
      private void down(int i) {
          int n = heap.size();
          while (true) {
              int left = i * 2 + 1;
              int right = i * 2 + 2;
              int smallest = i;
            
              if (left < n && heap.get(left) < heap.get(smallest)) smallest = left;
              if (right < n && heap.get(right) < heap.get(smallest)) smallest = right;
            
              if (smallest == i) break;
            
              swap(i, smallest);
              i = smallest;
          }
      }
            
      private void swap(int a, int b) {
          int t = heap.get(a);
          heap.set(a, heap.get(b));
          heap.set(b, t);
      }
  }
  • 해시
    • 개념
      • key를 해시 함수를 통해 배열의 인덱스(해시 값)로 변환하는 자료구조
      • 탐색, 삽입, 삭제 평균 O(1)
        • 최악은 체이닝 리스트면 O(n), 레드블랙트리면 O(logn)
      • 내부는 실제로 배열 + LinkedList/Tree 조합
    • 핵심 구조
      1. 해시 함수
        1. key → index
        2. 이상적인 해시함수 조건
          1. 충돌이 적음
          2. 연산이 빠름
          3. 키를 고르게 분산
      2. 해시 버킷
        1. key-value 저장
        2. 보통 배열 + 그 안에 여러개 저장할 연결리스트 or 트리 구조
    • 사용 이유
      • 탐색, 삽입, 삭제가 평균 O(1)로 빠름
      • 문자열 키 기반 탐색을 빠르게 저장
      • 백엔드에서 사용자 조회, 캐싱, 권한, 세션 처리에서 사용
    • 해싱 충돌
      • 해싱 값이 같아 서로 다른 키가 같은 버킷을 차지하는 현상
      • 해결 방법
        1. 체이닝 (Separate Chaining)
          • 개념
            • 각 해시 버킷 내부에 LinkedList / Tree로 여러 값 저장
          • 구조
            • table[hash(key)] → LinkedList or Tree of Nodes
          • 장점
            • 구현 간단
            • 충돌 많이 나도 안정적으로 저장
            • 확장성 좋음
          • 단점
            • 최악 O(n) : 모두 같은 버킷으로 몰릴 때
              • Java8부터는 이 상황에서 LinkedList가 Red-Black Tree로 전환 ⇒ O(log n)
        2. 오픈 어드레싱 (Openn Addressing)
          • 개념
            • 충돌이 나면 빈 공간을 찾아 저장
            • 탐색 방식
              1. Linear Probing
                1. 한칸씩 순차적 이동
              2. Quadratic Probing
                1. 제곱 간격으로 이동
                  1. 1^2, 2^2, 3^2
              3. Double Hashing
                1. 또 다른 해시 함수를 한 번 더 사용
                2. 탐색 성능 가장 우수
            • 장점
              • 추가적인 메모리 필요 없음
              • 캐시 친화적(배열 기반)
            • 단점
              • 삭제 구현 복잡
              • 테이블이 찰수록 성능 급격히 저하 → 탐색 시간이 늘어나기 때문
              • 버킷 클러스터링 문제 발생 가능
                • 해시 충돌이 계속 이어져서 특정 구간의 연속된 영역이 꽉차는 현상
                • 특히 선형 탐색 방식에서 자주 발생
      • Load Factor (적재율)
        • 해시 테이블이 얼마나 차있는지 나타내는 지표
        • Load Factor = 현재 저장된 데이터 수 / 버킷 수
        • 적재율이 너무 높으면 → 충돌이 많아지고 성능 저하 → 리사이징 발생
        • 자바 기본 값 : 0.75
          • 현재 저장된 데이터 수 / 배열의길이(혹은 버킷 수)> load factor(0.75) 이면 용량 2배로 증가
      • Java HashMap 내부구조
        • 버킷 구조
          • 배열 + (연결리스트 or 레드블랙트리)
            1. 비어 있음 - null
            2. LinkedList 형태 (충돌 낮을 때)
            3. 버킷 크기가 커지면 Red-Black Tree로 자동 변환 treeify
              1. 변환 조건
                1. 버킷의 길이 ≥ 8
                2. 전체 테이블 크기 ≥ 64
  • 트리 기초
    • 개념
      • 부모- 자식 관계로 구성된 비순환(acyclic) 계층적 자료구조
      • 사이클이 없음
      • 루트에서 시작
        • 루트의 깊이는 0
      • 그래프의 한 종류
      • 노드가 n개면 간선은 항상 n-1개
    • 트리 순회
      • 전위 순회 : root → left → right
        • 구조 복사/직렬화 할 때 사용
      • 중위 순회 : left → root → right
        • BST 오름차순 결과
      • 후위 순회 : left → right → root
        • 하위 구조부터 삭제해야할때 사용(폴더 삭제 등)
    • 종류
      • 이진 트리 (Binary Tree)
        • 자식이 최대 2개
      • 완전 이진 트리 (Complete Binary Tree)
        • 왼쪽 부터 빈칸 없이 채워짐
        • 힙이 이 구조
      • 포화 이진 트리 (Full Binary Tree)
        • 모든 내부 노드가 자식 2개
      • 정 이진 트리 (Perfect Binary Tree)
        • 모든 레벨이 꽉 차있음
        • 리프가 같은 depth
      • 이진 탐색 트리 (Binary Search Tree)
        • left → root → right
        • 탐색/삽입 O(logn) 보장 (평균)
        • 정렬된 순서는 inorder
    • 시간 복잡도
      • 탐색 / 삽입 / 삭제
        • 평균 : O(log n)
        • 최악 : O(n) → 한쪽으로 치우쳐져 linked list처럼 됐을 때
      • 순회
        • O(n)
  • 균형 트리 (Balanced Binary Search Tree)
    • 개념
      • 트리의 높이를 O(log n) 수준으로 유지하기 위해 삽입/삭제 시 자동으로 균형을 맞추는 이진 탐색 트리 (한쪽으로 치우쳐지는 것을 방지)
    • 시간 복잡도
      • 탐색 : O(log n)
      • 삽입/삭제 : O(log n) + 재균형
    • 종류
      • AVL Tree (Adelson-Velsky & Landis Tree)
        • 개념
          • 균형이 엄격함
          • 어떤 노드든 왼쪽 높이 - 오른쪽 높이 ≤ 1
          • 탐색이 아주 빠름
          • 회전
        • 장점
          • 검색 성능 최강 (항상 더 균형 잡혀 있음)
          • 균형 조건이 엄격하여 탐색 O(log n) 보장
        • 단점
          • 삽입/삭제 시 회전이 자주 발생
          • 구현 복잡
        • 언제 사용?
          • 검색 비중이 매우 높을 때
      • Red-Black Tree
        • 개념
          • 자바 TreeMap, TreeSet이 사용하는 구조
          • FIFO/균형 유지 덜 엄격하지만 삽입/삭제가 더 빠름
          • 균형 조건 완화로 연산 속도가 전체적으로 안정적
        • 핵심 규칙
          • 5가지 색 규칙으로 균형 유지
          • 이 조건 덕분에 최대 높이 = 2 * log n
        • 장점
          • 속도 매우 안정적
          • 삽입/삭제가 AVL보다 덜 부담
          • 대부분의 언어 라이브러리 기본 구현
        • 단점
          • 탐색에서 AVL보다 약간 느릴 수 있음
        • 어디에 사용?
          • Java TreeMap / TreeSet / HashMap(충돌 버킷이 커지면! 자동 변환)
          • C++ map / multimap / set
          • Linux 커널의 레드블랙트리 구조체(rbtree)
          • JVM 내부 자료구조 탑재
  • 특수 트리
    • 트라이(Trie) - 문자열 처리에 특화된 트리
      • 개념
        • 문자열을 문자 단위로 분리해 트리 형태로 저장하는 자료 구조
      • 장점
        • 문자열 탐색 O(m) (m = 문자열 길이) → 해시 충돌 걱정 없음
        • 공통 접두사 재사용 → 메모리 절약
        • 자동완성 / 사전 / 문자열 검색에 매우 강력
      • 단점
        • 해시보다는 메모리 많이 씀
        • 구현 복잡도 증가

      • 코드

          class TrieNode {
      TrieNode[] child = new TrieNode[26];
      boolean isEnd;
  }
            
  class Trie {
      TrieNode root = new TrieNode();
            
      void insert(String word) {
          TrieNode cur = root;
          for (char c : word.toCharArray()) {
              int idx = c - 'a';
              if (cur.child[idx] == null)
                  cur.child[idx] = new TrieNode();
              cur = cur.child[idx];
          }
          cur.isEnd = true;
      }
            
      boolean search(String word) {
          TrieNode cur = root;
          for (char c : word.toCharArray()) {
              int idx = c - 'a';
              if (cur.child[idx] == null) return false;
              cur = cur.child[idx];
          }
          return cur.isEnd;
      }
            
      boolean startsWith(String prefix) {
          TrieNode cur = root;
          for (char c : prefix.toCharArray()) {
              int idx = c - 'a';
              if (cur.child[idx] == null) return false;
              cur = cur.child[idx];
          }
          return true;
      }
  }
    • 세그먼트트리(Segment Tree) - 구간(min/max/sum) 쿼리를 빠르게 처리하는 트리
      • 개념
        • 배열의 구간 정보를 저장하는 트리
        • 구간 합/최소/최대/최빈값 등을 O(log n)에 처리
      • 특징
        • 완전 이진 트리
        • 업데이트 O(log n)
        • 구간 쿼리 O(log n)
        • 저장 메모리 약 4배 필요

      • 코드 - 구간 합 버전

          int[] tree;
  int n;
            
  int init(int node, int start, int end) {
      if (start == end) return tree[node] = arr[start];
      int mid = (start + end) / 2;
      return tree[node] = init(node*2, start, mid)
                        + init(node*2+1, mid+1, end);
  }
            
  int query(int node, int start, int end, int l, int r) {
      if (r < start || end < l) return 0;
      if (l <= start && end <= r) return tree[node];
      int mid = (start + end) / 2;
      return query(node*2, start, mid, l, r)
           + query(node*2+1, mid+1, end, l, r);
  }
            
  void update(int node, int start, int end, int idx, int diff) {
      if (idx < start || end < idx) return;
      tree[node] += diff;
      if (start != end) {
          int mid = (start + end) / 2;
          update(node*2, start, mid, idx, diff);
          update(node*2+1, mid+1, end, idx, diff);
      }
  }
    • 펜윅 트리 (Fenwick Tree / Binary Indexed Tree)
      • 개념
        • 세그먼트 트리보다 단순하고 빠른 구간 합 자료구조
        • 내부적으로 이진수 LSB(가장 낮은 1비트) 기반으로 동작
      • 장점
        • 구현 매우 쉬움
        • 메모리 적음
        • O(log n)
        • prefix sum에 매우 강력
      • 단점
        • 구간 갱신 / 임의 범위 갱신 은 세그트리가 더 강력
        • 최소/최대 구하기에는 부적합

      • 코드

          class Fenwick {
      int[] fenwick;
      int n;
            
      Fenwick(int size) {
          n = size;
          fenwick = new int[n+1];
      }
            
      void update(int idx, int delta) {
          while (idx <= n) {
              fenwick[idx] += delta;
              idx += idx & -idx; // LSB 만큼 증가
          }
      }
            
      int sum(int idx) {
          int s = 0;
          while (idx > 0) {
              s += fenwick[idx];
              idx -= idx & -idx;
          }
          return s;
      }
            
      int rangeSum(int l, int r) {
          return sum(r) - sum(l-1);
      }
  }
    • B-트리 / B+ 트리 - DB, 파일 시스템 인덱스
      • B-Tree
        • 개념
        • 특징
      • B+Tree - DB 인덱스 구조
        • 개념
        • 장점
        • 사용처
  • 그래프 저장 구조
    • 인접 행렬
      • 구조
        • 2차원 배열로 표현
          matrix[u][v] = 1 또는 가중치
  matrix[u][v] = 0 (연결 없음)
      • 특징
        • 메모리 : O(V²)
        • 간선 존재 확인 : O(1)
        • 인접 노드 탐색 : O(V)
        • 방향 그래프 : 가능
        • 가중치 : 가능
        • 공간 낭비 : 그래프가 희소하면(간선이 적으면) 매우 낭비 큼
      • 장점
        • 특정 간선 존재 여부 체크 빠름 O(1)
        • 구현 단순
        • DP/플로이드 워셜 처럼 V가 작고 전처리가 많은 그래프에서 좋음
      • 단점
        • 노드 수가 10만 이상이면 메모리 폭발
        • 거의 모든 실전 문제에서는 사용 불가
      • 사용처
        • 플로이드 워셜
        • 작은 그래프 ( V ≤ 2000 )
        • 비트 마스크 DP에서 상태 인접성 저장할 때
    • 인접 리스트
      • 구조
        • 각 정점이 자신의 인접 정점 리스트를 가짐
      • 특징
        • 메모리 : O(V+E)
        • 인접 탐색 : O(연결된 간선 수) → 평균 매우 빠름
        • 희소그래프에 최적
        • 가중치 가능
        • 방향그래프 가능
      • 장점
        • 메모리 효율 최고
        • BFS/DFS/Dijkstra 등 대부분의 그래프 문제에서 표준
      • 단점
        • 간선 존재 여부 체크는 느림 : O(deg(v))
      • 사용처
        • BFS/DFS/다익스트라/MST(프림, 크루스칼) 등
    • 간선 리스트
      • 구조
        • 간선만 저장하는 형태
      • 특징
        • 메모리 : O(E)
        • 간선 순회 : O(E)
        • 인접성 탐색 : 느림
        • 가중치 가능
        • 방향 그래프 가능
      • 장점
        • 정렬이 필요할 때 최강 (크루스칼)
        • 메모리 효율 좋음
      • 단점
        • 인접 노드 탐색 분리
      • 사용처
        • 크루스칼
        • 입력이 간선 형태로 주어질 때
        • 그래프 재가공/필터링

    • 희소 그래프 / 밀집 그래프

      타입 정의 추천 구조
      희소 그래프 E ≪ V² 인접 리스트
      밀집 그래프 E ≈ V² 인접 행렬

results matching ""

    No results matching ""