C#(65)
-
0405 그래프의 탐색 ★★★★
깊이 우선 탐색 Depth First Search 너비 우선 탐색 Breath First Search 그래프는 트리와 다르게 여러 정점들이 무차별적으로 연결될 수 있으므로, 그래프의 탐색은 해당 정점을 이미 방문했는지를 체크하는 추가작업이 포함된다. 별도의 방문 테이블을 만들어 방문 노드들을 추가하거나, 클래스 방문 여부를 표시하는 속성을 추가한다. 깊이 우선 탐색 DFS 자식, 그 자식의 자식 등 계속 이동하여 깊은 노드부터 처리하는 방식 형제 노드를 방문하기 전 자식부터 모든 노드를 방문하면서 목표 노드를 검색하는 연산 재귀호출과 스택을 사용한 비재귀 호출 너비 우선 탐색 BFS 형제 노드부터 처리하는 방식 각 노드에서 자식 노드를 방문하기 전에 형제 노드를 먼저 방문한다. 모든 노드를 방문하는 연산..
2021.04.05 -
0402 그래프
그래프는 루트 노드와 부모 자식 개념이 없다. 그래프는 네트워크 모델을 표현하는 구죠 연결이 단절된 부분 그래드들의 집합으로 구성 가능 정점(vertex)과 간선(edge)으로 구성 정점=그래프 노드 간선=노드를 연결하는 라인 그래프 G=(V,E) 가중치 = 한 정점에서 다른 정검으로 가는 간선에 할당된 비용 인접 정점 = adjacent vertex 부분 그래프 = 한 그래프의 부분 영역을 가리키는 것으로 정점과 간선 집합의 부분 집합 방향 그래프 = 간선이 방향을 가지는 그래프 무방향 그래프 = 간선이 양방향 차수 = 한 노드에 연결된 노드 정점들의 수 진입 차수 = 방향 그래프에서 밖에서 들어오는 간선의 수 진출 차수 = 방향 그래프에서 밖으로 나가는 간선의 수 경로 = 간선으로 연결된 정덤들을 순..
2021.04.02 -
0402 이진 탐색 트리 재귀 함수로 중위순회
public class BSTNode { public int data; public BSTNode left; public BSTNode right; //생성자 public BSTNode(int data) { this.data = data; } } public class BST { private BSTNode root; public List ToSortedList() { //동적 배열 생성 List list = new List(); this.Traversal(this.root, list); return list; } public void Add(int data) { if (this.root == null) { this.root = new BSTNode(data); } else { //변수에 루트 담기 va..
2021.04.02 -
0401 이진탐색트리Binary Search Tree
왼쪽 노드의 값이 루트 노드의 값보다 작고, (root>node)=left 오른쪽 노드의 값이 루트 노드의 값보다 큰 값을 갖는 트리 (root 0) { //넣은 값>노드면 오른쪽 node = node.right; } else if (result < 0) { //넣은 값
2021.04.01 -
0401 연결리스트를 사용해 이진트리 만들고 Postorder Traversal (Iterative) 복습
public class BinaryTree { public BinaryTreeNode root; public BinaryTree(string data) { this.root = new BinaryTreeNode(data); } public void PostorderIterative() { //스택을 만든다. var stack = new Stack(); //변수에 루트를 넣는다. var node = this.root; //왼쪽 끝까지 오른쪽 노드와 루트 노드를 넣는다. while (node != null) { if (node.right != null) { stack.Push(node.right); } stack.Push(node); node = node.left; } //스택에 요소가 있으면 반복 whil..
2021.04.01 -
0401 연결리스트로 이진트리 만들고 중위순회 하기 (Iterative방식) 복습
public class BinaryTree { public BinaryTreeNode root; public BinaryTree(string data) { this.root = new BinaryTreeNode(data); } public void PrintInorderIterative2() { //스택 만든다. var stack = new Stack(); //변수에 루트를 넣는다. var node = this.root; //변수에 노드가 있거나 스택에 요소가 있을 경우 반복 while (node != null || stack.Count > 0) { //변수에 노드가 있다면, 반복 while (node != null) { //변수의 노드를 스택에 넣는다 stack.Push(node); //변수에 노드의 ..
2021.04.01