컴퓨터 과학 개론 - 자료구조 스택, 큐 , 그래프

스택과 큐

 

 

스택(Stack)

 

데이터의 삽입과 삭제가 한쪽 끝에만 이루어지는 자료구조

 

※ FILO : First In Last Out , 처음들어온 데이터가 나중에 나가는 구조.

 

스택구조에서 연산용어

 

- push : 데이터의 삽입연산

- pop : 삭제연산

- top : 데이터의 상단을 표기

 

 

 

push(‘Stack’, “A”)

push(‘Stack’, “C”)

if is not empty : pop(‘Stack’)

push(‘Stack’, ‘Z’)

push(‘Stack’, ‘S“)

 

 

*Stack overflow : 스택의 최대 사이즈가 가득 찼을 때 원소를 넣을 때 발생 (push 연산시)

*Stack Underflow : 스택의 Top 이 –1 일 때 Pop을 실행했을 때

 

 

큐 (Queue)

 

큐에서는 가장먼저 입력된 데이터가 가장 먼저 제거되는 선입선출 특징을 가진다.

※ FIFO : First In First Out

 

데이터의 삽입과 삭제를 위해 2개의 연산잔 Front, Rear 가 필요로 하며, Front 는 삭제의 위치 끝을 가리키며, Rear 는 삽입되는 위치의 끝을 가리킨다.

 

 

enqueue(‘Q’, ‘B’)

enqueue(‘Q’, ‘C’)

if is not empty dequeue(‘Q’)

enqueue(‘Q’, ‘K’)

if is not empty dequeue(‘Q’)

 

  

 

 

트리

 

트리는 비선형 자료구조이며, 계층관계를 가지고 있다.

 

트리는 노드와 노드를 연결하는 가지(Branch, edge) 로 구성된다.

 

 

 

각각 노드에 연결된 가지의 수를 차수(degree)라고 한다.

 

잎 노드(leaf node), 단말노드(terminal node) 는 노드의 차수가 0인 노드를 가리키며, 옆 그림에서는 E, F, D가 잎 노드이다.

 

내부노드는 단말 노드와 루트노드를 제외한 노드를 단말노드라 한다. 옆 그림에서 C가 내부 노드이다.

•  레벨 루트 노드로부터의 거리(가지의 개수)를 의미

 

  

•  서브트리(subtree)란 특정노드를 루트 노드로 하여 아래에 있는 연결된 구조를 의미

 

   

 

 

 

 

이진트리(Binary Tree)

 

이진트리는 트리 중에서 차수가 2인 트리를 의미

※ 모든 노드 차수는 최대 2를 넘지 않는다.

※ 각 서브 트리는 왼쪽 서브트리와 오른쪽 서브트리로 구분

 

 

 

 

 

 

이진트리의 주요 연산은 삽입 , 삭제, 순회가있다.

 

 

 

 

대표적인 연산인 순회(traverse),

 

전위 순회 Pre-order

A→ C → E → F → D → G → H

 

중위 순회 In-order

 

E→ C → F → A → G → D → H

 

후위 순회 post-order

 

E→ F →C → G → H → D → A

 

 

 

 

p포화 이진트리 깊이가 k인 이진트리 중에서 노드의 개수가 인 이진트리이다.

깊이 최대 개수는 이며, 단말노드의 개수는 이다.

 

이진 트리 종류

 

 

 

완전 이진트리 : 루트노드를 1번으로 시작하여 각 레벨별 왼쪽에서 오른쪽까지 번호를 부여할 수 있고,

노드의 번호가 연속적인 번호를 갖는 것.

 

그래프

 

 

 

그래프 G는 정점(vertex)들의 유한집합 V와 두 개의 정점을 연결하는 간선(edge)들의 유한집합 E로 정의된다.

 

 

 

 

 

두 그래프를 집합으로 표현

 

V( ) = {1,2,3,4}

E( ) = {(1,2), (1, 3), (1,4), (2,3), (2, 4), (3,4) }

 

 

V( ) = { 1,2,3,4 }

E( ) = {<1,2>, <2,3>, <3,1>, <4,1>, <4, 2>, <4,3> }

무 방향그래프에서 간선 ()로 표현 ,방향그래프에서 간선은 <> 로 표현

 

두 정점은 간선으로 연결되어 있으면, 정점은 인접(adjacent) 해있다 라하고, 해당 간선은 두 정점에 부수(incident) 되었다 한다.

 

경로(Path)는 간선으로 연결된 정점들의 순서적으로 나열

 

경로의 길이 : 경로에 포함된 간선의 개수

 

단순 경로 : 경로 상에 존재하는 정점들이 모두 다른 경로

 

사이클(Cycle) : 시작 정점과 끝 정점이 같은 경로.

단순 사이클 : 시작점과 끝 정점을 제와하고 모든 정점이 다른 경로

 

 

 

그래프의 표현

 

 

그래프를 컴퓨터 프로그래밍 언어로 구현하기 위해서는 인접행렬, 인접 리스트를 이용한다.

   

 

1) 인접행렬을 사용하여 그래프 표현

 

 

 

 

※ 그래프에서 정점과 정점이 연결되었을 경우 1로 표현하고 연결되지 않았을 경우 0으로 표시한다.

 

 

 

 

 

2) 인접 리스트를 활용한 그래프 표현

 

 

 

 

 

그래프의 탐색

 

깊이 우선 탐색과 너비우선 탐색

    

 

 

 

※ 순서는 프로그래머가 결정한다.