자료구조
-
04/02 수업내용 메모자료구조/수업내용 2021. 4. 2. 18:08
2021/04/01 그래프 비선형 자료구조, 정점(Vertex)과 간선(Edge), G = (V,E) 루트노드 개념 없음, 부모/자식 개념 없음, 네트워크 모델을 표현하는 구조 정점 간선 가중치 인접 정점 부분그래프 방향그래프 무방향그래프 : 양방향으로 이동 가능 비순환그래프 순환그래프 가중치 그래프 : 간선에 가중치를 작성 방향 비순환 그래프 : 위상정렬이 가능 그래프 표현 인접리스트, 인접 행렬 인접리스트 노드데이터, 노드동적배열, 가중치동적배열 정점 클래스와 간선 클래스를 각각 정의 그래프 탐색 [DFS] 깊이 우선탐색 (Depth First Search) [BFS] 너비 우선탐색 (Breath First Search)
-
04/02 그래프 연습자료구조/수업내용 2021. 4. 2. 17:42
Program.cs using System; namespace Study09 { class Program { static void Main(string[] args) { Console.WriteLine("Main"); new App(); } } } App.cs using System; namespace Study09 { public class App { //생성자 public App() { Console.WriteLine("App"); Graph g = new Graph(); g.AddVertex("서울"); g.AddVertex("대전"); g.AddVertex("대구"); g.AddVertex("부산"); g.AddVertex("강릉"); g.AddEdge("서울", "강릉", 10); g.AddEd..
-
04/01 수업내용 메모자료구조/수업내용 2021. 4. 1. 18:22
2021/04/01 힙 자료구조가 완전이진트리에 해당 배열로 이진트리 레벨 순으로 왼쪽에서 오른쪽으로 저장 A[0]는 루트노드 왼쪽추가(부모인덱스, 데이터) 왼쪽노드 계산 : (부모인덱스 * 2) + 1 계산한 인덱스에 데이터 추가 오른쪽추가(부모인덱스, 데이터) 오른쪽노드 계산 : (부모인덱스 * 2) + 1 계산한 인덱스에 데이터 추가 트리 순회 전위, 중위, 후위, 레벨 반복문 전위순회 루트 노드를 스택에 넣음 스택이 빌때까지 루프를 돌음 스택에서 pop하여 노드 출력 오른쪽 노드가 있으면 스택에 저장 왼쪽 노드가 있으면 스택에 저장 반복문 중위순회 1 루트 노드에서 최좌측 노드까지 스택에 저장 스택이 빌때까지 루프를 돌음 스택에서 pop하여 노드를 출력 오른쪽 노드가 있으면 오른쪽 노드부터 오른쪽..
-
04/01 연결리스트로 구현한 BinaryTree & Preorder Traversal 복습자료구조/수업내용 2021. 4. 1. 10:21
Program.cs using System; namespace Study09 { class Program { static void Main(string[] args) { Console.WriteLine("Main"); new App(); } } } App.cs using System; namespace Study09 { public class App { //생성자 public App() { Console.WriteLine("App"); BinaryTree tree = new BinaryTree("A"); tree.root.left = new BinaryTreeNode("B"); tree.root.right = new BinaryTreeNode("C"); tree.root.left.left = new Bi..
-
04/01 BinaryTree Preorder 순회 (Iterative) 복습자료구조/수업내용 2021. 4. 1. 09:57
순서 1. 이진트리, 노드 클래스 생성 2. 스택생성 루트를 스택에 넣음 3. 스택요소가 없을 때 까지 반복 스택에서 요소를 꺼내 출력 오른쪽이 null아니면 스택에 넣음 왼쪽이 null아니면 스택에 넣음 Program.cs using System; namespace Study09 { class Program { static void Main(string[] args) { Console.WriteLine("Main"); new App(); } } } App.cs using System; namespace Study09 { public class App { //생성자 public App() { Console.WriteLine("App"); BinaryTree tree = new BinaryTree("A")..
-
04/04 게임 알고리즘 시험자료구조/수업과제 2021. 4. 1. 00:45
'꿈의 나라'라는 머드 게임 구현연습 로그인 기능 구현 로그인 시 아이디 입력으로 기존유저와 신규유저 판별함 기존유저는 아이디와 일치하는 비밀번호를 입력하는것으로 게임 시작 신규유저는 이름과 비밀번호 성별등을 입력받아 회원가입 유저 로그인 정보는 user_data.json에 저장 인벤토리 기능 구현 아이템을 버리고 줍는 기능을 구현 아이템은 user_info.json에 저장 Program.cs using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Exam01 { class Program { static void Main(string[]..
-
03/31 수업내용 메모자료구조/수업내용 2021. 3. 31. 18:18
2021/03/31 왼쪽자식 오른쪽형제 트리 부모가 가진 자식들을 알기 위해서는 부모의 왼쪽 자식노드의 오른쪽 형제노드를 찾아가야함 이진트리 .net은 이진트리, 이진 탐색 트리를 제공하지 않음 트리 중 자식노드가 2개 이하인 것(0, 1, 2) 1.사향이진트리 한쪽으로만 기운 트리 2.포화이진트리 3.완전이진트리 연결리스트 또는 배열로 이진트리 구현가능 Preorder 부모노드를 먼저 순회하고 다음 왼쪽 서브트리를, 마지막으로 오른쪽 서브트리를 순회하는 방식 배열을 이용한 이진 트리의 구현 배열에 이진트리를 저장하는 방식은 기본적으로 트리 레벨 순으로 왼쪽에서 오른쪽으로 저장, 배열 A의 A[0]에는 루드노드, A[1]에는 루트의 왼쪽 자식노드, A[2]에는 오른쪽 자식노드를 저장 ?? null이 아닌..
-
03/31 BinaryTree 전위, 중위, 후위 순회 출력자료구조/수업내용 2021. 3. 31. 17:22
Program.cs using System; namespace Study09 { class Program { static void Main(string[] args) { Console.WriteLine("Main"); new App(); } } } App.cs using System; namespace Study09 { public class App { //생성자 public App() { Console.WriteLine("App"); BinaryTree tree = new BinaryTree("A"); tree.root.left = new BinaryNode("B"); tree.root.right = new BinaryNode("C"); tree.root.left.left = new BinaryNode..