Cs/알고리즘&자료구조
자료구조[Data Structure]
ukkkk7
2023. 11. 5. 21:03
728x90
반응형
자료구조란?
데이터 값의 모임. 각 원소들이 정의된 규칙에 의해서 나열되어 있고 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것
목적
데이터를 효율적으로 저장, 관리하여 메모리를 효율적으로 사용하기 위해
- 실행시간 단축, 메모리 용량 절약
자료구조와 알고리즘
알고리즘 = 문제 해결을 위한 방법
자료구조 = 효율적인 알고리즘을 사용할 수 있게 해주는 수단
자료구조의 종류
선형 구조: 순차적으로 나열 되어있는 형태의 구조
비선형 구조: 나열되어 있지는 않지만 하나의 자료가 다른 자료와 연결된 구조
파일 구조: 같은 성질을 가지는 레코드들끼리 모아 놓은 파일을 일정한 규칙에 따라 저장하는 것
필수 자료구조
1. Array(배열)
- 동일한 타입의 데이터 저장 , 고정된 크기
- 인덱싱 되어있음
- 장점: 데이터에 빠르게 접근 가능
- 단점: 삽입, 삭제 연산에서 다른 데이들을 이동해야 하기 때문에 시간이 오래걸림
2. Linked List(연결 리스트)
- 연결 리스트(Liked List:연결 목록)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
- 장점: 새로운 요소의 추가 및 삭제가 용이하고 메모리 크기가 동적이다.
- 단점: 데이터 탐색의 경우 원하는 데이터를 한번에 찾아낼 수 없고 리스트를 전부 탐색해야 함
3. Stack(스택)
- 한 방향으로만 입력, 저장, 삭제가 가능하고 중간에 값을 끼워 넣어 저장할 수 없다.
- LIFO구조로 가장 마지막에 들어온 데이터가 가장 먼저 리턴
- 장점: 빠른 런타임과 동적인 메모리 크기
- 단점: 가장 최신 요소만 가져옴 = 중간에 위치한 데이터의 접근이 어렵다.
4.Queue(큐)
- 양방향에서 입력과 출력이 이루어진다.
- FIFO구조로 가장 먼저 들어온 데이터가 가장 먼저 출력된다.
- 장점: 스택과 동일
- 단점: 스택과 동일
5. Hash Table
- 해시함수를 사용하여 변환한 값을 색인(index)삼아 key, value를 저장하는 자료구조
- 장점: 데이터의 크기에 관계없이 삽입 및 검색에 효율적
- 단점: 충돌이 일어날 수 있다(입력된 키의 해시값이 이미 데이터가 저장된 버킷을 가리킬 수 있음)
6. Graph(그래프)
- 정점(Vertex)과 간선(edge)로 이루어진 자료구조
- directed : 방향그래프는 일방통행
- undirected : 무방향 그래프는 양방향 통행
- 장점: 복잡한 상호관계 표현 가능
- 단점: 너무 복잡할 경우 연산 속도가 느림
7. Tree(트리)
- 최상위 노드(루트)를 갖고 계층적 구조를 이룬 형태
- 상위 노드(parent), 하위 노드(child)
- 장점: 데이터를 효율적으로 검색할 수 있음
- 단점: 삽입, 삭제시 많은 수의 노드를 거쳐야 하기 때문에 시간이 오래걸림
8. Heap(힙)
- 힙은 완전 이진 트리의 형태로 만들어진 자료구조
- 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- 최소 힙: 부모 노드의 키 값이 자식 노트의 키 값보다 작거나 같은 완전 이진 트리
- 장점: 최대 최솟값을 빠르게 찾을 수 있음
- 단점: 특정 값을 검색하는 것은 느림
틀린 부분이 있다면 댓글로 알려주시면 감사하겠습니다!
Refereces
728x90
반응형