셩잇님의 잡동사니

A* 길찾기 알고리즘 A* 길찾기 알고리즘과 다익스트라 알고리즘 비교 [다익스트라] 1. 해당 지점에서 갈 수 있는 모든 경로에 대한 최단 거리를 찾는다. (비효율적) 따라서 시작 지점만 알면 된다. 목적지를 주진 않는다. 다익스트라를 목적지 찾으면 종료하게끔 개선할 수도 있지만 그래도 아쉽다. 매번 모든 지점마다 갈 수 있는 모든 경로에 대한 최단 거리를 찾아 비교하기 때문이다. 2. 예약된 정점들 중 최고의 정점을 선택할 땐 최단 거리 경로를 유지할 수 있는 정점을 선택한다. [A*] 1. 모든 경로를 다 찾지 않는다. (시작 지점, 끝 지점 목적지. 이렇게 두 개가 주어진다. 목적지를 알고 있다.) 2. 예약된 정점들 중 최고의 정점을 선택할 땐 1️⃣ 최단 거리 경로를 유지할 수 있는 정점도 고려..

힙 이진 트리 모든 노드들이 자식 노드를 최대 2 개까지만 가지는 트리 이진 트리의 종류 1. 이진 검색 트리 (Binary Search Tree) 항상 왼쪽 자식은 나보다 작고 오른쪽 자식은 나보다 크다. 2. 힙 트리 (Heap Tree) Max Heap Tree : 항상 부모가 자식보다 크다. 따라서 루트는 최대값이다. Min Heap Tree : 항상 부모가 자식보다 작다. 따라서 루트는 최소값이다. [이진 트리] 다음과 같은 조건이 적용된 이진트리 1. 왼쪽을 타고 가면 현재 값보다 작다. 👉 왼쪽 자식 노드는 부모 노드보다 작아야 한다. 루트를 기준으로 왼쪽 서브트리 노드의 데이터들은 전부 루트보다 작은 값을 가진다. 2. 오른쪽을 타고 가면 현재 값보다 크다. 👉 오른쪽 자식 노드는 부모 노..

트리 [트리 이론] 트리 👉 계층적 구조를 갖는 데이터를 위한 자료 구조 ex) 회사 조직도, 노드(Node) : 데이터 표현 루트(Root) 노드는 트리를 상징하며, 부모가 없다. 즉 최상위 조상이 되는 트리의 첫 노드. 잎(Leaf) 노드는 자식이 없는, 트리의 말단 노드들을 뜻한다. 간선(Edge) : 노드의 계층 구조를 표현하기 위해 사용 이름 그대로 나무와 같다. 뻗어 나가는 구조. 트리도 그래프의 일종이라고 볼 수 있다. 단, 제한적인 모양의 그래프라고 생각할 수 있다. 또한 트리는 사이클이 있어선 안된다. 👉 한 쪽 방향으로만 뻗어야 한다. 각 노드의 부모는 딱 하나만 있어야 한다. 트리는 재귀적인 속성을 가진다. 따라서 트리에서 일부분을 떼보면 그 부분도 트리다.(서브 트리) 트리 구현 트..

다익스트라 최단 경로 알고리즘 최소 비용으로 모든 정점을 방문한다. 0 방문 예약 👉 1 (15), 3 (35) 0 을 지나 1 으로 온다면 1의 가중치는 15 0 을 지나 3 으로 온다면 3의 가중치는 35 15 = closet) continue; // 지금 시점까지 발견한 가장 좋은 후보 closet = distance[i]; now = i; } distance가 Int32.MaxValue 이 아니면 3️⃣ 과정에서 현재 예약 되어 있거나, 혹은 예약이 예전에 됐던적이 있는 정점이다. 최소값 찾기 알고리즘처럼 closet에 해당 시점까지의 최소값을 저장해 나가고 더 작은 distance를 가진 정점을 찾으면 해당 값으로 업데이트 한다. now에도 그때 그때 시점에서의 최단 거리를 가진 정점을 저장해두..

BFS(너비 우선 탐색) Queue 큐를 이용하여 가까운 순서대로 방문한다. 출발 정점을 기준으로 가까운 순서대로 차례 차례 방문한다. 예를 들어 순회을 0 정점에서 시작한다면 0 정점에서 거리 1 (간선 1 개를 타야 갈 수 있는) 👉 1, 3 0 정점에서 거리 2 (간선 2 개를 타야 갈 수 있는) 👉 2, 4 0 정점에서 거리 3 (간선 3 개를 타야 갈 수 있는) 👉 5 최종적으로 BFS 순회는 0 1 3 2 4 5 순으로 방문하게 된다. 그 때, 그 때 방문하는 정점마다 가장 가까운 거리의 정점들을 큐에 넣는다.(선입선출) 즉, 들어간지 오래된 정점부터 빠져나오게 된다. 따라서 DFS는 다양한 용도에 사용되며, BFS는 거의 최단 거리 칠 갖기 용도로 사용 된다! [BFS 구현] 큐에 다음에 방..

