알고리즘 소개
1. 자료구조 (data structure)
- 컴퓨터 기억공간 내에 자료를 표현하고 조직화시키는 방법
2. 배열 (array)
- 같은 자료형을 갖는 연속적인 데이터를 하나의 변수로 묶어놓은 데이터 집합
- 논리적 순서와 물리적 순서가 동일: 각 원소에 대한 접근시간은 동일
- 인덱스(index, 첨자)로 각 원소를 구분
- 1차원 / 다차원 배열 행(row)
- 희소배열(sparse matrix): 원소값이 0인 원소들이 많은 배열, '행, 열, 값'으로 효율적으로 표현 가능
- 데이터의 삽입/삭제 연산에서 시간적 오버헤드 발생, 적절한 배열 크기를 미리 결정하기 어려워 오버플로/공간의 낭비를 초래
3. 리스트
1) 선형리스트(linear list, ordered list)
- 1개 이상의 원소들이 순서를 가지고 구성되어 있는것
A = (a1, a2, .. an)
- 1차원 배열과 동일한 구조로 빈번한 자료이동에 불편
2) 연결리스트(linked list)
a. 데이터필드와 링크필드를 가진 노드들의 연결을 통해 구성하여, 각 원소들이 물리적으로 인접해있지 않아도 됨
b. 링크필드만 조정하는 작업을 통해 간단히 삽입과 삭제를 수행, 기억장치의 할당과 반환을 통해 동적으로 관리
c. 포인터 변수 head: 연결리스트의 시작노드
노드의 링크: 바로 다음에 위치하는 노드를 가리키는 주소
마지막 노드의 링크: NULL 포인터
d. 종류
- 단일 연결 리스트 (singly linked list)
- 이중 연결 리스트 (doubly linked list)
- 원형 연결 리스트 (circular linked list): 순회 연산 가능
스택(stack)
- 데이터의 삽입과 삭제가 리스트의 한쪽 끝에서만 이루어지는 제한된 선형 리스트
- LIFO (Last-in-First-Out) 구조
큐 (queue)
1. 큐
-
한쪽 끝에서는 삽입만 수행하고, 다른 쪽 끝에서는 삭제만 수행하는 리스트
-
FIFO (First-In-First-Out), enqueue, dequeue
-
오버플로, 언더플로 발생
-
작업스케줄링, 버퍼
2. 원형큐(circular queue): front 앞에 빈자리가 존재하게되는 순차적인 큐의 단점을 보완, 모듈(module) 연산자
데크(deque, double ended queue): 양쪽 끝 모두에서 삽입과 삭제가 가능한 구조
트리 (tree)
-
노드 (node, 정보학목)와 가지(branch, 노드를 연결)로 계층적인 구조를 이루는 비선형 자료구조
1) 트리구조
2) 이진트리(binary tree)
-
공백이거나 각 노드의 차수가 2이하인 순서트리 (not 공백트리)
-
한 노드에 대한 서브트리의 순서는 중요한 의미를 갖는다
a. 특성
-
n개의 노드를 갖는 경우:
트리 최대높이 = (경사이진트리) n
트리 최소높이 = (포화, 완전이진트리) | log2n | +1 -
각 레벨 i에서 가질 수 있는 최대 노드수 = 2i ( i >= 0 )
-
깊이(높이) k (k >= 1)인 이진트리의 최대 노드 수 = 2k-1
b. 이진트리의 균형
- 트리의 높이가 짧을수록 탐색이 짧음
- 균형요소 (balance factor): 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차
- AVL(Adelson, Velskii, Landis) 트리: 균형요소가 -1, 0, 1 균형을 이루고 있는 트리
c. 이진트리의 종류
- 전(full) 이진트리: 모든 노드의 차수가 0이거나 2인 이진트리
단말 노드의 수 = 비단말 노드의 수 + 1 - 포화(perfect) 이진트리: 빈자리없이 노드를 모두 가지 높이가 동일한 이진트리
노드의 개수 = 2k-1 (k: 높이)
단말 노드의 개수 = 2k-1 - 완전(complete) 이진트리:
마지막 레벨 전까지 포화이진트리를 형성하고, 마지막 레벨에서는 왼쪽부터 오른쪽ㅇ로 중간에 빈자리없이 채워진 트리
- 총 노드수가 2k-1-1을 초과하지 않으면서 포화이진트리의 노드번호에 해당하는 연속적인 번호를 갖는다
- 노드의 개수 = 2k-1 에서 2k-1의 값 - 균형(balanced) 이진트리: 모든 단말노드의 깊이 차이가 많아야 1인 이진트리
균형 이진트리의 깊이[log2n](n: 노드의 개수) - 경사(skewed) 이진트리: 한쪽 방향으로만 뻗어나간 트리, 낭비가 심함
d. 연산
-
삽입
-
삭제
-
순회(traverse): 일정한 순서에 따라 트리의 각 노드를 한번씩 방문 (각 레벨마다 자식노드가 있을경우, 내려가 순서를 다시 고려)
e. 표현
- 이진트리는 일치된 배열 또는 연결리스트를 이용해서 구현
히프(heap) 트리
- 각 노드의 값이 그 노드의 자식노드의 값보다 크거나(작거나) 같은 완전이진트리
- 최대값 삭제 및 원소 삽입이 수월해서 우선순위 큐, 히프정렬에서 이용
4) 이진탐색트리(binary search tree)
- 각 노드의 유일한 키값을 가지며, 각 노드의 왼쪽 서브트리의 모든 키값은 해당노드의 키값보다 작고, 오른쪽 서브트리의 모든 키값은 해당 노드의 키값보다 크다
- 루트 노드로부터 키값 비교를 통해 작으면 왼쪽 가지, 크면 오른쪽가지를 따라 탐색
그래프
기본개념
-
G = (V, E): 그래프 G는 정점(vertex)들의 유한집합V와 정점들의 쌍을 연결하는 간선(edge)들의 유한집합E로 구성
-
일반적으로 정점은 인덱스를, 간선은 가중치(weight)를 갖는다
-
간선의 방향성 존재 여부에 따라
용어
- 인접과 부수: 두 정점은 인접(adjacent)해 있다
- 경로(path): 간선으로 연결된 정점들의 순차열 (ex. G2의 {3, 4, 2})
- 경로의 길이(length): 경로에 포함된 간선의 개수
- 단순경로(simple path): 한 경로상에서 처음과 마지막 정점을 제외한 모든 정점들이 모두 다른 경로
- 사이클(cycle): 세개 이상의 정점을 가진 경로중에서 시작점들과 끝정점이 같은 경로 (ex. G2에서 {1, 3, 4, 1})
- 단순사이클: 시작정점과 끝정점을 제외하고 모든 정점이 서로 다른 사이클
- 연결되다(connected): 두 정점 사이에 경로가 존재하는 경우
- 서로 연결되었다
- 양쪽으로 (강하게, strongly), 한쪽으로(약하게, weakly) 연결되었다
- 가중 그래프(weighted graph): 간선에 비용이나 시간과 같은 특정의미(숫자)를 부여한 그래프 (ex. 도시와 도시 사이의 거리)
- 부분 그래프(subgraph): G=(V,E)에 대해 V'(G)<=V(G)이고 E'(G)<=E(G)인 그래프 G'=(V', E')
- 완전 그래프(complete): 최대개수의 간선을 갖는 그래프, 무방향 n(n-1)/2, 방향 n(n-1)
- 차수(degree): 정점에 부수된 간선의 개수, 진입차수(in-degree), 진출차수 (out-degree)
