lower_bound, upper_bound

우선 lower_bound와 upper_bound는 이진 탐색(Binary Search)을 기반으로 탐색하는 함수이다.

따라서 배열이나 리스트, 벡터 등이 기본적으로 정렬이 되어있어야 하고, 시간복잡도는 O(logn)이다.

기본적으로 이진 탐색은 찾고자 하는 원소가 있는지, 있다면 어디에 위치해 있는지를 찾는다면,

lower_bound와 upper_bound는 이진 탐색을 바탕으로 원소가 어느 부분에 속할 수 있는지를 알려주는 함수이다.

lower_bound

• 용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
• 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함

upper_bound

• 용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
• 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함
  

code example

#include<iostream>
#include<vector>

int main() {

	vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 };
	cout << "5 이상 11 이하의 갯수 : " << upper_bound(arr.begin(, arr.end(), 11) - lower_bound(arr.begin(), arr.end(), 5);

	return 0;
}

graph

MST 알고리즘

정점 -1개의 가선으로 이루어진 신장트리 중에서 가중치의 합이 가장 작은것. 고르는 간선은 사이클을 만들이 않아야 하고, 가중치가 작은 것들부터 골라져야 한다.

크루스칼

MST 의 목적을 이루기 위해 간선들을 가중치 오름차순으로 "정렬"해두고, 사이클을 만들지 않는 간선이라면 골라나가서 n-1개를 고르면 완료.

프림

정점을 고르는 정점 중심 MST 목적을 이루기 위해 정점들을 선택된 집합과 선택되지 않은 집합으로 나누고, 선택된 집합으로부터 뻗어나가 선택되지 않은 집합의 정점으로 이어지는 간선 중에 제일 작은 것을 골라나가며 모두 편입되면 완료.

최단 경로

다익스트라 알고리즘

정점을 고르는 정점 중심

출발 정점으로부터 다른 모든 정점까지의 거리를 선택된 정점을 지나서 가는 경우와 직접 가는 경우 중 최솟값을 갱신해가면서 가장 가까운 정점을 하나씩 선택된 정점에 편입시켜가며 최단경로를 갱신. 음의 가중치를 허용하지 않는다.

동작 원리

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.
2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.
3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.
4. 2~3번 과정을 반복한다.

플로이드 와샬 알고리즘

모든 정점들에 대한 최단 경로.

벨만 포드 알고리즘

다익스트라 알고리즘과 동일하지만 벨먼 포드 알고리즘은 음의 가중치 허용한다.