본문 바로가기
반응형

프로그래밍 언어/알고리즘 및 디자인패턴20

우선 순위 큐 마무리 using System; using System.Collections.Generic; namespace Exercise { class PriorityQueue where T : IComparable { List _heap = new List(); public void Push(T data) { // 힙의 맨 끝에 새로운 데이터를 삽입한다 _heap.Add(data); int now = _heap.Count - 1; //도장깨기를 시작 while (now > 0) { // 도장깨기를 시도 int next = (now - 1) / 2; if (_heap[now].CompareTo(_heap[next]) 2023. 7. 17.
우선 순위 큐 namespace Exercise { class PriorityQueue { List _heap = new List(); public void Push(int data) { // 힙의 맨 끝에 새로운 데이터를 삽입한다 _heap.Add(data); int now = _heap.Count - 1; //도장깨기를 시작 while (now > 0) { // 도장깨기를 시도 int next = (now - 1) / 2; if (_heap[now] 2023. 7. 17.
트리 이론 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조 트리 관련 용어 부모(parent) 노드 자식{child) 노드 형제(sibling)노드 선조(ancestor) 자손 (descemdant) 루트(root) 잎(leaf) 노드의 깊이(depth) 트리의 높이(height) 트리의 재귀적 속성 및 서브트리(subtree) 2023. 7. 17.
다익스트라 최단 경로 알고리즘 namespace Exercise { internal class Program { class Graph { int[,] adj = new int[6, 6] {{ -1, 15, -1, 35, -1, -1 }, { 15, -1, 05, 10, -1, -1 }, { -1, 05, -1, -1, -1, -1 }, { 35, 10, -1, -1, -15, -1 }, { -1, -1, -1, 05, -1, 05 }, { -1, -1, -1, -1, 05, -1 }}; List[] adj2 = new List[] { new List{ 1, 3 }, new List{ 0, 2, 3 }, new List{ 1 }, new List{ 0, 1, 4 }, new List{ 3, 5 }, new List{ 4 }, }; pu.. 2023. 7. 16.
BFS를 이용한 길찾기 구현 using System; using System.Collections.Generic; using System.Text; namespace Algorithm { class Pos { public Pos(int y, int x) { Y = y; X = x; } public int Y; public int X; } class Player { public int PosY { get; private set; } public int PosX { get; private set; } Random _random = new Random(); Board _board; enum Dir { Up = 0, Left = 1, Down = 2, Right = 3 } int _dir = (int)Dir.Up; List _points .. 2023. 7. 16.
BFS(너비 우선 탐색) namespace Exercise { internal class Program { class Graph { int[,] adj = new int[6, 6] {{0,1,0,1,0,0}, {1,0,1,1,0,0}, {0,1,0,0,0,0}, {1,1,0,0,1,0}, {0,0,0,1,0,1}, {0,0,0,0,1,0}}; List[] adj2 = new List[] { new List{ 1, 3 }, new List{ 0, 2, 3 }, new List{ 1 }, new List{ 0, 1, 4 }, new List{ 3, 5 }, new List{ 4 }, }; public void BFS(int start)//길찾기에서 쓰임 { bool[] found = new bool[6]; int[] parent =.. 2023. 7. 16.
DFS(깊이 우선 탐색) namespace Exercise { internal class Program { class Graph { int[,] adj = new int[6, 6] {{0,1,0,1,0,0}, {1,0,1,1,0,0}, {0,1,0,0,0,0}, {1,1,0,0,1,0}, {0,0,0,1,0,1}, {0,0,0,0,1,0}}; List[] adj2 = new List[] { new List{ 1, 3 }, new List{ 0, 2, 3 }, new List{ 1 }, new List{ 0, 1 }, new List{ 5 }, new List{ 4 }, }; // 1) 우선 now부터 방문하고. // 2) now와 연결된 정점들을 하나씩 확인해서, // [ 아직 미발견(미방문)상태라면] 방문한다. public v.. 2023. 7. 16.
그래프 생성 namespace Exercise { internal class Program { class Graph { int[,] adj = new int[6, 6] {{0,1,0,1,0,0}, {1,0,1,1,0,0}, {0,1,0,0,0,0}, {1,1,0,0,1,0}, {0,0,0,1,0,1}, {0,0,0,0,1,0}}; }; List[] list = new List[] { new List{ 1, 3 }, new List{ 0, 2, 3 }, new List{ 1 }, new List{ 0, 1, 4 }, new List{ 3, 5 }, new List{ 4 }, }; static void Main(string[] args) { //DFS(Depth First Search 깊이 우선 탐색) //BFS(Bre.. 2023. 7. 16.
그래프 이론 [현실 세게의 사물이나 추상적인 개념 간]의 [연결 관계]를 표현 정점(Vertex): 데이터를 표현(사물, 개념 등) 간선(Edge) : 정점들을 연결하는데 사용 2023. 7. 16.
오른손의 법칙 Board using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Algorithm { class Board { public TileType[,] Tile { get; private set; } public int Size { get; private set; } const char CIRCLE = '\u25cf'; public int DestY { get; private set; } public int DestX { get; private set; } Player _player; public enum TileType { Empty, Wa.. 2023. 7. 14.
플레이어 이동 Player using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Algorithm { class Player { public int PosY { get; private set; } public int PosX { get; private set; } Random _random = new Random(); Board _board; public void Initialize(int posY, int posX, int destX, int destY, Board board) { PosX = posX; PosY = posY; _board = bo.. 2023. 7. 13.
SideWinder 미로 생성 알고리즘 using System; namespace Algorithm { class Board { public TileType[,] _tile; public int _size; const char CIRCLE = '\u25cf'; public enum TileType { Empty, Wall } public void Initialize(int size) { if (size % 2 == 0) return; _tile = new TileType[size, size]; _size = size; //Mazes for Programmers //일단 길을 다 막아버리는 작업 for(int y = 0; y 2023. 7. 13.
반응형

티스토리툴바