[자료 구조] 자료 구조 정리

자료 구조

• 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다.
• 메모리 자원은 매우 한정적인데 넣어야 할 데이터는 무수히 많아서 메모리 공간을 효율적으로 사용해야 하는데 필요한 것이 자료 구조이다. -> 실행 시간의 효율성도 가져야 한다.
• 따라서 자료 구조가 갖는 장점과 한계를 잘 알고 사용하는 것이 개발자가 필수로 가져야 할 개념이다.
• 필수 자료 구조 종류

출처 : https://key-to-programming.blogspot.com/2016/01/key-to-data-structure.html

• 자료 구조 실행 시간 정리 표

자료 구조 종류

1. Array (배열)

• 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다.
• 인덱싱이 되어있어 인덱스 번호로 데이터에 접근할 수 있다.

• 사용되는 곳
  • 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용
  • 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용

2. Linked List (연결 리스트)

• 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조
• 동적인 데이터 추가/삭제에 유리하다.

• 각 요소는 Node
• 각 Node에는 key와 다음 노드를 가리키는 포인터인 next가 포함
• 첫 번째 요소는 Head
• 마지막 요소는 Tail
• 사용되는 곳
  • Alt _ Tab을 사용하여 프로그램 간 전환
  • 갤러리

위의 두 가지 자료 구조는 아래의 자료 구조들을 구현하기 위한 기본 자료 구조라고 할 수 있다.

3. Stack (스택)

• 순서가 보장되는 선형 데이터 구조
• 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO (Last In First Out)

• 사용되는 곳
  • 실행 취소
  • 수학적 표현식을 구문 분석하고 평가

4. Queue (큐)

• 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out)

• 사용되는 곳
  • 멀티스레딩에서 스레드를 관리
  • 대기열 시스템

5. Hash Table (해시 테이블)

• 해시 함수를 사용하여 변환된 값을 index로 삼아 key와 value르 저장하는 자료 구조.
• 데이터의 크기에 관계 없이 삽입 및 검색에 매우 효율적

• 보통 테이블 내에 더 작은 서브그룹인 '버킷(Bucket)'과 'key/value' 쌍을 저장한다.
  • 단, 충돌이 자주 일어날 수 있으며 이를 위해 다양한 방법으로 해시 함수를 개선하거나 해시 테이블의 구조 개선의 방법이 사용된다.
• 사용되는 곳
  • 데이터베이스 인덱스 구현
  • 사용자 로그인 인증
  • 'set' 데이터 구조 구현

6. Graph (그래프)

• nodex/vertices(노드) 사이에 edge(선)가 있는 컬렉션
• directed(방향) 그래프는 일방통행
• undirected(방향 없는) 그래프는 양방향

• 사용되는 곳
  • 소셜 미디어 네트워크를 나타내는 데 사용
  • 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용
  • GPS에서 위치와 경로를 나타내는 데 사용

7. Tree (트리)

• 그래프가 계층적 구조를 가진 형태
• 최상위 노드(루트)를 가지고 있음
• 상위 노드를 부모(parent) 노드, 하위 노드 자식(child) 노드라 한다.
• 아래 사진에서 depth를 level,

• 사용되는 곳
  • Binary Tree (이진 트리)
  • Binary Search Tree (이진 검색 트리)
  • Heap (힙)

8. Heap (힙)

• Complete Binary Tree (완전 이진 트리) 이다.
  • 완전 이진 트리 마지막 레벨은 왼쪽부터 채워져야 한다. 마지막 레벨을 제외한 노드는 다 채워져야 한다.
• 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같
  • 루트 노드의 키 값이 트리의 최솟값
• 최대 힙 : 부모의 키 값이 자식의 키 값보다 크거나 같다
  • 루트 노드의 키 값이 트리의 최댓값

• 사용되는 곳
  • 힙 정렬 알고리즘
  • 우선 순위 큐

 

 

다음 게시글 알고리즘 정리

https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC

[알고리즘] 알고리즘 정리

참고 자료

https://bnzn2426.tistory.com/115