[컴퓨터과학개론] 자료구조

추상화

공통적인 개념을 통해 같은 객체를 정의하는 것

 

자료구조

추상화로 자료의 논리적인 관계를 표현한 것

 

 

배열

동일한 변수에 동일한 자료형의 데이터를 일렬로 저장한 자료구조

원소의 논리적 순서 = 원소가 저장된 물리적 순서

인덱스(첨자): 변수에서의 데이터 위치

원소(값): 변수에 저장된 데이터 자체

 

1차원 배열: 1개의 인덱스로 데이터접근 A[i]

2차원 배열: 행과 열로 구성, 2개의 인덱스 A[i][j]

- 열우선 순서 행렬: 첫 번째 원소부터 저장

- 행우선 순서 행렬: 첫 번째 행 원소부터 저장

희소행렬: 0이 아닌 원소의 (행번호, 열번호, 값) 형태로 저장한 2차원 배열

 

연결 리스트

원소의 논리적 순서가 실제 저장된 순서와 다름

노드 = 데이터필드 + 링크 필드

데이터필드: 원소값

링크필드: 다음 원소의 노드 주소

 

스택

데이터 삽입(push)과 삭제(pop)가 한쪽 끝에서만 이루어지는 자료구조 (예. 접시 쌓기)

후입선출 (LIFO, Last In First Out)

 

큐

데이터 삽입(enqueue)과 삭제(dequeue)가 다른 끝에서 이루어지는 자료구조 (예. 줄 서기)

선입선출 (FIFO, First In First Out)

 

트리

비선형 자료구조

- 루트(root): 맨 꼭대기에 있는 하나의 노드

- 차수: 각 노드의 아래로 향하는 가지 수

- 트리의 차수: 가장 큰 차수

- 단말 노드 / 잎 노드(leaf node): 노드 차수가 0인 노드 (자식 노드가 없는 노드)

- 비단말 노드 / 내부 노드 : 루트와 잎노드를 제외한 노드들

- 레벨: 루트 노드부터 특정 노드까지의 거리 (가지의 수)

- 트리의 깊이/높이 : 루트 노드부터 가장 긴 경로의 노드 레벨 + 1

 

이진트리

모든 노드 차수가 2를 안 넘는 트리

최대 높이: 노드 개수(N)와 동일

최소 높이: [log_{2}N] + 1

 

트리 순회

전위(preorder) 순회: 루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

중위(inorder) 순회: 왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리

후위(postorder) 순회: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드

 

그래프

 

그래프 탐색