Developer Ahn

- interpolation search

- 사전이나 전화번호부를 탐색하는 방법과 같이 탐색 키가 존재할 위치를 예측, 비례식 이용

- 탐색 위치 = (k-list[low]) / (list[high]-list[low] * (high-low) + low

- 시간복잡도: 

- binary search

- 정렬된 배열에서의 탐색

- 재귀 호출, 반복을 이용하여 구현 가능 

- 시간복잡도: 

- sequential search

- 정렬여부 상관없이 비슷한 성능

- 시간복잡도: 

- 개선된 순차 탐색
 : 비교 횟수를 줄이는 방법

int seq_search2(int key, int low, int high) 
{
    int i;
    list[high+1] = key;
    for(i=low; list[i] != key; i++) // 키 값을 찾으면 종료
        ;
    if(i==(high+1)) return -1; //탐색 실패
    else return i;             //탐색 성공
}

- topological sort

- 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

- 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부속된 모든 간선을 삭제 -> 반복

- 사이클이 있는 경우 위상정렬 불가

- Floyd

- 최단 경로 알고리즘

- 모든 정점 사이의 최단 경로를 구하려면 다익스트라의 알고리즘을 정점의 수만큼 반복 실행, But 모든 정점 사이의 최단 거리를 구하려면 더 간단한 알고리즘으로 플로이드 알고리즘

- 2차원 배열을 이용하여 3중 반복을 하는 루프로 구성

- distance 배열없이 그래프를 갱신함.

- 다익스트라로 모든 정점의 쌍으로 최단 경로를 구하려면 알고리즘 n번 반복, 전체 복잡도는 

- 시간복잡도: 

- Dijkstra

- 최단 경로(shortest path) 알고리즘

- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

- distance[w] = min(distance[w], distance[u] + weight[u][w])

- 시간복잡도
  : 선형탐색일 경우 
  : 이진 힙을 이용하면 실행 시간은  시간이 되고, 피보나치 힙을 통해  시간까지 개선할 수 있다.

- Prim

- 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법, 정점 선택 기반

- 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함

- 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장

- 시간복잡도 

 => 희박한 그래프를 대상으로 할 경우에는 크루스칼의 알고리즘이 적합, 밀집한 그래프의 경우에는 프림 알고리즘이 유리

- Kruskal

- 탐욕적인 방법(greedy method), 간선 선택 기반  

- 간선들을 가중치의 오름차순으로 정렬, 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가

- 시간복잡도 

- union-find 연산 (사이클, 집합)

#define MAX_VERTECS 100

int parent[MAX_VERTECS]; // 부모 노드
int num[MAX_VERTECS]; // 각 집합의 크기

// 초기화
void set_init(int n)
{
	int i;
	for(i=0; i<n; i++) {
		parent[i] = -1;
		num[i] = 1;

	}
}

// vertext가 속하는 집합을 반환한다.
int set_find(int vertex)
{
	int p, s, i = -1;
	for(i = vertex; (p=parent[i])>=0; i=p) // 루트 노드까지 반복
		;
	s = i; // 집합의 대표 원소(최상위 부모노드)
	for(i = vertex; (p=parent[i])>=0; i=p)
		parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정
	return s;
}

// 두 개의 원소가 속한 집합을 합친다.
void set_union(int s1, int s2)
{
	// 연산량을 줄이기 위해 정점의 개수가 적은 트리의 루트가 큰 트리의 루트를 가리키도록 함
	if(num[s1] < num[s2]) { 
		parent[s1] = s2;
		num[s2] += num[s1];
	}
	else {
		parent[s2] = s1;
		num[s1] += num[s2];
	}
}