[자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

 

1. 선형 리스트 (Linear List)

• 설명: 데이터를 연속된 메모리 공간에 저장하며, 순서를 보장하는 자료구조.
• 특징:
  • 인덱스를 통해 O(1) 시간 복잡도로 접근.
  • 삽입/삭제는 O(n)로 비효율적.
• 필수 알고리즘:
  1. 이분 탐색 (Binary Search):
     • 정렬된 리스트에서 O(log n) 시간 복잡도로 값을 탐색.
  2. 슬라이딩 윈도우 (Sliding Window):
     • 고정 크기의 연속 부분 리스트 처리.

 

자료 출처: https://velog.velcdn.com/images/hyhy9501/post/1c9f28a0-8e27-4aa2-9f6e-e89bb79ed2b4/image.png

 

---

 

2. 연결 리스트 (Linked List)

• 설명: 노드(Node)와 포인터로 구성된 비연속적 메모리 저장 구조.
• 특징:
  • 삽입/삭제가 O(1)로 빠름.
  • 탐색은 O(n)으로 느림.
• 필수 알고리즘:
  1. 역순 연결 리스트 (Reverse Linked List):
     • 연결 리스트를 뒤집음.
  2. 사이클 검출 (Cycle Detection):
     • 플로이드의 토끼와 거북이 알고리즘 사용.

 

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

 

• 정의:
  마지막 노드가 첫 번째 노드를 가리키도록 연결된 리스트.
• 특징:
  • 순환 구조: 노드 끝에서 다시 시작으로 돌아옴.
  • 종료 조건: 명확한 조건 없이 탐색하면 무한 순환 가능.
  • 삽입/삭제: 리스트 어디서나 삽입과 삭제가 용이.
• 단점:
  • 순환 구조 때문에 리스트의 끝을 감지하기 어려움.
• 활용 사례:
  • 자원 관리, 라운드 로빈 스케줄링.

 

 

 

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

• 정의:
  • 기존 단순, 원형 연결 리스트의 단점인 단방향 흐름을 2개의 링크 필드를 이용하여 양방향으로 움직일 수 있게 만든 것이 이중 연결 리스트
  • 각 노드가 데이터, 다음 노드의 포인터(next), 그리고 **이전 노드의 포인터(prev)**를 가지는 리스트.
• 특징:
  • 양방향 탐색 가능: 앞뒤로 자유롭게 이동할 수 있음.
  • 삽입/삭제 용이: 특정 노드 위치에서 삽입/삭제가 간단.
  • 단점: 추가 포인터(prev)가 필요하므로 메모리 사용량 증가.
• 활용 사례:
  • 양방향 데이터 흐름을 다루는 시스템.

 

 

---

 

3. 스택 (Stack)

• 설명: LIFO(Last In First Out) 구조의 자료구조.
  
  • LIFO (선입후출)
• 특징:
  • 삽입/삭제 연산이 O(1).
• 필수 알고리즘:
  1. 괄호 유효성 검사:
     • 올바른 괄호 쌍을 확인.
  2. DFS (Depth First Search):
     • 스택 기반의 깊이 우선 탐색.

 

 

---

 

4. 큐 (Queue)

• 설명: FIFO(First In First Out) 구조의 자료구조.
• 특징:
  • 삽입은 뒤쪽, 삭제는 앞쪽에서 이루어짐.
• 필수 알고리즘:
  1. BFS (Breadth First Search):
     • 너비 우선 탐색.
  2. 라운드 로빈 스케줄링:
     • 프로세스 스케줄링.

 

4.1 원형 큐(Circular Queue)

 

• 정의:
  큐의 끝이 다시 시작 부분과 연결된 순환 구조의 큐.
• 특징:
  • 일반 큐와 달리 공간 낭비를 줄임.
  • 빈 공간이 있으면 공간을 재활용 가능.
• 단점:
  • 순환 구조이므로 포인터 관리가 필요.
• 활용 사례:
  • 네트워크 버퍼 관리, 데이터 스트리밍.

 

---

 

5. 데크 (Deque)

• 설명: 양쪽 끝에서 삽입/삭제가 가능한 자료구조.
• 특징:
  • 스택과 큐의 특성을 모두 가짐.
• 필수 알고리즘:
  1. 슬라이딩 윈도우 최대값:
     • O(n)으로 최대값 계산.
  2. LRU 캐시 구현:
     • 최근 사용되지 않은 데이터를 삭제.

 

 

자료 출처: https://img1.daumcdn.net/thumb/R800x0/?scode=mtistory2&fname=https%3A%2F%2Ft1.daumcdn.net%2Fcfile%2Ftistory%2F9955354C5C4723F11C

 

 

---

 

6. 이진 트리 (Binary Tree)

• 설명: 각 노드가 최대 두 개의 자식을 가지는 계층적 자료구조.
• 특징:
  • 전위, 중위, 후위 순회 가능.
• 필수 알고리즘:
  1. 트리 순회:
     • 전위, 중위, 후위 탐색.
  2. 최대 깊이 계산:
     • 트리의 깊이 계산.

 

 

6.1 이진 트리 종류

6.1.1 정 이진 트리(Full Binary Tree)

 

• 정의:
  모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리.
• 특징:
  • 리프 노드를 제외한 모든 노드는 반드시 2개의 자식을 가짐.
  • 트리의 깊이가 hhh일 때, 최대 노드 수는 2h+1−12^{h+1} - 12h+1−1.

 

 

 

 

6.1.2 포화 이진 트리(Perfect binary tree)

• 정의:
  모든 리프 노드가 같은 깊이에 있고, 모든 노드가 2개의 자식 노드를 가진 이진 트리.
• 특징:
  • 트리의 깊이가 hhh일 때, 노드의 개수는 2h+1−12^{h+1} - 12h+1−1.
  • 모든 레벨이 가득 채워짐.

 

 

 

6.1.3 완전 이진 트리(complete binary tree)

 

• 정의:
  모든 레벨이 가득 차 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 차례대로 노드가 채워진 이진 트리.
• 특징:
  • 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.
  • 힙(Heap) 구현에 자주 사용됨.

 

 

6.1.4 편향 이진 트리(skewed binary tree)

 

• 편향 이진 트리 정의
  • 왼쪽 편향 이진 트리 (Left-Skewed Binary Tree):
    모든 노드가 왼쪽 자식만 가지는 트리.
  • 오른쪽 편향 이진 트리 (Right-Skewed Binary Tree):
    모든 노드가 오른쪽 자식만 가지는 트리.
• 특징
  • 노드 구조:
    • 각 노드는 한쪽 방향(왼쪽 또는 오른쪽)으로만 자식을 가지며, 다른 한쪽은 비어 있습니다.
  • 효율성 문제:
    • 높이가 nnn인 경우, 트리의 성능이 **연결 리스트(Linked List)**와 비슷해짐.
  • 검색, 삽입, 삭제의 시간 복잡도가 최악의 경우 O(n)O(n)O(n)로 비효율적.
• 특수한 경우:
  • 데이터가 이미 정렬된 순서로 삽입될 때 발생.
  • 예: 이진 탐색 트리(BST)에서 정렬된 데이터를 삽입하면 편향 트리가 생성됨.

 

 

---

 

7. 트리 (Tree)

• 설명: 계층적으로 데이터를 저장하는 자료구조.
• 특징:
  • 루트 노드에서 시작하여 자식 노드로 확장.
• 필수 알고리즘:
  1. LCA (Lowest Common Ancestor):
     • 최소 공통 조상 찾기.
  2. 트리 기반 DP:
     • 구간 연산 최적화.

 

 

자료 출처: https://velog.velcdn.com/images/eunsung-dev/post/75d09e4c-50f9-456d-8afd-70de9235b5bd/image.jpeg

 

7.1 . 트리 & 이진트리 주요 차이점

 

특징트리(Tree)이진 트리(Binary Tree)

노드의 자식 수	제한 없음	최대 2개의 자식 노드 (왼쪽, 오른쪽)
구조의 제약	자유로운 계층 구조	고정된 구조 (이진)
활용 사례	조직도, 파일 시스템, XML 구조 등	이진 탐색 트리, 힙, 표현식 계산 등
복잡도	다양한 변형 구조로 유연함	엄격히 구조화되어 알고리즘 설계가 간단

 

 

---

 

8. 그래프 (Graph)

• 설명: 정점(Vertex)과 간선(Edge)으로 구성된 네트워크 구조.
• 특징:
  • 방향, 무방향, 가중치 그래프 존재.
• 필수 알고리즘:
  1. DFS, BFS:
     • 그래프 탐색.
  2. 다익스트라 알고리즘:
     • 최단 경로 계산.

 

 

 

---

 

9. 해시 테이블 (Hash Table)

• 설명: 키-값 쌍을 저장하며, 해시 함수로 빠르게 검색.
• 특징:
  • 평균 O(1)의 검색, 삽입.
• 필수 알고리즘:
  1. 충돌 해결:
     • 체이닝, 오픈 어드레싱.
  2. Anagram 검출:
     • 문자열 빈도 계산.

 

 

 

---

 

10. 힙 (Heap)

• 설명: 우선순위 큐를 구현하는 완전 이진 트리.
• 특징:
  • 최소 힙: 루트는 최솟값.
  • 최대 힙: 루트는 최댓값.
• 필수 알고리즘:
  1. 힙 정렬:
     • O(n log n) 정렬.
  2. 다익스트라 알고리즘:
     • 최소 힙을 이용한 최단 경로.

 

 

---

 

11. 트라이 (Trie)

• 설명: 문자열 검색에 특화된 트리 구조.
• 특징:
  • 각 노드가 문자열의 한 문자를 저장.
• 필수 알고리즘:
  1. 문자열 검색:
     • 접두사 기반 탐색.
  2. 자동 완성:
     • 입력한 문자열로 가능한 단어 추천.

 

 

---

 

12. 세그먼트 트리 (Segment Tree)

• 설명: 배열의 구간 연산(합, 최솟값 등)을 빠르게 처리.
• 특징:
  • 쿼리와 업데이트가 O(log n).
• 필수 알고리즘:
  1. 구간 합 쿼리:
     • 특정 구간의 합 계산.
  2. 최소/최댓값 쿼리:
     • 구간 내 최소값 또는 최대값 찾기.

 

---

 

13. 유니온-파인드 (Union-Find)

• 설명: 상호 배타적 집합 관리 자료구조.
• 특징:
  • 경로 압축으로 집합을 효율적으로 관리.
• 필수 알고리즘:
  1. Union 연산:
     • 두 집합 병합.
  2. Find 연산:
     • 특정 요소의 집합 찾기.