5장 컴퓨터 과학/Data Structure & Algorithm27 [자료구조] 그래프 (Graph) 개념 그래프는 객체를 표현하는 정점(vertex)과 객체를 연결하는 간선(edge)으로 구성한다. G = (V, E)로 표현하는데 V와 E의 두 집합으로 구성된다. 여기서 V는 공집합이 아닌 정점(vertex)들의 유한 집합, E는 두 정점을 잇는 간선(Edge)들의 집합이다. V(G)는 그래프 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합을 의미한다. 종류 무방향 그래프(undirected graph)는 간선을 나타내는 정점의 쌍에 순서가 없는 그래프이다. 간선 (vi, vj)와 간선 (vj, vi) 는 동일한 간선으로 본다. 방향 그래프(directed graph)는 각 간선을 방향이 표시된 정점의 쌍 (vi, vj)으로 나타낸다. 간선 (vi, vj)와 간선 (vj, vi)는 서로 다른.. 2021. 6. 3. [자료구조] 이진 트리 (Binary Tree) 개념 순서 트리(ordered tree)의 일종으로서 각 노드의 차수가 2이하인 트리이다. 모든 노드의 차수가 0, 1 또는 2인 트리는 모두 해당이 된다. 성질 임의의 이진 트리에서 단말 노드(terminal node)의 수 n0와 차수가 2인 간 노드(nonterminal node)의 수 n2 사이에는 n0 = n2 + 1 의 관계가 성립한다. 모든 노드의 수가 n인 완전 이진 트리의 i번째 노드에 대해 다음 성질이 있다. parent(i)는 i=1이 아니면 i/2에 위치한다. i=1일 때는 근을 나타내므로 부모 노드가 존재하지 않는다. lchild(i)가 2i≤n이면 2i번째에 위치한다. 만약 2i>n이면, i의 왼쪽 밑에 존재하는 노드는 없다. rchild(i)가 2i+1≤n이면 2i+1번째에 위.. 2021. 6. 3. [자료구조] 트리 (Tree) 개념 트리는 원소들을 계층적으로 저장하는 추상 데이터 타입이다. 최상위 원소를 제외하고, 각각의 원소는 하나의 부모 원소와 0 또는 여러 개의 자식 원소를 갖고 있다. 특성 일반적으로 트리는 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 말한다. T의 원소 중 근 노드(root node)라 불리우는 특정한 1개의 노드가 존재한다. 근 노드를 제외한 나머지 노드들은 서로 분리된 부분 집합이다. 순환(cycle)을 허용하지 않는다. 처음과 끝의 경로가 같은 단순 경로를 사이클(cycle)이라 한다. 트리는 그래프의 부분 집합으로서, 그래프를 형성하는 정점 가운데서 어떠한 두 정점 사이에도 사이클이 형성되지 않은 연속된 그래프(connected graph)라고도 할 수 있다. 용.. 2021. 6. 3. [자료구조] 큐 (Queue) 개념 큐(queue)는 리스트의 한 쪽 끝(rear)에서 자료의 입력이 이루어지고, 다른 쪽(반대 쪽) 끝(front)에서 자료의 출력이 이루어지도록 구성된 구조를 의미한다. 따라서 큐는 선입선출(FIFO, First In First Out)이라고 하며 이는 먼저 들어간 것이 먼저 나온다는 것을 의미한다. 큐는 공유 자원 접근, 멀티 프로그래밍, 메시지 큐, 그래프와 트리의 너비 우선 탐색 등에 사용된다. 이동 큐(Remove Queue) 큐의 구조상 큐에 기억 공간에 남아 있어도 새로운 노드를 삽입시킬 수 없게 된다. 따라서 이를 해결하기 위하여 기억 공간을 정리하여 새로운 노드를 삽입할 수 있도록 하는 방식이다. 큐의 추상 데이터 타입(ADT) push(val): 큐의 rear에 val을 삽입한다. .. 2021. 6. 3. [자료구조] 스택 (Stack) 개념 스택(stack)은 어떤 리스트에서 모든 입력과 출력이 한쪽 끝에서만 일어나는 구조이다. 즉, 새로운 항목을 리스트 안으로 입력하는 것(삽입)과 리스트 내에 이미 들어 있는 항목을 출력하는 것(삭제)이 모두 리스트의 한쪽 끝(top)에서만 일어나는 항목들의 순서 집합을 의미한다. 이러한 방식을 후입선출(LIFO, Last In First Out)이라 한다. 스택은 재귀 호출, 후위 표현식의 계산, 백트래킹, 트리와 그래프의 깊이 우선 탐색 등에 사용된다. 추상 데이터 타입(ADT) push(val): val을 스택의 최상위에 삽입한다. pop(): 스택의 top에 있는 객체를 스택에서 제거한다. 만약 빈(empty) 스택이라면 오류를 발생한다. top(): 스택의 최상위 원소를 반환한다. 만약 빈(.. 2021. 6. 3. 이전 1 2 3 4 5 6 다음 반응형