DFS(깊이 우선 탐색) [1. 배열로 구현된 그래프 DFS] 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 }, }; bool[] visited = new bool[6]; // 방문 체크를 위해 public void DFS(int now) // 순회 시작 위치가 인수로 들어 옴 { // 1) now 부터 방문 하고 Console.WriteLine(now); visited[now] = true; // 2) now 와 연결된 정점들을 하나씩 확인해서..

그래프 이론 [그래프의 개념] 현실 세계의 사물이나 추상적인 개념간의 연결 관계를 표현. 정점(Vertex) 👉 데이터를 표현 (사물, 개념 등) 간선(Edge) 👉 정점들을 연결하여 정점 간의 연결 관계를 표현 (간선에 가중치와 같은 값 또한 줄 수도 있다.) 그래프 ex) 소셜 네트워크 관계도 (페이스북 친구 관계) [방향 그래프] 방향이 존재하는 간선을 가진 그래프 방향 그래프 ex) 사람 간의 호감도, 일방 통행이 포함된 도로망 [그래프 순회 방법] 배열이나 리스트는 선형 자료 구조이므로 원소들을 차례대로 순회하면 되지만 그래프는 선형 자료 구조가 아닌, 한 정점에 연결된 정점들이 여러개일 수 있으므로 연결된 정점들 중 다음엔 어떤 정점을 탐색할지 다르므로 순회 방법이 다양하다. 대표적으로 두 가..

