재민

그래프의 순회나 탐색은 하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산이다. 그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색이 있다. 깊이 우선 탐색의 경우, 먼저 하나의 정점을 방문한다. 그리고 이웃한 정점으로 갈 수 있으면 무조건 이웃 중 하나로 방문하고(단, 과거에 방문하지 않은 정점이어야한다.) 이를 계속 반복하여 시작점에서 점점 깊이가 깊어지는 노드로 전진시킨다. 만약 방문 가능한 이웃 정점이 없다면 왔떤 경로 상의 가장 최근에 방문했던 정점으로 돌아가서 그 정점의 이웃 노드 방문을 시도한다. 이 때 스택을 이용한다. 알고리즘은 다음과 같은 절차로 구성된다. 1) 먼저 시작 정점 v를 결정하고, 방문한다. 2) 정점 v에 인접하고 아직 방문하지 않은 한 정점 w를 선택한다..

다익스트라 알고리즘은 최단 경로 알고리즘 중 가장 많이 사용되는 알고리즘으로, 무방향 그래프와 방향 그래프 모두에서 사용 가능한 알고리즘이다.모든 간선은 음이 아닌 비용을 가진다는 가정을 바탕으로, 시작 정점으로부터 G의 모든 다른 정점까지의 최단 경로를 구하는 것을 목표로 한다. 다익스트라 알고리즘의 개념은 다음과 같다. 시작 정점 v에서 정점 u까지의 최단 경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 새로 추가된 정점 u에 대해 단축되는 경로가 있는 지를 확인한다. 현재 알고 있는 dist[w]를 새로 추가된 정점 u를 거쳐서 가는 dist[u] + cost[u][w]를 계산한 경로를 비교해 경로가 단축되면 dist[w]를 단축된 경로값으로 수정함으로써 최단 경로를 찾는다. [python..

Krustal Algorithm은 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법이다. Krustal Algortihm의 설계 방법은 다음과 같다. 1) 그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬한다. 2) 그래프 G에서 가중치가 가장 높은 간선을 제거한다. 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우 그 당므으로 가중치가 높은 간선을 제거한다. 3) 그래프 G에 간선이 n-1개만 남을 때까지 (2)를 반복한다. 4) 그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리가 완성된다. [python으로 구현한 코드] class Graph: def __init__(self, vertices): self.V = vertices self.graph = [..

Graph는 연결되어 있는 원소들 사이의 다대다 관계를 표현하는 비선형 자료구조로서, 버스노선도나 지하철 노선도와 같이 여러 원소들이 맞물려 있는 경우에 사용하는 자료구조형이다. 그래프는 두개의 집합 V와 간선 E로 구성되어 있다. 표기는 G = (V,E)로 한다. 그래프는 무방향 그래프와 방향그래프, 부분그래프, 가중 그래프로 나눌 수 있다. 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프로서, 간선을 나타내는 쌍에 순서가 없다. 즉 간선을 통해서 양방향으로 갈 수 있는 그래프이다. 방향 그래프는 모든 간선이 방향을 가지는 그래프로서, 방향은 정점의 쌍 의 정점의 순서로 표시한다. 간선을 통해서 한 쪽 방향으로만 갈 수 있다. 부분그래프는 원래의 그래프에서 정점이나 간선을 일부만 제외하여..

이진 탐색 트리는 탐색을 효율적으로 하기 위한 자료구조로서, 이진트리이자 모든 원소는 서로 다른 key를 가지는 특성을 가지고 있다. 이진탐색에서의 탐색은 searchBST() 연산을 이용하여 진행된다. 우선 루트에서 시작하여, 탐색할 key값 x를 루트 노드의 key값과 비교한다. key값보다 루트 노드의 key값이 클 경우 왼쪽 서브트리에서, key값이 루트노드의 key값보다 클 경우 오른쪽 서브트리에서 탐색을 진행한다는 기본 메커니즘을 기반으로 탐색을 진행한다. 이진탐색에서 탐색의 구현은 반복/재귀가 있다. 반복적 방법은 while p != NULL을 이용하여 p값을 찾을 때까지 삽입 연산을 계속 수행하는 방법이고, 재귀적 방법은 찾고자하는 key값이 해당 key값보다 클 경우 범위를 제한하여 다시..

Tree는, 하나 이상의 노드로 이루어진 유한집합으로서, 하나의 루트 노드와 분리 집합으로 분할된 다른 노드들의 집합이다. 앞서 다루었던 다른 자료구조와 달리(stack,queue,linkedlist) 원소들 간에 1:n 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층 관계를 가지는 계층형 자료구조이다. [Tree의 주요 용어 및 개념] node: 트리의 구성 요소 서브트리: 하나의 노드와 그 노드들의 자손으로 이루어진 트리 노드의 차수: 노드의 서브트리 개수 루트 노드: 부모가 없는 노드(최상위 노드) 단말 노드: 자식이 없는 노드, 차수 0 형제 노드: 부모가 같은 자식들 트리의 차수: max{노드의 차수} 노드 레벨: 트리의 각 층의 번호 트리의 높이: max{노드 레벨} 조상: 루트까지의 경..

이진트리의 순회는 다음과 같은 과정을 통해 이루어져야 한다. 1) 트리에 있는 모든 노드를 단 한번씩만 방문해야 함 2) 왼쪽 서브트리는 항상 오른쪽 서브트리보다 먼저 방문해야 함 순회 방법으로는 총 세가지가 있는데, LVR(중위순회), VLR(전위순회), LRV(후위순회) 이다. 1) 중위순회 왼쪽 서브트리 방문 > 루트 노드 방문> 오른쪽 서브트리 방문 2) 전위순회 루트노드 방문> 왼쪽 서브트리 방문> 오른쪽 서브트리 방문 3) 후위순회 왼쪽 서브트리 방문> 오른쪽 서브트리방문> 루트노드 방문 class TreeNode: def __init__(self, key): self.left = None self.right = None self.val = key def inorder_traversal(roo..

덱, Deque(Double- ended- Queue)는 큐의 front 와 rear에서 모두 삽입,삭제가 가능한 큐로서, 스택과 큐의 특성을 모두 가지고 있다. 이는 덱을 스택으로도, 큐로도 사용할 수 있음을 의미한다. - 스택으로 사용시: top > rear일때, push() >> deque의 insertRear()와 비슷, Pop() > deleteRear()와 비슷함 - 큐로 사용시 : enqueue > insertRear()와 비슷, Dequeue() > deleteFront()와 비슷 덱도 스택과 큐에서 구현한 방식처럼, 1) 배열로 구현하는 방법과, 2) 연결 리스트를 이용한 방법이 있다. 배열로 구현한 경우, 양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서변화가 많..

연결리스트를 이용하여 큐를 구현하는 예제이다. Node class와 Queue class를 이용하여 queue를 구현하였다. class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def is_empty(self): return self.front is None def enqueue(self, data): new_node = Node(data) if self.is_empty(): self.front = self.rear = new_node else: self.rear.next = new_node self.rear..

[큐 구현: 배열 이용방법] 1. 개요: 큐(Queue)는 데이터를 선입선출(FIFO, First-In-First-Out)의 원칙에 따라 처리하는 자료구조로, 배열을 이용해 구현할 수 있다. 이 보고서에서는 배열을 활용하여 큐를 구현하는 방법과 그 한계점에 대해 다룹니다. 2. 구현 알고리즘: · - Enqueue (삽입): · 큐의 끝에 새로운 원소를 추가하는 작업이다. · 배열의 끝에 원소를 추가하고, 큐의 끝을 업데이트한다. · - Dequeue (삭제): · 큐의 맨 앞에서 원소를 제거하는 작업이다. 배열의 맨 앞에서 원소를 제거하고, 큐의 시작 지점을 업데이트한다. · - Peek (참조): · 큐의 맨 앞에 있는 원소를 조회하는 작업이다. 배열의 시작 부분에 위치한 원소를 반환한다. 3. 예시..