자료구조(Data Structure)

자료구조(Data Structure)

• 데이터를 저장하는 방식
• 일련의 자료들을 조직하고 구조화하는 것
• 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 중요하다.

📋 선형 자료구조

• 자료를 구성하는 데이터를 순차적으로 나열시킨 형태를 의미한다.
• 자료를 저장하고 꺼내는 것에 중점을 맞춘다.
• 종류 : 배열, 연결 리스트, 스택, 큐, 데크
• 자료탐색법 종류: 순차 탐색, 이분 탐색

1. 배열(Array)

: 데이터가 순차적으로 저장된 것을 말한다. 어느 자리에 있는지 번호(index) 로 지정이 가능하다. (인덱스는 0부터 시작한다.)

2. 연결 리스트(Linked list)

• 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조
• 기억 공간이 연속적이지 않아도 된다.
• 중간 노드의 연결이 끊기면 다음 노드를 찾기 어렵다.
• 연결을 위한 포인터를 저장할 공간이 별도로 필요하기 때문에 효율이 좋지 않다.
• 종류: 단순 연결 리스트, 이중 연결 리스트 등

3. 스택(Stack)

• 리스트의 한 쪽 끝으로만 자료의 삽입(push)과 삭제(pop)이 이루어지는 자료구조
• LIFO(Last In First Out)

4. 큐(Queue)

• 한 쪽에서는 삽입, 다른 한 쪽에서는 삭제 작업이 이루어지는 자료구조
• FIFO(First In First Out)
• 운영체제 작업 스케줄링에 사용된다.

5. 데크(Dequeue)

• 리스트의 양 쪽에서 삽입, 삭제가 모두 가능한 자료구조

📋 비선형 자료구조

• 선형 자료구조가 아닌 모든 자료구조
• 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것을 의미한다.
• 자료의 표현에 중점을 맞춘다.
• 자료들 간 앞뒤 관계가 '1:다' 혹은 '다:다'의 관계를 갖는다.

1. 트리(Tree)

• 노드(node)들과 선분(branch)으로 구성된 사이클을 이루지 않는 그래프를 의미한다.

• 용어

  • 노드(node) : 그래프의 정점

    • 루트 노드 : 트리의 기준
    • 부모 노드 : 어떤 노드에서 자신과 인접한 노드들 중 루트 노드로 향하는 노드
    • 자식 노드 : 어떤 노드에서 자신과 인접한 노드들 중 루트 노드의 반대로 향하는 노드
    • 단말 노드 : 자식 노드가 존재하지 않는 노드
    • 형제 노드 : 부모 노드가 같은 노드

  • 가지(branch) : 그래프의 간선. 트리에서는 모두 양방향이다.

  • 차수(degree) : 자식 노드의 개수

  • 길이(length) : 임의의 두 노드를 시작 노드, 도착 노드로 하는 경로에서 거치게 되는 노드 수

    • 깊이(debth) : 루트에서 해당 노드까지의 길이
    • 레벨(level) : 깊이가 같은 노드의 집합
    • 높이(height) : 가장 깊이가 깊은 단말 노드까지의 길이

• 트리의 종류

  • 이진 트리 : 모든 노드의 차수가 2 이하인 트리
  • 전 이진 트리 : 모든 노드의 차수가 0 또는 2인 트리
  • 포화 이진 트리 : 모든 단말 노드의 레벨이 동일한 이진 트리로, 단말 노드가 아닌 노드는 모두 자식 노드가 2개
  • 완전 이진 트리 : 마지막 레벨을 제외한 각 레벨이 빠짐없이 채워져있고, 마지막 레벨에서는 중간에 빈 칸 없이 왼쪽부터 노드들로 채워져 있는 이진트리

• 순회 알고리즘

  1. 전위 순회
  • 탐색 순서: root → left → right
  • 위 그래프 이미지에서 순서를 따지면 ABCDEF가 된다.
  2. 중위 순회
  • 탐색 순서: left → root → right
  • 위 그래프 이미지 기준으로 CBDAEF
  3. 후위 순회
  • 탐색 순서: left → right → root
  • 위 그래프 이미지 기준으로 CDBFEA

2. 그래프(Graph)

• 정점(vertex)와 간선(edge)로만 이루어진 자료구조

• 용어

  • 정점(vertex) : 연결점. 여러 가지 특성을 가질 수 있는 객체
    • 고립 정점 : 간선이 단 하나도 연결되지 않은 정점
  • 간선(edge) : 두 정점을 연결하는 연결선. 두 정점 간의 관계를 의미한다.
    • 단방향 간선
    • 양방향 간선
    • 자기 간선 : 자기 자신을 연결하는 간선
    • 다중 간선 : 동일한 다른 접점과 여러 간선이 연결되는 간선
  • 인접 : 두 정점이 하나의 간선으로 연결되어 있을 때 두 정점이 인접하다고 한다.
  • 차수(degree) : 정점에 연결된 간선의 수
  • 경로(path) : 어떤 한 정점에서 다른 하나의 정점으로 가는 길. 동일한 정점으로도 가능하다.
    • 길이(length) : 어떤 경로에서 시작 정점에서 도착 정점까지 거쳐야 하는 정점의 수
    • 단순 경로 : 경로에서 시작, 끝 정점을 제외한 방문하는 모든 점이 다른 경로
      • 사이클(cycle) : 시작 정점과 끝 정점이 같은 단순 경로

---

참고

• 리브레 위키
• 이진 트리 참고 블로그