[알고리즘] 선형 구조와 비선형 구조

자료구조란?

자료구조는 데이터를 컴퓨터의 기억장치에 효율적으로 저장하고, 처리하고, 관리하기 위한 방법을 의미한다. 우리가 알고리즘을 사용할 때 빠른 계산과 정렬, 검색을 위해 어떤 형태로 데이터를 저장할지가 매우 중요하다. 이러한 자료 구조는 크게 선형 구조와 비선형 구조로 나뉜다. 자료구조는 검색 엔진, 게임, 네비게이션, 운영체제 등 실생활 속 여러 기술에 폭넓게 활용된다.

 

선형 구조

1. 배열

배열은 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 가지는 집합이다. 

- 정적인 자료구조로 기억장소의 추가가 어렵다.

- 데이터 삭제 시 데이터가 저장되어있던 기억장소는 빈 공간으로 남아 메모리 낭비 발생

- 인덱스를 이용하여 데이터에 접근한다. (O(1))

- 인덱스의 개수에 따라 n차원 배열이라 부른다. 

- 삽입/삭제 시 (O(n))

 

2. 선형 리스트

배열과 비슷한 구조지만, 동적으로 크기를 조절할 수 있다. 구현 방식은 다음 두 가지다:

• 연속 리스트: 배열처럼 메모리 공간이 연속된 형태로 할당됨.
• 연결 리스트: 노드라는 단위로 데이터를 저장하고, 포인터로 서로 연결한다.

연결 리스트는 순서를 지켜 연속적으로 저장하는 것은 아니다. 임의의 기억 공간에 기억시키되, 노드의 포인터 부분을 이용하여 연결시킨다. 포인터까지 기억해야해서 기억 공간 효율은 좋지 않다. 조회는 느리나O(n) 삽입 삭제가 빠르다. O(1)

 

 

3. 스택

LIFO 리스트. 

- 함수의 호출 순서, 인터럽트 처리, 컴파일러를 이용한 언어 번역 등에 이루어진다.

- 스택의 모든 기억 공간이 꽉채워지면 오버플로가, 데이터가 없는 상태(Top == 0)에서 데이터를 삭제하면 언더플로가 발생한다.

- 삽입, 삭제 O(1) 탐색 O(n)

- 재귀, 호출, 후위표기법, 깊이 우선 탐색 등 왔던 길을 되돌아가는 경우에 사용된다.

 

4. 큐

FIFO 리스트.

- 시작과 끝을 표시하는 두 개의 포인터가 있다.

- 삽입, 삭제 O(1) 탐색 O(n)

 

5. 데크

- 삽입과 삭제가 리스트 양쪽 끝에서 발생할 수 있다. 

- 입력 제한 데크: Scroll, 입력은 한 쪽에서 출력은 양쪽에서

- 출력 제한 데크: Shelf, 입력은 양 쪽에서, 출력은 한 쪽에서

- 삽입, 삭제 O(1) 탐색 O(n)

 

 

비선형 그래프

1. 그래프

- 정점(버텍스)과 간선(엣지)의 두 집합으로 이루어진다.

- 방향 그래프와 무방향 그래프가 있다. 

- 트리는 사이클이 없는 그래프이다. 

 

 

2. 트리

정점(노드)과 선분(브랜치, 링크)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태. 

[용어]

- 근노드(루트 노드): 트리의 맨 위에 있는 노드

- 차수(디그리): 각 노드에서 뻗어나온 가지의 수

- 단말노드, 잎 노드(터미널 노드, 리프 노드): 자식이 없는 즉 디그리가 0인 노드

 

[운행법]

각 노드를 찾아가는 방법. 자식은 항상 왼쪽에서 오른쪽이다. 

- preorder: 부모, 왼쪽, 오른쪽 (부모가 앞 pre)

- Inorder: 왼쪽, 부모, 오른쪽 (부모가 중간 in)

- postorder: 왼쪽, 오른쪽, 부모 (부모가 뒤 post)

 

각각의 운행법으로 만들어진 수식의 표기법은 아래로 나온다. 

- 전위 표기법(prefix)

- 중위 표기법(infix)

- 후위 표기법(postfix)