자료구조

자료구조와 알고리즘

프로그래밍은 알고리즘을 작성하고, 그에 맞는 자료구조를 선택하는 것이라 할 수 있다. 따라서 자료구조를 제대로 알고 있지 않으면 실력 있는 개발자가 되기 어려울 것이다. 개발자로서 내실을 다지기 위해 자료구조를 알아보자.

1. 자료구조(Data Structure)란?

데이터를 효율적으로 다루기 위해 데이터를 조직, 관리, 저장하는 것을 말한다.

2. 자료구조의 분류

• 단순 (Primitive) : 기본적인 데이터 타입 int, long, float, double, char, boolean 등

• 복합 (Non-Primitive)

  • 선형 (Linear): 데이터들이 선형으로 연결되어 있는 구조. 데이터 요소가 순서대로 정렬

    • 정적 자료구조(Static Data Structure) : 크기가 고정되어 있는 자료구조
      ex) 배열

    • 동적 자료구조(Dynamic Data Structure) : 크기가 바뀔 수 있는 자료구조
      ex) 연결 리스트, 큐, 스택

  • 비선형 (Non-Linear): 계층구조나 네트워크 망과 같이 데이터 요소가 비연속적으로 연결된 구조
    ex) 트리와 그래프

3. 자료구조의 종류

• 배열 (Array): 연속적인 메모리상에 동일한 데이터 타입의 요소를 일렬로 저장하는 자료 구조

  • 배열 요소는 인덱스를 사용하여 데이터에 직접 접근할 수 있다.
  • 배열은 고정된 크기를 가지는 정적 자료구조이다
  • 배열의 사이즈와 상관없이 한 요소를 인덱스로 접근할 경우 O(1)의 시간이 소요
  • 배열에서 값을 추가, 검색, 삭제할 경우 O(n)의 시간이 소요
    1) 가변 배열(Jagged Array)
    2) 동적 배열(Dynamic Array)
    3) 원형 배열(Circular Array)
    

• 연결 리스트(Linked List): 연결 리스트는 노드들로 연결된 자료구조. 노드는 데이터와 다음 또는 이전 노드를 가리키는 포인터를 갖는다.

  • 노드 추가 시 O(1)의 시간이 소요
  • 검색, 삭제 시 O(n)의 시간이 소요
  • 인덱스로 접근 시 O(1)의 시간이 소요
    1) 단일 연결 리스트: 단일 방향으로 노드를 연결하는 단순 구조. 포인터가 다음 노드를 가리킨다.
    2) 이중 연결 리스트: 이전과 다음 노드를 가리키는 포인터를 갖고 있어 양방향으로 탐색이 가능
    3) 원형 연결 리스트: 마지막 노드의 포인터가 처음 노드를 가리킨다.

• 큐(Queue): 먼저 추가된 데이타가 먼저 처리되는(FIFO, First In First Out) 자료 구조

  • 마지막(tail)에 데이타를 계속 추가하고, 제일 앞(head)에서만 데이타를 읽는다.

• 스택(Stack): 가장 나중에 추가된 데이타가 먼저 처리되는(LIFO, Last In First Out) 자료 구조. 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

  • Push: 데이터를 저장하는 것
  • Pop: 데이터를 꺼내는 것

• 트리(Tree): 하나의 부모 노드에 여러 개의 자식 노드들을 가지는 계층적 구조

  • 한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 순환(Cycle)구조를 가질 수 없다.
  • 이진 트리(Binary Tree): 자식노드가 0개 ~ 2개인 트리. 검색에 O(n)의 시간이 소요
  • 이진 탐색 트리(Binary Search Tree): 특정 노드에서 자신의 노드보다 작은 값들은 모두 왼쪽, 큰 값들은 모두 오른쪽에 위치
    • 매 검색마다 검색영역을 절반으로 줄여 O(log n)으로 검색
    • 중복값을 허락하지 않음

• 해시테이블(Hash Table): Key - Value pair를 저장하는 자료구조. 해시 함수와 버킷 배열로 구성

  • 해시 함수(Hash Function): 키를 해시 코드로 변환하는 함수
  • 버킷 배열(Bucket Array): 키-값 쌍을 저장하는 배열
  • 해시 함수를 사용하여 키를 해시 코드로 변환, 이를 인덱스로 사용하여 값을 저장
  • 키를 이용해 값을 빠르게 추가, 검색, 삭제할 수 있다. O(1)의 시간이 소요
  • C#의 Dictionary<Tkey,TValue> 클래스가 해시 테이블이다.

• 그래프(Graph): 노드(꼭지점, Vertex)와 두 노드를 잇는 선(Edge)으로 구성

  • Edge에 방향이 있나 없나에 따라서 Directed Graph, Undirected Graph로 나눌 수 있다.
  • Edge에 가중치가 있는 Weighted graph (Network)
  • 일반적으로 인접리스트(Adjacency List)나 인접 행렬(Adjacency Matrix) 등의 방법으로 표현

• 힙(Heap): 힙 속성(Heap Property)를 만족하는 트리 기반의 자료구조

  • 최대값과 최소값을 빠르게 찾아낼 수 있다. MaxHeap - 최대값 리턴, MinHeap - 최소값 리턴
  • 중복값 허용