본문 바로가기

분류 전체보기

 (231)
길찾기 1 우수법 항상 플레이어가 오른족으로 갈 수 있는지 확인하는 방법. 디아블로 동굴 맵 밝힐 때 주로 쓰는 그 방법을 코드로 표현. Init 함수에서 우수법으로 지나갈 길을 전부 저장하고 Update 함수에서 플레이어를 저장한 포지션으로 순서대로 이동 시킨다.Stack 으로 막다른 길의 Pos 를 전부 삭제 시킨다. void Player::Init(Board* board){ _pos = board->GetEnterPos(); _board = board; Pos pos = _pos; _path.clear(); _path.push_back(pos); // 목적지 도착하기 전에는 계속 실행 Pos dest = board->GetExitPos(); Pos front[4] = { Pos {-1,0}, // UP Pos {0,..
레드 블랙 트리 이진 탐색 트리의 단점은 루트 노드의 값 보다 계속 크거나 작은 값이 자식 노드로 들어오면 해당 이진 탐색 트리는  O(n) 의 시간 복잡도를 가질 수 없다는 것이다. 이것을 보안하기 나온 자료구조 중 레드 블랙 트리가 있다.레드 블랙 트리는 모든 노드가 레드, 블랙 중 하나의 색상을 가진다.모든 루트 노드는 블랙이다리프 노드들은 블랙이다. 그래서 리프 노드를 공노드가 아닌 더미 노드를 이용한다. 블랙이라는 것을 알려주기 위해서레드 노드의 자식 노드 양쪽은 언제나 모두 블랙이다. 레드가 연달아 나오기 불가능. 블랙 만이 레드의 부모가 될 수 있다.어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도착하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.위의 특성이 지켜지지 않으..
이진 탐색 트리 이진 탐색 트리이진 탐색을 배열로 실행하면 탐색 자체는 O(logn) 의 시간으로 빠른 탐색이 가능하지만 해당 배열에 삽입/삭제 시에는 결국 배열로 시간복잡도 O(n) 의 느린 삽입/삭제를 보인다. 삽입/삭제 또한, 빠르게 가능한 이진 탐색 트리를 알아본다. 이진 탐색 트리이분 탐색 뿐만 아니라 삽입/삭제도 O(logn) 의 빠른 시간 복잡도를 가지는 트리 구조이다.다만, 삽입 시 정렬된 수열이 차례로 삽입 되면 트리가 한 쪽으로 몰려서탐색, 삽입, 삭제 시간 복잡도 O(n) 의 안좋은 경우가 생긴다.이것을 위해 균형 이진 트리가 만들어짐 1. 부모노드의 왼쪽 자식노드는 부모 노드보다 작아야하며 오른쪽 자식 노드는 부모 노드보다 커야한다.2. 위의 1번 규칙은 부모노드의 자식 노드 뿐 아니라 해당 부모노..
힙으로 구현한 우선순위 큐 힙으로 구현한 우선순위 큐 자료구조의 시간 복잡도는 삽입 삭제에서 O(logn) 이다.우선순위에 따라 값이 정렬된다. #include "iostream"#include "vector"#include "queue"#include "algorithm"#include "list"using namespace std;template, class Predicate = less>class PriorityQueue{public: void push(const T& data) { // 우선 힙 구조부터 맞춰준다. _heap.push_back(data); // 도장깨기 시작! int now = static_cast(_heap.size() - 1); // 루트까지 시도하다가 중간에 멈추면 break while (n..
이진트리 와 힙 이론 이진트리 : 각 노드가 최대 2개의 자식 노드를 가지는 트리한개여도 되고 전부 공노드여도 괜찮다. 이진 트리는 특히 이진 트리 검색에서 많이 사용됨.다만, 이진 검색 트리는 왼쪽 노드는 부모 노드보다 값이 작아야하고 오른쪽 노드는 부모 노드보다 값이 커야한다. 자식 노드 기준만이 아니라 아래 계층의 모든 노드가 해당 좌우 규칙을 지켜야한다. 트리는 구현 자체에 난이도가 있다.아래도 이진 검색 트리가 맞긴하지만….. 검색의 효율이 원하는 정도로 나오지않을것이다. 이때, 트리 재배치로 균형을 맞춰줘야한다. 이 방식이 AVL, 레드블랙트리 이다.이진 검색 트리는 추가 삽입 삭제 난이도가 상당하다.  힙 트리 특징이진 트리 기반이다.부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 크다마지막 레벨을 제외한 ..
트리 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조노드 : 데이터를 표현간선 : 노드의 계층 구조를 표현하기 위해 사용부모, 자식 노드 : 계층 구조의 노드형제 노드 : 같은 부모와의 계층 구조를 이루는 노드루트 노드 : 최상위 노드잎 노드 : 맨 밑에 노드들깊이 : 루트 노드를 기준으로 0부터 아래 계층에 1씩 더해진다높이 : 트리의 계층의 갯수를 의미트리는 재귀적 속성 및 서브트리로 볼 수 있다.트리 내부에 트리가 있다.  #include #include #include #include using namespace std;using NodeRef = shared_ptr;struct Node{ Node() {} Node(const string& data) :data(data) {} string data..
BFS 인접 행렬 인접 행렬로 BFS 구현#include #include #include #include using namespace std;struct Vertex{ // int data;};vector vertices;vector> adjacent;vector> adjacent2;vector visited;vector discovered;void CreateGraph(){ vertices.resize(6); discovered.resize(6); adjacent = vector>(6); adjacent2 = vector>(6); // 인접 리스트 사용 그래프 구현 adjacent[0].push_back(1); adjacent[0].push_back(3); adjacent[1].push_back(0); adjacent[..
BFS 인접 리스트 너비 우선 탐색사용 범위가 DFS에 비해 제한적이다.길찾기에서 유용하게 쓰인다.시작점을 지정하고 탐색 시작. 시작점에서 가까운 노드부터 탐색재귀를 사용하지 않는다. (while 문 사용)queue 를 사용하여 발견한 노드를 저장Dfs 는 발견시 바로 해당 노드를 탐색하지만, Bfs 는 발견한 노드를 따로 저장 후 발견한 노드들을 차례대로(선입선출) 탐색한다.시간 복잡도 :인접 행렬 : O(n2)인접 리스트 : O(n+ 간선수)  시작점이 0노드 일 경우에 1,3 번 노드를 먼저 탐색하고 그 후, 2번 4번 노드를 탐색 한 후 5번 노드를 탐색한다.여기서 1,3 or 2,4 번 노드 중 어떤 노드에 먼저 탐색을 진행할지는 큐 자료구조를 이용하여 구현한다. 인접 리스트를 이용한 Bfs 구현#include #..

티스토리툴바