그래프 [스택과 큐] 둘 다 선형 자료구조이다. 선형 구조 자료란? 자료들이 일렬로 나열된 상태를 말한다. using System; using System.Collections.Generic; namespace Excercise { class Program { static void Main(string[] args) { Stack stack = new Stack(); stack.Push(101); stack.Push(102); stack.Push(103); stack.Push(104); stack.Push(105); int data1 = stack.Pop(); // 105 리턴 및 삭제 int data2 = stack.Peek(); // 104 리턴만 Queue queue = new Queue(); qu..

목적지 설정 [Board.cs] using System; using System.Collections.Generic; using System.Text; namespace Algorithm { class Board { const char CIRCLE = '\u25cf'; public TileType[,] Tile { get; private set; } // 맵의 타일들을 담을 배열 public int Size { get; private set; } public int DestY { get; private set; } public int DestX { get; private set; } Player _player; public enum TileType { Empty, // 갈 수 있는 타일 Wall, // ..

플레이어 이동 [Player.cs] 플레이어의 위치 결정 및 업데이트 using System; using System.Collections.Generic; using System.Text; 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, Board board) { PosX = posX; PosY = posY; _board = board; } const int MOVE_TICK = 100; // 0...

미로 준비 가장 자리만 벽으로 하는 것이 아닌, 진짜 미로처럼 벽을 배치해 보자. 미로 생성 알고리즘 👉 Binary Tree, Side Winder 두개 말고도 많지만 이 두개만 배운다. [BinaryTree 방식의 미로] 1️⃣ 가장 자리는 모두 갈 수 없는 벽으로 지정 public void Initialize(int size) { _tile = new TileType[size, size]; _size = size; for (int y = 0; y < _size; y++) { for (int x = 0; x < _size; x++) { if (x == 0 || x == _size - 1 || y == 0 || y == size - 1) _tile[y, x] = TileType.Wall; else _t..

미로 준비 미로는 한 칸 한 칸마다 채워져 있는 원 하나로 그린다. 미로의 크기는 size X size 로 지정. 미로 배열은 이차원 배열로 관리하고 원소를 타일이라고 하자. 가장 자리의 타일들은 벽이며 빨간색. 가장 자리가 아닌 타일들은 갈 수 있는 곳이며 초록색. Board.cs using System; using System.Collections.Generic; using System.Text; namespace Algorithm { class Board { const char CIRCLE = '\u25cf'; // 채워진 원 그리는 문자 코드 public TileType[,] _tile; // 맵 배열. 2차원 배열 public int _size; // 맵 크기. _size X _size 로 정해..

선형 자료 구조 데이터들을 일렬로 나열된 형태로 저장하고 싶을 때 사용하는 자료 구조 [선형 자료 구조] 👉 자료를 순차적으로 나열 배열 (Array) 동적 배열 (List) 연결 리스트 (LinkedList) [비선형 자료 구조] 👉 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 트리 그래프 배열 (Array) 특징 반드시 선언시 크기를 결정해야하며 배열의 크기는 고정적이며 절대 변경할 수 없다. 메모리 상에서도 원소들이 연속적으로 붙어 있다. 장점 메모리 안에서도 연속적으로 붙어 있어서 접근이 빠르고 편함. 인덱스로 접근이 가능한 이유! 단점 방을 추가하고 축소하는게 불가능 2D 맵의 구성시 맵의 타일(Tile)들은 게임 도중에 크기가 변할 일도 보통 없고, 타일마다 바로 바로 빠르게 접근이 가능..

[환경 설정] [게임의 3 단계] 1. 입력 유저의 입력 2. 게임 로직 입력에 따른 어떤 실행 3. 렌더링 로직에 따라 게임 화면에 그래픽을 그림 [Console 함수] Console.WriteLine 콘솔 창에 문자열 출력하고 자동으로 한 줄 띄워준다. (Line) Console.WriteLine(“문자열"), Console.WriteLine(); 👉 단순 개행. std::endl; 같은 Console.SetCursorPosition 콘솔 창의 커서 위치를 세팅한다. Console.SetCursorPosition(0, 0); 👉 커서 위치가 콘솔 창의 맨 왼쪽 상단에. Console.CursorVisible 콘솔 창에서 커서 위치를 보이게 할건지 아닌지. Console.CursorVisible = f..

Big-O 표기법 [Big-O 표기법을 사용하는 이유] 알고리즘의 성능을 객관적으로 측정하기 위하여 사용. 단순히 실행 속도를 비교하는 것으로 알고리즘 성능을 측정하는건 컴퓨터 실행 환경에 따라 차이가 있기 때문에 별로 좋지 못하다. 입력이 적은 구간과 많은 구간에서 성능이 확연히 차이가 나는 경우도 있을 수 있다. [표기 방법] 1단계 : 수행 연산의 개수를 대략적으로 판단 어떤 연산이 1 개만 있다면 1 개 어떤 연산이 N 번 도는 for문 안에 있다면 N 개 어떤 연산이 N 번 도는 이중 for문 안에 있다면 N^2 개 2단계 : 대장만 남긴다. public int Add(int N) { int sum = 0; // 1 번 for (int i = 0; i < N; i++) // N 번 sum += ..

해당 포스팅은 인프런에 있는 Rookiss님의 강의 Part2: 자료구조와 알고리즘 및 깃허브 블로그 '평생 공부 블로그'님의 포스팅을 참고하여 작성 한다는 것을 미리 밝힙니다.

Nullable(널러블) Nullable 👉 Null + able. 값이 없다는 것을 표현할 수 있도록 int 같이 null 값을 가질 수 없는 데이터들이 null 값을 가질 수 있도록 하는 것. 객체를 참조하는 변수는 (Monster monster 같은) null을 가질 수 있다. 그러나 int, struct 같은 기본 자료형 변수는 null을 가질 수 없기 때문에 C# 에서는 값이 없다는 것을 표현할 수 있도록 이 같은 변수들이 null 값을 가질 수 있도록 해주는 문법이 있다. 👉 Nullable 값이 없으면 return 0 혹은 return -1 이런식으로 많이 표현하는데 return null로 표현할 수 있다면 더 좋을 것이다. [Nullable 속성과 함수] 1. Value Nullable 변..

Reflection(리플렉션) 리플렉션을 사용하면 X-Ray 찍는 것과 같이 객체의 이름, 모든 멤버, 이벤트 목록 등등 객체의 세세한 정보들까지 객체의 모든 정보를 런타임 중에 가져와 분석하고 사용할 수 있다. C++엔 없고 C#에만 있는 기능이다. 그래서 C#을 사용하는 유니티에선 실행 중에도 멤버에 무엇이 있는지를 체크하고 이에 접근할 수 있는 UI를 열어 주는 등등 C#의 리플렉션 기능을 활용한다. 언리얼은 리플렉션 기능이 없는 C++을 사용하기 때문에 리플렉션을 모방하는 방식으로 리플렉션을 위한 매크로 함수를 멤버나 함수 등등에 붙이고 이 정보를 가지고 파싱하고 따로 기록하여 리플렉션 하는 방식을 취한다고 한다. .NET Reflection은 .NET 객체의 클래스 타입, 메서드, 프로퍼티 등의..

Exception(예외 처리) 게임에선 예외처리를 잘 하지 않는 편이다. 그냥 크래쉬 된 체로 냅두고 문제가 되는 코드 자체를 나중에 수정하는게 보통이다. 예외처리가 큰 의미가 없기 때문이다. 그래도 게임이라도 네트워크 오류 같은 문제는 예외 처리가 필요함! [예외가 발생하는 상황 예시] 0 으로 나눌 때 잘못된 메모리를 참조할 때 오버플로우 등등… [try-catch] try내부에서 예외가 발생하면 catch에게 예외 상황을 던져주고, 해당 예외 상황과 대응되는 catch가 이를 받아 예외 처리를 진행한다. static void Main(string[] args) { try { int a = 10; int b = 0; int result = a / b; int c = 0; // 실행 X } catch ..

Lambda(람다식) 익명의 일회용 함수를 만드는데 사용하는 문법 [익명 함수가 필요한 이유] enum ItemType // 아이템 타입 { Weapon, Armor, Amulet, Ring } enum Rarity // 레어한 정도 { Normal, Uncommon, Rare, } class Item { public ItemType ItemType; public Rarity Rarity; } static Item FindWeapon() { foreach (Item item in _items) { if (item.ItemType == ItemType.Weapon) return item; } return null; } static Item FindRareItem() { foreach (Item item i..