01. 자료구조 요약 정리

1. 자료구조의 분류 체계

 

* 자료구조의 소요 시간표( Big-O 표기법)

 

성능 최적화의 핵심

시간 복잡도: 효율적인 알고리즘을 사용해서 작업을 얼마나 빠르게 처리할 수 있는지. 예를 들어,

                     리스트 순차 탐색을 최적화하거나 불필요한 반복을 줄이는 방법.

공간 복잡도: 메모리를 얼마나 효율적으로 사용할 것인지. 불필요한

                     데이터나 객체를 생성하지 않도록 관리하는 방법.

코드의 가독성: 성능을 추구하더라도 코드가 지나치게 복잡해지면 나중에 다른 사람이

                         이해하기 어려워지니까, 항상 가독성과 유지보수성도 중요해.

 

 

2. 자료 구조 요약 정리

1) Array (배열)

• 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다
• 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있다.
• 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용
• int a[] = {1, 2, 3} 그림

 

2) Linked List (연결리스트)

• 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조
• 동적인 데이터 추가/삭제에 유리하다.
• 각 Node에는key와 다음 노드를 가리키는 포인터인next가 포함

 

3) Stack

• 순서가 보존되는 선형 데이터 구조
• 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO (Last In First Out)
• 재귀 프로그래밍에서 함수 호출을 구현

4) Queue

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

5)  Hash Table

• 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
• 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적
• 사용자 로그인 인증, SET 데이터 구조 구현
• 보통 테이블 내에 더 작은 서브그룹인버킷(bucket)에키/값(key/value) 쌍(pair)을 저장한다.

 

6) Graph

• nodes/vertices(노드) 사이에edge(엣지)가 있는 collection
• directed(방향) 그래프는 일방통행, undirected(무방향) 그래프는 양방향
• 소셜 미디어 네트워크, 검색 엔진에 의해 웹 페이지 및 링크, GPS에서 위치와 경로를 나타내는 데 사용

 

7) Tree

• 그래프가 계층적 구조를 가진 형태
• 최상위 노드(루트)를 가지고 있음
• 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다.
• 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 한다.
• 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있다.
• 자식이 없는 노드는 leaf 라고 한다.

 

8) Heap

• Binary Tree(이진트리)
• 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다. 루트 노드의 키 값이 트리의 최솟값
• 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다. 루트 노드의 키 값이 트리의 최댓값