알고리즘 복습7

• 

  알고리즘 복습) 기본 정렬(버블/선택/삽입) 기본 정렬 정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을때, 이를 정해진 기준에 맞게 정렬하여 출력하는 알고리즘이다. 기본 정렬에는 버블/선택/삽입 정렬이 있으며, 이는 모두 O(N²)의 시간복잡도를 가진다. 버블정렬 버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. //버블정렬 void Sort::Bubble(vector& v) { for (int j = v.size(); j > 0; j--) { for (int i = 0; i v[i + 1])::swap(v[i], v[i + 1]); } } } } 선택정렬 선택정렬은 주어진 리스트 중에 최소값을 찾 그 값을 맨 앞에 위치한 값과 교체한다.그리고 맨 처음 위치를 뺀 나.. 알고리즘 복습/정렬 2022. 2. 28.

• 

  알고리즘 복습) 이진 탐색 트리 이진 탐색 트리 이진 탐색 트리는 이진 트리 기반의 탐색을 위한 자료 구조이다. 이진 탐색 트리를 알기 위해선 먼저 이진 탐색을알아야 한다. 이진탐색 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 임의의 접근을 허용해야되는 탐색의 특성상 연결리스트를 사용하기는 부적합하며 vector나 배열같은 것을 사용하는 것이 바람직하다. 시간 복잡도는 log(n)이다. // 이진 탐색 vectornum; void BinaryTree(int N) { int left = 0; int right = num.size() - 1; bool correct=false; while (left6-.. 알고리즘 복습/탐색트리 2022. 2. 20.

• 

  알고리즘 복습)우선순위 큐/힙 우선순위 큐 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙트리를 이용하여 구현한다. 기본적으로 내림차순(less)으로 설정되어 있지만, Predicate를 설정하여 오름차순(greater)으로 변경할수 있다. 힙트리 힙트리는 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙트리 구조 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.(완전 이진 트리) 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야한다. i번 노드의 왼쪽 자식/오른쪽 자식/부모는 각 각 [(2*i)+1]/[2*i+2]/[(i-1)/2]이다. 힙 트리 특징 부모 노드가 가진 값은.. 알고리즘 복습/힙&우선순위 큐 2022. 2. 10.

• 

  알고리즘 복습)트리 기초 트리 트리란 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다. 그래프와 동일하게 노드와 간선을 가지고 있으나, 계층이 있다는 점에서 그래프와 차별점을 갖는다. 트리의 특징 트리는 다음과 같은 특징을 갖는다. 1.오직 하나의 루트 노드를 갖는다. 2.루트노드와 자식노드들은 0개 이상의 자식을 갖는다. 3.모든 자식노드는 하나의 부모노드만을 갖는다. 4.N개의 노드가 있을경우 항상 N-1개의간선을 갖는다. 트리 용어 루트 노드(root node) : 최상위 노드이며, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드, leaf 노드라고도 부른다. 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름) 형제(sibling): 같은 부모를 가지.. 알고리즘 복습/힙&우선순위 큐 2022. 2. 6.

• 

  알고리즘 복습) BFS(너비 우선 탐색) BFS BFS는 맹목적 탐색 방법중 하나로, 최단 경로 혹은 임의의 경로를 찾을때 매우 유용하다. BFS구현 그래프는 지난 포스팅의 그래프를 활용한다. [알고리즘 복습/그래프] - 알고리즘 복습) DFS(깊이 우선 탐색) 알고리즘 복습) DFS(깊이 우선 탐색) DFS 깊이 우선 탐색은 맹목적 탐색방법으로써 길을 탐색할 때 한 방향으로 이동 가능 할 때까지 탐색한 후 더 이상 이동이 불가 하면 마지막 갈림길로 돌아가 다른 방향으로 다시 탐색을 진행하 pjnull.tistory.com void BFS(int here)//인접리스트 { vectorparent(6,-1); vectordistance(6,-1); queueq; q.push(here); visited[here]=true; parent[here]=.. 알고리즘 복습/그래프 2022. 2. 5.

• 

  알고리즘 복습) DFS(깊이 우선 탐색) DFS 깊이 우선 탐색은 맹목적 탐색방법으로써 길을 탐색할 때 한 방향으로 이동 가능 할 때까지 탐색한 후 더 이상 이동이 불가 하면 마지막 갈림길로 돌아가 다른 방향으로 다시 탐색을 진행하는 방법이다.이러한 DFS는 그래프의 전체구조 및 관계도 파악에 매우 유리하다. DFS구현 그래프는 다음의 그래프를 사용한다. struct Vertex{}; vectorver; vectoradjacent; vectorvisited(6,false); void CreateGraph()_1//인접 리스트 { ver.resize(6); adjacent=vector(6); adjacent[0].push_back(1); adjacent[0].push_back(3); adjacent[1].push_back(0); adjacent[.. 알고리즘 복습/그래프 2022. 2. 5.

• 

  알고리즘 복습) 그래프 기초 그래프 우리가 흔히 그래프라고 알고 있는 것은 시각화된 차트나 다이어그램일 것이지만, 알고리즘에서의 그래프는 사물 혹은 추상적인 개념간의 연결관계를 표현한 것이다. 이러한 그래프는 정점(Vertex)와 간선(Edge)들로 이루어져있다. 정점(Vertex):데이터를 표현(사물,개념) 간선(Edge):정점들(Vertex)을 연결하는데 사용 사용할 그래프 이번 포스팅에서 사용할 그래프는 가중치 그래프와 방향그래프 두가지이다. 가중치 그래프 가중치 그래프는 연결관계를 나타낼뿐 아니라 이들의 관계에서 숫자를 기입하여 중요도등을 나타낼수 있는 그래프이다. ex)지하철 노선도 방향 그래프 방향 그래프는 양방향으로 연결된것이 아닌 특정 방향으로 연결관계를 나타내는 것을 의미한다. ex)일방통행이 포함된 도로망, 상호작.. 알고리즘 복습/그래프 2022. 2. 5.