본문 바로가기

자료구조 알고리즘

(30)
버블 정렬 버블 정렬시간 복잡도는 명령어가 몇 번 실행되는지 확인한다.i for 문애서 (N - 1)j for 문에서 (N - 1 - i) 개 만큼이것은 전체 계산 값이 1이 될때까지 계속 되기 때문에 등차수열의 합으로 인해 N * (N -1) / 2, O(N^2) 의 최악의 시간복잡도를 가진다. 거의 못쓰는 수준. void BubbleSort(vector& v){ const int n = (int)v.size(); for (int i = 0; i v[j + 1]) { int temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; ..
이진 탐색 STL 에서 이진탐색을 제공하고 있음이진 탐색(binary search)배열에 데이터가 정렬되어 있을 때  탐색 자체는 O(logn) 이다. 빠름 특정 숫자가 배열에 있는지 찾는다면,배열의 중간 배열부터 시작해서 탐색한다. 정렬되어 있는 배열을 배열의 중간 인덱스로 재귀 속성을 가지고 탐색한다.정렬된 연결 리스트로는 불가하다. [] 를 이용한 임의 접근이 불가능해서임 배열 자체가 중간 삽입/삭제가 느리기 때문에 해당 값의 인덱스를 찾아도 거기서 해당 값을 삭제하거나 없을 시 삽입 하면 그때는 시간복잡도 O(n) 으로 느리게 반응하는 단점이 생긴다. 그래서 데이터의 변경까지 빠르게 하기 이해서 이진 탐색 트리를 사용한다.밑은 이진 탐색을 반복문과 재귀로 구현한 것 #include #include #incl..
길찾기4 A* 알고리즘 BFS, 다익스트라는 시작점은 있지만 목적지를 향해서 가는 것은 아니다.break 로 어느 지점에서 멈추라고는 했지만 목적지를 정해놓는 알고리즘은 아니었다. A* 는 시작점과 더불어 도착점까지 완벽하게 설정하고 길찾기를 시작한다.사실 이 차이점 외에는 다익스트라와 큰 차이가 없다. A* 는 출발점에서 내가 가고 있는 길이 얼마나 떨어져있는지(비용) 뿐 만 아니라 도착점과 얼마나 가까워지고 있는지도 판단할 것 이다. 2가지 고려함최적의 경로를 위해 비용을 계산하는 것은 다익스트라와 비슷하지만 비용을 2가지 방식으로 계산한다는 것이다. struct PQNode{ // 우선순위 큐에다가 정보를 넣어서 비교를 할 때에는 f 를 기준으로 비교할것 bool operator(const PQNode& other) co..
길찾기3 다익스트라 길찾기 BFS 로 길찾기 가능하지만 간선 별로 가중치가 없을 때에 최적의 경로를 찾는 것이다. 간선 별 가중치에 따라 이동 시간이 늘어난다고 하였을 때에는 다익스트라 길찾기 쓴다.목적지는 딱히 의미가 없고, 시작 노드로부터 각 노드까지의 최소 비용을 찾는 알고리즘이다. 각 노드 별로 탐색 시에 해당 경로까지의 비용을 갱신한다.  위의 3번 노드는 처음 35 비용이 저장되지만, 0 → 1 → 3 으로 탐색 되어질 때 25비용으로 갱신된다. // BFS 로 길찾기 가능하지만 간선 별로 가중치가 없을 때에 최적의 경로를 찾는 것이다.// 간선 별 가중치에 따라 이동 시간이 늘어난다고 하였을 때에는 다익스트라 길찾기 쓴다. // 목적지는 딱히 의미가 없고, #include #include #include #includ..
길찾기2 BFS 를 이용하기 일단 최단거리가 보장이 된다. 미로가 있을 때, 해당 미로의 각 POS를 정점으로 생각하면 그래프를 만들수 있다.아래 그림에서 초록색을 길, 빨간색을 벽으로 생각하면, 모든 초록색 빨간색 POS를 각각 정점으로 생각할 수 있고, 초록색이 연속으로 있으면 인접(간선이 연결 되어있다.)라고 말하고 초록색과 빨간색이 붙어있으면 초록색 노드와 빨간색 노드는 인접해 있지 않은것이다.  BFS 로 파란색 도착노드와 좌상단 시작 노드를 parent 노드를 찾는 역추적 방식으로 BFS 길찾기를 진행할것이다.시작노드와 도착노드 사이의 역추적을 통해 최적의 경로를 찾아서 저장하고 해당 경로로 플레이어가 이동하게 만들것이다. pch.hmap 변수 parent 를 사용할 것인데 map 이 Pos 라는 구조체를 비교하여 자동정..
길찾기 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번 규칙은 부모노드의 자식 노드 뿐 아니라 해당 부모노..