🧬 자료구조(1) - array, list, stack, queue, heap, tree, graph..

필수 자료구조 8개

Array, Linked List, Stack, Queue, Hash Table, Graph, Tree, Heap

1. Array List (배열)

입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조

• stack
• 배열의 크기는 처음 생성할 때 정하며, 이후에는 변경할 수 없다.
• 메모리 상에서 연속적으로 저장되어 있는 특징을 가지기 때문에 index를 통한 접근이 용이하다.
  • 장점: 인덱스를 통해 데이터에 빠른 접근이 가능하다.
  • 단점: 삽입/삭제 연산에서 다른 데이터들을 이동시켜야 하기 때문에 시간이 오래 걸린다.
• 시간 복잡도
  • 탐색
    • 접근하고자 하는 인덱스를 알고 있을 경우: O(1)
    • 인덱스 모르고 있을 경우: O(n) → 탐색 시간 소요
  • 삽입/삭제
    • 배열의 처음 또는 중간에 할 경우: O(n)
      삽입 지점 이후의 데이터를 옮겨야 하기 때문에 전체 탐색해야 함
    • 배열의 끝에 할 경우: O(1)

---

2. Linked List (연결 리스트)

여러 개의 노드들이 순차적으로 연결된 형태의 자료구조

• heap
• 첫번째 노드를 head, 마지막 노드를 tail 이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다. (순서 X)
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
• Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성이 드러난다.
• 시간 복잡도
  • 탐색
    • O(n) (처음부터 순회해야하므로쿠키..)
  • 삽입/삭제 → 삽입과 삭제 자체는 O(1)..
    • 연결리스트의 처음에 삽입/삭제: O(1)
    • 연결리스트의 중간에 삽입/삭제: O(n) → 탐색 시간 소요
    • 연결리스트의 끝에 삽입/삭제
      • 끝을 가리키는 별도의 포인터(tail)를 갖는 경우: O(1)
      • 끝을 가리키는 별도의 포인터가 없는 경우: O(n) → 탐색 시간 소요

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

연결 리스트와 다르게 prev, next node를 모두 가지고 있어 전/후로 탐색이 가능한 자료구조

• 장점: 단순 연결 리스트에서는 최악의 경우 n번을 탐색해야 하지만, 이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝다면 역방향으로 탐색이 가능하기 때문에 (prev 타고..타고..) 탐색 시간을 줄일 수 있다.
  

---

배열 vs 연결 리스트

배열의 장단점

• 장점
  • 인덱스를 통한 빠른 접근 가능
• 단점
  • 삽입/삭제가 오래 걸림 → 다른 데이터의 인덱스를 모두 이동시켜야하기 때문에..
  • 배열 중간에 있는 데이터가 삭제되면 공간 낭비가 발생함
• 용도
  • 빠른 접근 요구 + 데이터의 삽입, 삭제 적을 때

연결리스트의 장단점

• 장점
  • next node를 가지고 있기 때문에 삽입과 삭제 시 용이함
• 단점
  • 별도의 인덱스가 없기 때문에 임의 접근이 불가능하여 처음부터 탐색을 진행해야 함 → 탐색 시간 소요
• 용도
  • 삽입과 삭제 연산이 잦음 + 검색 빈도가 적을 때

---

3. Stack (스택)

순서가 보존되는 선형 자료구조

• LIFO(Last In First Out) 구조
• 함수 호출 등 스택 메모리 구조에 사용된다.
• 같은 구조의 같은 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
• top으로 정한 곳을 통해서만 접근 가능하다.
  스택의 top은 가장 마지막에 쌓인 data 위치!!!!
• 삭제는 top을 통해서만 가능하다.
• push나 pop을 할 때 해당 값의 위치를 알고 있어야 하는데, 스택 포인터(sp)가 위치를 기억한다. 처음 기본 값은 -1
• 스택의 활용 예시
  • 웹 브라우저 방문기록 (뒤로가기): 가장 나중에 열린 페이지부터 다시 보여줌
  • 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력
  • 실행 취소 (undo): 가장 나중에 실행된 것부터 실행 취소
  • 후위 표기법 계산
  • 재귀 함수(recursive call)

---

4. Queue (큐)

순서가 보존되는 선형 자료구조

• FIFO(First In First Out) 구조
• Java Collection에서 Queue는 인터페이스다.
• 가장 첫 원소를 front, 끝 원소를 rear라고 한다.
• front와 rear로만 접근 가능
  • 데이터를 넣고 뺄 때 해당 값의 위치를 기억해야 함(스택 포인터와 같은 역할)
• 큐의 활용 예시
  • 대기 번호표
  • 물품 진열
  • BFS 구현
  • 프린터 출력 처리
  • 콜센터 고객 대기시간

---

5. Heap (힙)

