Crat

2-5. 다익스트라(Dijkstra) 알고리즘

0. BFS의 한계 (1) 연결된 간선들을 동일한 비용이라고 가정 -> 거리에 따른 가중치가 없음 (2) 인접한 정점을 모두 예약, 방문하기 때문에 낭비가 있음 다익스트라 알고리즘에서는 가중치를 비교하므로 비용이 크면 방문하지 않음 1. 다익스트라(Dijkstra) 알고리즘 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘. (1) 시작 정점에서 가장 가까운 정점을 선택 (2) 다른 노드로 가는 최단 거리 계산 (3) 방문하지 않은 정점에서 최단 거리를 가지는 정점 선택 (4) 해당 정점을 거쳐 다른 정점으로 가는 경로의 최단 거리 계산 ... (반복) - 거리는 다음 정점(자식)을 기준으로 이전 정점(부모)의 가중치와 그 다음 정점의 가중치를 더한 값이다. 2. 가중치 그래프 구현 stru..

2-3. BFS - 너비 우선 탐색

1. BFS(Breadth First Search) ; 너비 우선 탐색 큐를 이용하여 시작 정점과 거리가 가까운 순으로 탐색. (0 -> 1 -> 3 -> 2 or 4) 길찾기에 주로 사용됨. 시작 정점에서 가장 가까운 다음 정점들을 큐에 넣는 식으로 작동한다. 2. 여러 가지 방법 (1) 단일 리스트 방법 struct Vertex { }; vector vertices; vector adjacent; vector visited; void CreateGraph() { vertices.resize(6); adjacent = vector(6); adjacent[0].push_back(1); adjacent[0].push_back(3); adjacent[1].push_back(0); adjacent[1].pus..

2-2. DFS - 깊이 우선 탐색

1. DFS(Depth First Search) ; 깊이 우선 탐색 깊이를 우선으로 탐색하는 알고리즘. struct Vertex { }; vector vertices; vector adjacent; vector visited; void CreateGraph() { vertices.resize(6); adjacent = vector(6); adjacent[0].push_back(1); adjacent[0].push_back(3); adjacent[1].push_back(0); adjacent[1].push_back(2); adjacent[1].push_back(3); adjacent[3].push_back(4); adjacent[5].push_back(4); } 위의 그래프 사진과 같이 정점들과 연결 상태..

2-1. 그래프 기초

1. 그래프 종류 (1) 가중치 그래프(Weighted Graph) 요소들의 연결 관계 뿐 아니라 어떤 연결적 특징이 있는지 가중치를 이용하여 나타냄. (2) 방향 그래프(Directed Graph) 화살표를 이용하여 연결 관계의 방향성을 나타낼 수 있다. 2. 위의 방향-가중치 그래프 표현하기 void CreateGraph_1() { struct Vertex { vector edges; // 간선들의 목록 }; vector v; v.resize(6); v[0].edges.push_back(&v[1]); v[0].edges.push_back(&v[3]); v[1].edges.push_back(&v[0]); v[1].edges.push_back(&v[2]); v[1].edges.push_back(&v[3]..

1-8. 오른손 법칙 개선하기

0. 시간 복잡도 (1) 동적 배열 ; vector (1-1) push_back : O(1) - 상수 초 (1-2) 중간 삽입 / 삭제 : O(N) - 요소의 개수 만큼 복사 / 이동이 발생 (1-3) 임의 접근 : O(1) (2) 이중 연결 리스트 ; list (2-1) 삽입 / 삭제 : O(1) (2-2) 임의 접근 : O(N) - 요소의 포인터를 타고 타고... (3) 스택 : O(1) (4) 큐 : O(1) 1. 오른손 법칙 개선 지금의 우수법 방법은 갈 필요가 없는 곳도 진행해야한다. 따라서 앞으로 갈 곳에 대한 정보를 스택에 저장해서 사용한다. (1) Player.cpp void Player::Init(Board* board) { //~~~~ stack s; for (int i = 0; i <..

1-7. 큐(Queue)

1. FIFO(First In First Out) - 큐의 자료 구조 선입선출. 먼저 들어온 데이터가 먼저 나간다. 대기열 등에서 쓰임. 2. 문법 (1) 데이터 삽입 ; push int main() { queue q; q.push(1); q.push(2); q.push(3); (2) 가장 앞에 있는 원소 추출 ; front, 데이터 삭제 ; pop int data = q.front(); q.pop(); (3) 원소 개수 ; size int size = q.size(); (4) 모든 데이터 추출하기 ; empty while (q.empty() == false) { int data = q.top(); q.pop(); } 3. 구현 동적배열(vector)로 구현하려고 하면 일부 기능이 지원되지 않는다. (p..

1-5. 이중 배열 리스트(List) - 구현 복습

0. 필요성 vector가 list에 비해 얻는 편의성이 높기 때문에 대부분 vector를 사용하지만, 앞으로 공부할 자료 구조가 list가 기초가 되기 때문에 연습이 필요하다. 1. vector와 다른점? (1) push_front가 존재 vector는 데이터 수정을 위해서 각 요소를 한칸씩 미는 것이 복사 - 이동의 순서를 거치기 때문에(비효율적) 제공하지 않는 기능이다. (2) 중간 삽입 삭제가 효율적 (3) 이전 / 다음 노드를 가리키는 포인터를 저장 (4) list는 임의 접근이 불가능하기 때문에, 각 노드들을 타고 가서 찾는다 (5) insert가 존재 중간에 삽입하는 insert가 존재한다. insert('삽입 위치의 바로 다음','삽입할 값') // return 값은 반복자이다. 2. No..

1-4. 동적 배열(vector) - 구현 복습

1. 소멸자 소멸자 호출 시에 data 배열을 삭제 2. push_back (1) size와 capacity의 크기가 같게 되면 용량의 확장이 발생 (2) capacity와 새로운 capacity가 동일하면(capacity가 0이었을 때 발생함) 1 증가시켜야 함. (3) reserve 함수를 호출해서 새로운 capacity 값을 전달 (4) _size 인덱스의 값에 매개변수를 전달 (5) size의 크기를 증가시킴 3. reserve (1) 기존의 capacity는 매개변수의 값보다 작을 수 없음(축소불가). (2) capacity 값을 대입 (3) 데이터 복사 전에 새로운 메모리 영역을 capacity로 동적 할당해야함. (4) 새로운 데이터 영역에 기존 데이터를 복사 (5) 기존 데이터 영역 할당 ..