자료구조란?

“데이터를 효율적으로 사용할 수 있도록 정리하는 방법”

→ 주어진 메모리 공간을 효율적으로 사용해야 하는데 필요하며, 실행시간도 고려함

• ex) 메모리 : 책장 / 데이터 : 책

자료구조 + 알고리즘 = 프로그램

일반적으로 자료구조가 결정되면, 그에 맞는 알고리즘은 명확해진다.

따라서 자료구조의 선택 → 효율적인 알고리즘의 선택으로 볼 수 있으며

알고리즘 + 자료구조 = 프로그램으로 귀결된다.

필수 자료구조

Array

• 동일한 타입
• 고정된 크기
• index 번호로 접근이 가능하다
• heap, hashTable, vector 등 데이터 구조를 구축하기 위한 기본 블록으로 사용됨
• bubble, merge, quick 등 다양한 정렬 알고리즘에서 사용

LinkedList

• 각 데이터가 순서를 가지고 연결된 순차적 구조
• 동적인 데이터 추가/삭제에 유리함
  • 각 요소 Node
  • Node 에는 Key 와 다음을 가르키는 pointer(next) 가 포함되어있음
  • 첫번째 요소는 head, 마지막은 tail

Stack

• 순서가 보존되는 선형 데이터 구조
• 마지막 부터 처리하는 LIFO (Last In First Out - 후입선출)
• ex) 실행취소, 계산기구현, 재귀프로그래밍

Queue

• 먼저 입력된 요소를 처리하는 FIFO (Fist In First Out - 선입선출)
• ex) 멀티스레딩에서 스레드관리, 대기열 시스템

HashTable

• 해시함수를 사용하여 변환한 값을 index 로 삼아 key 와 value 를 저장하는 자료구조
  • key : hash function 의 input
  • hash function : key를 고정된 길이의 hash 로 변경해주는 역할
  • value : 저장소(버킷, 슬롯)에 최종 저장되는 값으로, hash와 매칭되어 저장됨 → hash 는 색인 또는 인덱스, hash function 은 key를 hash 로 만들어주는 함수, hashTable 은 hash를 주소로 삼아 데이터를 저장하는 자료구조
• 해시충돌 : 서로 다른 key 가 고정된 길이의 hash 로 변환되다보면 겹치는 경우도 있다.
• 장점
  • 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적 O(1)
• 단점
  • 해시 충돌이 발생(개방주소법, 체이닝 기법으로 해결해야함)
  • 순서/관계가 있는 배열에 어울리지 않음
  • 공간 효율성이 떨어짐. 공간을 미리 셋팅해야하며, 채워지지 않는경우도 발생함
  • Hash function 의존도가 높다.

Graph

• Node 사이에 Edge 가 있는 collection
• directed(방향) 그래프는 일방통행
• undirected(무방향) 그래프는 양방향
• ex) 소셜 미디어 네트워크, 위치/경로 나타내는데 사용

Tree

• 그래프가 계층적 구조를 가진 형태
• 최상위 노드(루트)를 가지고 있음
• ex) 이진트리, 이진검색트리, 힙

Heap

• 이진트리
• 최소 힙 : 부모의 키 값이 자식의 키값보다 작거나 같다 → 루트가 최소
• 최대 힙 : 부모의 키 값이 자식의 키값보다 크거나 같다 → 루트가 최대
• ex) heap 정렬, 우선순위 큐(priorityQueue)