본문 바로가기

전체 글

 (231)
힙 정렬 힙 자료구조를 이용하는 정렬.O(nlogn)의 시간복잡도를 가진다. 맨 마지막 인덱스부터 정렬한다.void HeapSort(vector& v){ priority_queue, greater> pq; // O(NlogN) // pq 에 데이터를 push 할 때는 시간 복잡도 logN이다. // 그러나 여기서는 v의 모든 요소 N 개를 집어넣으니 NlogN이다. for (int num : v) pq.push(num); v.clear(); // O(NlogN) // 위와 같음 while (!pq.empty()) { v.push_back(pq.top()); pq.pop(); }}
삽입 정렬 삽입 정렬정렬할 배열의 원소를 하나씩 빼서 정렬한다.보통 배열을 하나 더 만들어서 값을 복사해오면서 정렬할거라 생각할수 있지만 실제로는 그렇게 구현하지 않고, 정렬할 배열의 왼쪽, 오른쪽 등의 기준으로 나누어 정렬한다.결국 시간복잡도 O(N^2) 이다.. 일반적으로 효율 안좋다. 배열을 안쪽 for 문을 돌 때 마다 인덱스 i 까지의 배열 요소들이 정렬된다.예) i == 3 이면 v[0]~v[3] 까지의 요소들이 정렬된다. 즉, 안쪽 for 문 돌 때마다 정렬이 특정 범위까지 계속 일어난다.  void InsertionSort(vector& v){ const int n = (int)v.size(); for (int i = 1; i =0; --j) { if (v[..
선택 정렬 선택 정렬배열을 전체 스캔을 통해서 가장 우선순위가 되는 원소를 맨 앞으로 이동시킨다. 즉, 버블 처럼 순간순간 비교하여 바꾸는 것이 아니라 배열 전체 스캔 후 1번. 이것을 정렬이 끝날 때 까지 반복한다. 버블 정렬보다는 성능이 좋지만 O(N^2) 이다. 좋지 않음 void SelectionSort(vector& v){ const int n = (int)v.size(); for (int i = 0; i
버블 정렬 버블 정렬시간 복잡도는 명령어가 몇 번 실행되는지 확인한다.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 라는 구조체를 비교하여 자동정..

티스토리툴바