Crat

7-1. 동적 계획법(Dynamic Programming)

1. 이항 계수(조합 ; Combination), 경우의 수 (1) 5개의 공 중에서 2개를 뽑는 경우의 수는? (2) 코드로 구현하기 #include #include using namespace std; int combination(int n, int r) { if (r == 0 || n == r) return 1; return combination(n - 1, r - 1) + combination(n - 1, r); } int main() { __int64 start = GetTickCount64(); int num = combination(45, 6); __int64 end = GetTickCount64(); cout

6-4. 프림 알고리즘(Prim Algorithm)을 이용한 미로 맵 만들기

0. vs Kruskal 크루스칼 알고리즘은 탐욕적인 방법을 이용하여 가장 작은 간선을 먼저 선택하는 방법을 이용하여 그룹을 합치고 경로를 발견했다. 프림 알고리즘은 랜덤의 정점을 기준으로 간선을 하나씩 수집하여 진행한다. (정점에서 이어진 간선들 중 최적의 간선을 선택) 그리고 간선으로 연결된 정점과 그룹화한다. 이 때 다음 간선을 확인하고 이전의 간선들과 비교했을 때, 다음 간선이 이전의 간선보다 훨씬 낮으므로 이전의 쓸모없는 간선은 사용하지 않는다. (위 그림에서 35에 해당하는 간선) - 다익스트라 알고리즘과는 다른점? 다익스트라는 시작점을 기준으로 코스트가 낮은 간선을 선택하지만 프림은 트리(정점 집합)을 기준으로 코스트가 낮은 간선을 선택한다. 1. 코드 수정 2023.07.25 - [자료 구..

6-3. 크루스칼 알고리즘을 활용한 미로 맵 만들기

0. 구상 사전에 사용했던 미로 맵을 Kruskal 알고리즘을 사용하여 만든다. (기존의 미로 맵은 탈출구가 있던 세로 줄과 가로 줄은 모두 초록색으로 길이 뚫려 있었다) 간선을 경로로 만들고, 코스트를 랜덤으로 생성할 것이다. Kruskal 알고리즘을 통해 코스트가 가장 작은 경로를 선택하여 도착점까지 향하도록 설정한다. 1. 코드 수정 1-2. 미로 만들기(2) - 오른손 법칙(우수법) 1. 오른손 법칙 미로를 탈출할 때 오른쪽 벽에 손을 대고 벽을 따라가면 언젠가는 탈출한다는 법칙이다. player의 진행방향을 기준으로 오른쪽으로 갈 수 있는지, 바라보고 있는 방향으로 갈 수 있 crat.tistory.com 위의 포스트에서 만들었던 미로를 수정하기 위해 GenerateMap을 수정한다. (1) C..

6-2. 최소 신장 트리(Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm)

1. 최소 신장 트리(최소 스패닝 트리 ; Minimum Spanning Tree) 최소한의 간선을 이용하여 모든 정점을 연결한 트리. (1) 순환이 발생하면 안됨 ex) 0 -> 1 -> 2 -> 0 -> 1 ... (2) 정점이 N개이면 간선은 N-1개 2. 크루스칼 알고리즘 (Kruskal MST Algorithm) 탐욕적인(greedy) 방법을 이용함. -> 지금 순간에 최적인 답을 선택하여 결과를 도출 - 원리 (1) 코스트가 가장 낮은 간선들을 선택 (2) 코스트가 가장 낮은 다른 간선을 연결 (3) 그 다음으로 코스트가 낮은 간선을 연결 반복 단, 연결 사이에 순환이 발생하면 안됨(MST의 조건에 미달) - 순환을 판단하는 방법 연결이 완료된 정점들을 그룹으로 관리한다. 이 때 같은 그룹내에..

6-1. 상호 배타적 집합 (Disjoint Set)

최소 스패닝 트리를 공부하기 전에, 최소 스패닝 트리에 적용되는 서로소 집합에 대해서 공부한다. 1. 상호 배타적 집합(서로소 집합) ; Disjoint Set - 공통 원소(혹은 공통 부분 집합)를 가지지 않는 집합, 교집합이 없는 집합들. ex) { 1, 2, 3 } 과 { 4, 5, 6 } 은 서로소 집합이다. (1) 유니온-파인드(Union-Find) 알고리즘 - 유니온 (Union) : 두 개의 서로소 집합을 하나로 합침. - 파인드 (Find) : 주어진 원소를 가지는 집합을 찾음. 주어진 원소의 루트 노드를 찾는 것이 목표. 2. 트리 구조를 이용한 표현 class NaiveDisjointSet { public: NaiveDisjointSet(int n) : _parent(n) { for (..

5-4. 해시 테이블(Hash Table)

0. map vs hash_map (std::unordered_map) (1) map ( C#의 dictionary와는 다름 ) - 균형 이진 트리의 트리 구조, 레드-블랙 트리로 구성되어 있음 - 키를 기준으로 자동으로 정렬해서 저장 - 시간 복잡도 : O( log N ) (2) hash_map (std::unordered_map, C#의 dictionary) - 메모리를 대가로 속도를 이점으로 가져감 - 삽입 순서에 따라서 저장 - 해시 충돌이 없으면 속도가 map에 비해 굉장히 빠름 - 시간 복잡도 : 데이터의 추가, 탐색, 삭제가 상수의 시간 복잡도를 가짐 => O(1) 1. 해시 테이블 ; unordered_map 키-값 쌍으로 이루어져 있으므로 특정 값에 접근하려면 키만 알면 됨. 그러나 키-..

5-3. 퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)의 원리 (1) 인덱스 지정 - 배열의 첫 값을 pivot(피벗)으로 지정 - 그 다음 값을 시작위치인 low로 지정 - 배열의 마지막 값을 high로 지정 (2) 인덱스 이동 - pivot >= arr[low] 일 때까지 low 인덱스를 1씩 증가시킴 - pivot low보다 커질 때 알고리즘을 종료 - arr[pivot] 과 arr[high] 교체 위의 알고리즘을 통해 피벗을 기준으로 좌측은 피벗 값보다 작게, 피벗을 기준으로 우측은 피벗 값보다 크게 정렬된다. 2. 퀵 정렬 구현 int Partition(vector& v, int left, int right) { int pivot = v[left]; int low = left + 1; int high = right..

5-2. 힙 정렬, 병합 정렬

1. 힙 정렬(Heap Sort) 힙의 특성을 이용한 정렬. void HeapSort(vector& v) { priority_queue pq; // 우선순위 큐를 내림차순으로 정렬 for (int num : v) // 벡터 v의 모든 값을 우선순위 큐에 대입 pq.push(num); v.clear();// 벡터 v를 비움 while (pq.empty() == false) // 우선순위 큐가 빌 때 까지 { v.push_back(pq.top()); // 벡터 v에 우선순위 큐의 값을 작은 순서대로 집어넣음 pq.pop();// 우선순위 큐의 맨 위 데이터 제거 } } 우선순위 큐는 힙 구조로 되어있다. 우선순위 큐를 내림차순으로 정렬되어 있기 때문에 가장 작은 값이 우선순위 큐의 Top에 위치한다. 우선순..