주요 용어용어해설트리 데이터 간의 관계를 나타내는 비선형 자료구조로서 노드(node)라고 불리는 부분과 노드를 연결하는 가지(branch,edge)로 구분됨잎 노드 단말 노드(terminal node)라고도 하며, 노드의 차수가 0인 노드내부 노드 비단말 노드(non-terminal node)라고도 하며, 루트 노드와 단말 노드를 제외한 나머지 노드이진 트리 트리 중에서 차수가 2인 트리를 의미하고, 모든 노드의 차수는 최대 2를 넘지 않으며 모든 노드는 최대 2개의 서브 트리를 가짐이진 트리의 순회 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조완전 이진 트리 트리의 최대 레벨이 k일 때, 레벨 k-1까지는 포화 이진 트리를 형성하고, 레벨 k에서는 왼쪽부터 오른쪽으로 채워진 트리임그래프 정점..
그래프의 표현인접행렬 A[i][j]에 값이 존재하면 그래프의 정점 i에서 정점 j 사이에 간선이 존재함을 의미하고, A[i][j]의 값은 1로 정함 그래프의 탐색그래프의 모든 정점을 체계적으로 방문하는 것깊이 우선 탐색(depth first search)과 너비 우선 탐색(breadth first search)이 있음 깊이 우선 탐색 최근의 방문하지 않은 인접한 정점을 우선적으로 방문함최종적인 방문 순서는 : 1, 2, 4, 5, 7, 6, 3 이 됨 너비 우선 탐색 최근의 방문하지 않은 인접한 정점을 모두 방문함최종적인 방문 순서는 : 1, 2, 3, 4, 5, 6, 7 이 됨
그래프의 개념과 용어그래프 G- 정점(vertex)들의 유한 집합 V와 두 개의 정점을 연결하는 간선(edge)들의 유한 집합 E로 정의- G=(V,E)로 표시됨 방향 그래프(directed graph, digraph)- 두 정점을 연결하는 간선이 방향성을 가지는 간선으로 연결된 그래프 무방향 그래프(undirected graph)- 간선이 방향성이 없는 간선으로 연결된 그래프 V(G1)={1,2,3,4} E(G1)={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}V(G2)={1,2,3,4} E(G2)={,,,,,} 두 정점이 간선으로 직접 연결되어 있으면 두 정점은 인접(adjacent)해 있다고 하며, 해당 간선은 두 정점에 부수(incident)되었다고 함 ‘인접한다’- 정점간의..
이진트리(binary tree)트리 중에서 차수가 2인 트리를 의미모든 노드의 차수는 최대 2를 넘지 않음모든 노드는 최대 2개의 서브 트리를 가짐각 서브트리는 왼쪽 서브트리와 오른쪽 서브트리로 구분됨왼쪽 노드와 오른쪽 노드에 ‘순서’의 의미를 부여함이진트리의 각 서브트리는 다시 이진트리가 됨 이진트리의 높이N개의 노드를 가진 이진 트리의 높이를 계산으로 구할 수 있음최대 높이 : N으로 노드의 개수와 같음최소 높이 : 최대 2개의 자식 노드를 갖는 경우로서 [log2N]+1이 높이가 됨 이진트리 순회 연산일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 것순회 연산을 이용해서 트리 내의 정보를 선형적인 순서의 정보로 만들 수 있음 DLR- 루트 노드 방문 → 왼쪽 서브트리 방문 → 오른쪽 서..
트리(tree)데이터간의 관계를 나타내는 비선형 자료구조노드(node)라고 불리는 부분과 노드를 연결하는 가지(branch, edge)로 구분됨노드 사이에는 계층적인 관계성을 갖음 노드(node)- 정보 항목과 가지를 합쳐서 부르는 것 루트(root)- 빈 트리가 아닌 경우에 맨 꼭대기에 있는 하나의 노드 차수(degree)- 각 노드에 있는 가지의 수 잎 노드(leaf node)- 단말 노드(terminal node)- 노드의 차수가 0인 노드 내부 노드(internal node)- 비단말 노드(non-terminal node)- 루트 노드와 단말 노드를 제외한 나머지 노드 조상(선조, ancestor) 노드•루트 노드로부터 어떤 노드 X까지의 경로(가지들의 모음) 상에 존재하는 모든 노드를 X의 조상..
주용 용어용어해설자료구조 추상화를 통해 자료의 논리적 관계를 구조화한 것추상화 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것데이터의 추상화 다양한 객체를 컴퓨터에서 표현하고 활용하는 데 필요한 데이터의 구조에 대해서 공통의 특징만을 뽑아 정의한 것배열 동일한 자료형을 갖는 여러 개의 데이터를 동일한 변수 이름의 방에 일렬로 저장하는 자료의 집합체스택 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조큐 선형 리스트의 한쪽 끝에서는 데이터의 삭제만 이루어지고, 다른 한쪽 끝에서는 데이터의 삽입만 이루어지는 자료구조 연습문제1. 자료들 사이의 논리적인 인접 구조에 따라 자료 구조를 구분할 때 비선형 자료 구조에 속하는 것은 어느 것인가?① 배열② 리스트③ 트리④ 큐> 더 보기정답 : ..
스택(stack)데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조가장 먼저 입력된 데이터가 가장 나중에 제거되는 선입후출(FILO, First-In-Last-out) 특징을 가짐 스택의 연산오버플로(overflow)- 삽입 연산을 수행할 때 발생함- 스택을 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상 언더플로(underflow)- 삭제 연산을 수행할 때 발생함- 스택에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상 스택의 동작12345678push(S, 'A') push(S, 'B') if not empty(S) then pop(S) push(S, 'C')push(S, 'D')cs 큐(queue)선형 리스트의 한쪽 끝에서는 데이터의 삭제만 이루어지고, 다른 한쪽 ..
선형 리스트(linear list)순서 리스트(ordered list)라고도 함1개 이상의 원소들이 순서를 가지고 구성됨A=(a1, a2,…, ai,…, an)와 같이 표시하며, ai은 i 번째 원소를 나타내고, an의 n은 리스트의 크기가 됨예) 요일 리스트: (월, 화, 수, 목, 금, 토, 일) 선형 리스트의 구현 선형 리스트와 1차원 배열은 순차적인 구조를 가지고 있으므로 1차원 배열로 간단하게 표현할 수 있음 선형 리스트의 구현(배열을 통한 구현)원소를 삽입하기 위해서는 삽입될 위치 이후의 원소들의 순서를 그대로 유지하면서 원소를 삽입해야 함원소를 삽입할 위치에 있는 원소와 그 다음의 원소들을 모두 한 칸씩 뒤로 이동시켜야 함원소 삭제의 경우에도 삭제할 원소를 찾아 삭제한 후, 그 뒤에 있는 모..