티스토리

개발용

검색하기

블로그 홈

개발용

rulic.tistory.com/m

피주빈 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

0405 그래프의 탐색 ★★★★ 깊이 우선 탐색 Depth First Search 너비 우선 탐색 Breath First Search 그래프는 트리와 다르게 여러 정점들이 무차별적으로 연결될 수 있으므로, 그래프의 탐색은 해당 정점을 이미 방문했는지를 체크하는 추가작업이 포함된다. 별도의 방문 테이블을 만들어 방문 노드들을 추가하거나, 클래스 방문 여부를 표시하는 속성을 추가한다. 깊이 우선 탐색 DFS 자식, 그 자식의 자식 등 계속 이동하여 깊은 노드부터 처리하는 방식 형제 노드를 방문하기 전 자식부터 모든 노드를 방문하면서 목표 노드를 검색하는 연산 재귀호출과 스택을 사용한 비재귀 호출 너비 우선 탐색 BFS 형제 노드부터 처리하는 방식 각 노드에서 자식 노드를 방문하기 전에 형제 노드를 먼저 방문한다. 모든 노드를 방문하는 연산.. 공감수 0 댓글수 0 2021. 4. 5.
0402 그래프 그래프는 루트 노드와 부모 자식 개념이 없다. 그래프는 네트워크 모델을 표현하는 구죠 연결이 단절된 부분 그래드들의 집합으로 구성 가능 정점(vertex)과 간선(edge)으로 구성 정점=그래프 노드 간선=노드를 연결하는 라인 그래프 G=(V,E) 가중치 = 한 정점에서 다른 정검으로 가는 간선에 할당된 비용 인접 정점 = adjacent vertex 부분 그래프 = 한 그래프의 부분 영역을 가리키는 것으로 정점과 간선 집합의 부분 집합 방향 그래프 = 간선이 방향을 가지는 그래프 무방향 그래프 = 간선이 양방향 차수 = 한 노드에 연결된 노드 정점들의 수 진입 차수 = 방향 그래프에서 밖에서 들어오는 간선의 수 진출 차수 = 방향 그래프에서 밖으로 나가는 간선의 수 경로 = 간선으로 연결된 정덤들을 순.. 공감수 0 댓글수 0 2021. 4. 2.
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.. 공감수 0 댓글수 0 2021. 4. 2.
0401 이진탐색트리Binary Search Tree 왼쪽 노드의 값이 루트 노드의 값보다 작고, (root>node)=left 오른쪽 노드의 값이 루트 노드의 값보다 큰 값을 갖는 트리 (root 0) { //넣은 값>노드면 오른쪽 node = node.right; } else if (result < 0) { //넣은 값 공감수 0 댓글수 0 2021. 4. 1.
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.. 공감수 0 댓글수 0 2021. 4. 1.
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); //변수에 노드의 .. 공감수 0 댓글수 0 2021. 4. 1.
0401 연결리스트로 구현한 이진트리 InorderTraversal (Iterative) 복습 루트 노드에서 최좌측 노드까지 스택에 저장한다. public class BinaryTree { public BinaryTreeNode root; public BinaryTree(string data) { this.root = new BinaryTreeNode(data); } public void PrintInorderTraversal() { //스택을 만든다. var stack = new Stack(); //변수에 루트 넣기 var node = this.root; //루트 노드에서 최좌측까지 스택에 저장 while (node != null) { stack.Push(node); node = node.left; } //스택에 요소가 있다면 반복 while (stack.Count > 0) { //꺼내고 출력 .. 공감수 0 댓글수 0 2021. 4. 1.
0401 연결리스트로 구현한 이진트리 Preorder Traversal (Iterative) 복습 public class BinaryTree { public BinaryTreeNode root; public BinaryTree(string data) { this.root = new BinaryTreeNode(data); } public void PrintPreorderIterative() { var stack = new Stack(); stack.Push(this.root); while (stack.Count > 0) { var node = stack.Pop(); Console.WriteLine("{0}", node.data); if (node.right != null) { stack.Push(node.right); } if (node.left != null) { stack.Push(node.left.. 공감수 0 댓글수 0 2021. 4. 1.
0401 배열을 사용해 이진트리 구현하기 복습 public class BinaryTreeUsingArray { private string[] arr; public string Root { get { return this.arr[0]; } set { this.arr[0] = value; } } public BinaryTreeUsingArray(int capacity) { this.arr = new string[capacity]; } public void AddLeft(int parentIndex,string data) { var leftIndex = (parentIndex * 2) + 1; this.arr[leftIndex] = data; } public void AddRight(int parentIndex,string data) { var right.. 공감수 0 댓글수 0 2021. 4. 1.
0401 연결트리로 구현한 이진트리 복습 public class BinaryTreeNode { public string data; public BinaryTreeNode left; public BinaryTreeNode right; public BinaryTreeNode(string data) { this.data = data; } } public class BinaryTree { public BinaryTreeNode root; public BinaryTree(string data) { this.root = new BinaryTreeNode(data); } public void PrintPreorderTraversal() { this.PreorderTraversalImple(this.root); } private void PreorderTra.. 공감수 0 댓글수 0 2021. 4. 1.
0331 이진트리 Binary Tree preorder 부모노드를 먼저 순회하고, 다음 왼쪽 서브 트리를, 마지막으로 오른쪽 서브트리를 순회 배열에 이진 트리를 저장하는 방식은 기본적으로 트리 레벨 순으로 왼쪽>오른쪽으로 저장 A[0] = 루트, A[1] = A의 왼쪽 자식, A[2] = A 자식의 오른쪽 형제 public class BinaryTreeArray { private string[] arr; public string Root { get { return this.arr[0]; } set { this.arr[0] = value; } } public BinaryTreeArray(int capacity) { this.arr = new string[capacity]; } public void SetLeft(int pa.. 공감수 0 댓글수 0 2021. 3. 31.
0330 Tree 트리 여러 노드들이 가지처럼 연결되어 있는 비선형적 자료구조(Non-linear Data Structure) 트리는 계층적 구조를 가지는 사이클이 없는 그래드(Acrylic graph)의 일종이다. 가장 위에 루트로부터 출발하며, 그 밑에 여러 자식 노드들을 가지는 구조 (순회 x) 그 밑에 0개 이상의 자식 노드를 가질 수 있고, 그 자식 노드 각각은 다시 자기 자신의 자식 노드를 가질 수 있다. 루트 간선 edge 두 모드를 잇는 링크 자식 child 부모 parent 형제 sibling 부모가 같은 노드들 단말 leaf 자식을 갖지 않는 하단의 노드 높이 height 특정 노드에서 루트 사이의 길이 (윗쪽 방향으로 계산, 간선으로 측정) 깊이 depth 루트에서 노드까지 길이 (아랫쪽 방향) 트리 높이 .. 공감수 0 댓글수 0 2021. 3. 30.
0330 Stack 스택은 가장 최근에 넣은 데이터를 먼저 꺼내서 사용하는 선형적인 자료구조(linear data structure) top에 데이터를 추가(push), 데이터를 꺼낼 때 (pop)도 탑에서 배열/연결 리스트로 구현 ●Array Stack (고정 배열) push 메서드에서는 탑 인덱스를 하나 증가시킨 후에 새 요소 추가 (탑 = -1) pop 메서드에서는 탑 인덱스 요소를 가져오고 탑 인덱스 하나 감소 public class StackArray { //top private int top; //배열 생성 private string[] arr; public bool IsEmpty { get { return this.top == -1; } } public StackArray(int capacity) { this... 공감수 0 댓글수 0 2021. 3. 30.
0330 Queue 도착한 순서대로 데이터를 꺼내서 사용하는 선형적인 자료 구조 (선입선출) 배열이나 연결 리스트를 사용해서 구현한다. rear 인덱스에 데이터를 넣고, 데이터를 읽거나 제거할 땐 front 인덱스를 사용한다. ●Circular Queue (고정배열) front 인덱스를 다음 요소로 이동 / 모든 배열 요소를 front 앞으로 당긴다. 원형 동적 배열을 사용해 고정 배열의 문제점을 해결할 수 있다. 1. front/rear 인덱스는 -1로 설정 2. front/rear 데이터는 0으로 설정 3. queue가 가득 찼는지 확인 후 (rear+1)%arr.Length로 데이터 삽입 3-1. rear+1 == front 인덱스인지 확인 4. 데이터 제거 시, 비어있지 않으면 데이터를 읽고 front 하나 증가 마.. 공감수 0 댓글수 0 2021. 3. 30.
0329 Single Linked List 복습 public class Node { public int data; public Node next; public Node(int data) { this.data = data; } } public class SingleLinkedList { private Node head; public SingleLinkedList() { } public void Add(Node node) { if (this.head == null) { //헤드가 비어있을 경우 새 노드를 헤드로 설정 this.head = node; } else { //헤드가 있다면 Node current = this.head; while (current != null && current.next != null) { //노드 값이 널이 아니고, 그 다음 값.. 공감수 0 댓글수 0 2021. 3. 30.
0329 자료구조 (배열과 링크드 리스트) 데이터의 구조를 만들어 데이터를 저장하고 관리하는 것 잘 설계된 자료구조는 실행시간을 최소화하고 소요 공간을 최소한으로 사용하면서 연산을 수행할 수 있도록 한다. 추상적 자료형 : 알고지름이 문제를 해결하는데 필요한 자료의 형태와 그 자료를 사용한 연산들을 수학적으로 정의한 모델 무엇이 구현되어야 하는 지를 정의한 것, 논리적 형태로 정의한다. 자료구조의 종류: 1. 단순 구조 - 기본적인 데이터 타입으로 정수/실수/문자/불 2. 선형 구조 - 배열, 연결 리스트, 스택, 큐 같은 자료구조 3. 비선형 구조 - 1:다 , 다 대 다와 같은 구조. 트리, 그래프 등 4. 파일 구조 Array 순차적/일렬로 저장하는 자료구조 고정 크기를 가지며, 배열은 고정적이다. Jagged Array 가변 배열 [][].. 공감수 0 댓글수 0 2021. 3. 29.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.