완전 이진트리(Binary Tree)의 일종

• 여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료 구조
• 우선순위 큐를 위해 만들어진 자료구조
  • 우선순위 큐?
    • 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 삭제!
    • CPU 작업 스케줄링, 시뮬레이션 시스템에서 사용
• 시간복잡도: O(logn)
• 힙을 저장하는 표준적인 자료구조는 배열
• 중복 값을 허용한다.
• 반 정렬 상태를 유지한다.
• 힙 종류
  • 최대 힙(max heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
    • 부모 key ≥ 자식 key
  • 최소 힙(min heap)
    • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
    • 부모 key ≤ 자식 key
• 힙 연산
  • 삽입
    • 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
    • 새로운 노드를 부모 노드들과 교환
  • 삭제
    • 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됨
      (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것!)
    • 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
    • 힙을 재구성함

---

6. Tree (트리)

노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조.
= 그래프가 계층적 구조를 가진 형태

• 사실 트리는 그래프의 일종이다.
• 트리 내에 다른 하위 트리가 있고, 그 하위 트리 안에 또 다른 하위 트리가 있는 재귀적 자료구조이다.
• 단순 순환(loop)를 가지지 않고, 연결된 무방향 그래프 구조이다.
• 최상위 노드(루트)를 가진다
• 상위 노드를 부모(parent)노드, 하위 노드를 자식(child)노드라 한다.
  • 장점: 데이터를 효율적으로 검색할 수 있다.
  • 단점: 삽입, 삭제 시 많은 수의 노드를 이동해야하기에 시간이 오래 걸린다.
• 트리의 활용 예시
  • 컴퓨터의 directory 구조
  • 힙도 트리로 된 자료구조
  • 데이터베이스 인덱싱
    ex) B-Tree, B+Tree, AVL-Tree..
  • Trie: 사전, 전화번호부?

---

7. Graph (그래프)

정점(Node or Vertext)과 객체를 연결하는 간선(Edge)으로 이루어진 비선형 자료구조

• 그래프 G를 G=(V,E)로 정의하는데, V는 정점의 집합, E는 간선들의 집합을 의미한다.
• 트리는 그래프의 일종이지만 그래프는 트리와 달리 정점마다 간선이 존재하지 않을 수도 있으며, 루트 노드와 부모 노드, 자식 노드의 개념이 존재하지 않는다.
• 그래프의 활용 예시
  • 지하철 노선도 최단 경로
  • 도로
  • 선수 과목

그래프 구현 방법

그래프는 인접 행렬 또는 인접 리스트 로 구현할 수 있다.

1. 인접 행렬
인접 행렬이란 그래프의 정점을 2차원 배열로 만든 것이다.
정점 간에 직접 연결되어 있다면 1 , 아니라면 0 을 저장한다.

장점

• 2차원 배열에 모든 정점의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결을 조회할 때는 O(1)O(1) 의 시간 복잡도를 가진다.
• 인접 리스트에 비해 구현이 쉽다.

단점

• 모든 정점에 대해 간선 정보를 입력해야 하므로 인접 행렬을 생성할 때는 O(n2)O(n2) 의 시간 복잡도가 소요된다.
• 항상 2차원 배열이 필요하므로 필요 이상의 공간이 낭비된다.

2. 인접 리스트
인접 리스트는 그래프의 노드를 리스트로 표현한 것이다. 주로 정점의 리스트 배열을 만들어서 관계를 설정한다.

장점

• 정점들의 연결 정보를 탐색할 때 O(n) 시간 복잡도가 소요된다. (n 은 간선의 갯수)
• 필요한 만큼 공간을 사용하기 때문에 인접 행렬에 비해 상대적으로 공간의 낭비가 적다.
  

단점

• 특정 두 정점이 연결되어 있는지 확인하기 위해서는 인접 행렬에 비해 시간이 오래 걸린다.
• 구현이 인접 행렬에 비해 어렵다.

그래프 탐색
1. 깊이 우선 탐색 (DFS)
갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회한다.
주로 재귀 호출과 스택을 사용해서 구현한다.

2. 너비 우선 탐색 (BFS)
시작 정점을 방문한 후, 시작 정점에 인접한 모든 정점을 방문한다.
인접한 정점을 방문한 뒤, 다시 해당 정점의 인접한 정점을 방문하며 그래프를 순회한다.
주로 큐와 반복문을 사용해서 구현한다.

---

8. Hash Table (해시 테이블)

(key, value)로 데이터를 저장하는 자료구조

• key값에 해시함수를 적용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조이다.
• 장점
  • 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적
  • 빠른 데이터 검색 가능
• 단점
  • 충돌이 발생하는 경우 성능 저하
    • 해결 방안 알아보기.......
• 시간 복잡도
  • O(1)
  • index 충돌이 발생한 경우: O(n)