자료구조 Flashcards
자료 구조
[정의] 데이터 값의 모임, 또는 데이터 간의 관계 등 자료를 컴퓨터에 저장하는 방법
[종류]
1. 선형 구조
- 배열(Array) : 동일한 크기 순서를 가지고 나열되는 집합
- 스택(Stack): 삽입/삭제가 리스트의 한쪽 끝에서만 수행(LIFO), 인터럽트 발생 시 복귀주소 저장시 용이
- 큐(Queue): 한쪽에서는 삽입, 다른 쪽에서는 삭제 작업(FIFO), 대기 행렬 처리에 주로 이용
- 리스트(List): 노드 포인터를 이용하여 연결, 삽입/삭제 작업이 용이 (연결 리스트)
2. 비선형 구조
- 트리 : 부모와 자식 계층 구조, 정점(node)과 선분(branch) 이용
- 그래프 : 노드와 간선(edge)을 하나로 모아 놓은 자료구조, 방향/무방향 그래프, DFS/BFS
[자료구조와 알고리즘 관계]
- 자료구조 : 컴퓨터에 자료를 효율적으로 저장 (스택,큐)
- 알고리즘 : 자료구조 내 기본적인 연산을 구현하기 위한 명령어 집합 (분할정복, 동적 계획법)
Array
[정의] 같은 데이터형의 요소들이 동일한 크기로 순서를 갖고 나열되어 있는 집합
[특징] 인덱스 사용, 연속 할당, 임의 접근 가능, O(1) 읽기, O(n) 삽입 삭제
[선언] String arr = new String[3], String arr = {“a”, “b”, “c”}
스택
[정의] 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료 구조
[특징] LIFO 구조(먼저 들어간 요소가 가장 나중에 나오는 구조), TOP 접근 제한
* 스택은 동일 구조/크기 자료를 정해진 방향으로만 데이터 삽입 가능
[구성요소]
- 구조 : Top (삽입, 삭제가 일어나는 리스트의 끝) Bottom (처음들어간 데이터 위치)
- 동작 : Push (Overflow→ 스택 포인터 > 스택 크기) Pop(Underflow → Top pointer 주소 = 0)
- 체크 : isFull(top >= n-1), isEmpty(top < 0)
[활용예시] 웹브라우저 방문기록, 역순문자열 만들기, 실행취소(Undo), 깊이우선 탐색(DFS)
[문제점/해결방안] Statck Point가 Stack 경계를 넘는 경우 Stack Overflow 발생 / 변수 크기 제약, Heap 기반 동적 할당
큐
[정의] 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
[특징] FIFO 구조(선입선출), 삽입:Rear(후단)쪽 삽입. 삭제:Front(선단)쪽 삭제
[구성요소] Front (자료구조 줄의 전단), Rear(자료구조 줄의 후단), enQueue(출력동작), deQueue(입력동작)
[종류]
- 선형큐 : 배열을 선형으로 사용하여 큐 구현. 문제점 많아 미사용
- 순환큐 : 배열의 끝과 시작이 이어진 것처럼 전단과 후단을 관리
- 링크드 리스트 기반 큐 : 성능은 떨어지나 공백/포화 상태 관리가 필요없음
[활용예시] 프로세스 관리(FCFS), 캐시(Cache), 너비 우선 탐색(BFS)
[문제점/해결방안] DeQueue 앞단 Front 빈공간 낭비 (원형 큐 이용), 크기 제약으로 이동 비용 발생(연결 리스트 큐 이용)
우선순위 큐
[정의] 데이터에 우선순위를 부여하여 FIFO방식이 아닌, 우선순위가 높은 데이터가 먼저 나가는 자료구조
[구현유형] Array, Linked list, Heap(Heap이 가장 합리적)
[연산]
- 삽입 : 가장 우선순위가 낮다고 가정 마지막 위치에 저장후 부모 노드와 비교 정렬 수행
- 삭제 : Root 노드 삭제, 가장 낮은 마지막 노드를 Root에 위치후 정렬 수행
환형큐
[정의] 1차원 배열을 사용하여 순차 자료구조 방식으로 큐를 구현
[특징] 더미 공간을 생성하여 원래 용량(capacity)보다 +1 만큼 증가시켜 배열을 생성
[연산]
- 삽입 : Rear쪽 삽입. 포인터 이동
- 삭제 : Front 삭제. 포인터 이동
힙
[정의] 가장 큰 키 값을 가지는 노드나 가장 작은 키 값을 가지는 노드를 빠른 시간 내에 찾아내도록 만들어진 완전 이진트리
[특징] 완전 이진트리, 유일한 키값
[시간복잡도] 힙재구성-O(logN), 평균/최악-O(NlogN)
[유형]
- 최대 힙 : Key(부모) >= key(자식) - 내림차순
- 최소 힙 : key(부모) <= key(자식) - 오름차순
다중 연결 리스트
[정의] 양방향 및 다중 방향 검색이 가능하도록 선행 노드 포인터 크기를 유연하게 변경 가능한 연결 리스트
[특징] Next/Prev노드 정보, 양방향 탐색, 검색 속도 향상, 구현 어려움
[기법] 검색,삽입,삭제
