눈물보다 땀을

하나의 시작점으로 구성된 트리에 간선을 하나씩 수집하며 진행

MST를 만들 수 있다.

다익스트라는 시작점을 기준 최단 cost

프림은 트리(정점집합)을 기준 최단 cost

하나의 시작점으로 구성된 트리에 간선을 하나씩 수집하여 진행

- 다익스트라는 시작점을 기준으로 cost 계산

- 프림은 트리의 정점집합을 기준으로 cost 계산

- 탐욕적인(greedy) 방법과 Disjoint Set을 이용하여 MST(Minimum Spanning Tree)를 구한다.

구현 방법 Steps

1. 최소 코스트 경로를 임의로 선택

2. DisjointSet을 이용하여 해당 경로가 사이클이 발생 했는지 체크

3. 다음 최소 코스트 경로를 기준으로 step 반복

제시된 상황

1. 최소 경로 중 임의 경로 선택

2. 선택된 경로 중 싸이클이 발생 했는지 확인

3. DisjointSet을 이용하여 경로 채택 여부 판단

Result

PPT

버블정렬

- 배열의 앞뒤 요소를 비교해가면서 가장 큰 값을 배열의 맨뒤로 보내는 방식

- O(n^2)

선택정렬

- 배열을 순회 하면서 가장 찾은 값을 찾아서 맨 앞에 위치와 바꾸는 방색

- 버블 정렬과 달리 매번 값을 바꾸는게 아닌 가장 찾은 값 인덱스를 찾고 한번만 swap이 일어난다.

- O(n^2)

삽입정렬

- 새로운 배열에 선택된 값을 정렬된 위치에 넣는 방식으로 정렬이된다.

- 기존에 데이터가 정렬된 상태라면 조금 더 유리하다.

- O(n^)

힙

- 힙트리를 이용한 정렬

- O(NlogN)

병합

- 분할, 정복, 결합

- 개념이 중요함

- 멀티스레드에서 분할해서 정복하고 같이 결합하는 방식 등으로 활용될 수도 있는 개념이다.

- O(NlogN)

퀵

- 최악 O(N^)

- 평균 O(NlogN)

- 병합은 임시 벡터를 만들기 때문에 퀵정렬이 평균적으로 더 빠를 수 있다.

이진 탐색

특징

- 데이터가 정렬되어 있을때 가능하다.

- 데이터를 배열 형태 정렬된 데이터를 들고 있으면 중간 데이터 접근이 빠르나, 데이터를 중간 삽입/삭제이 느리다.

- 데이터를 리스트 형태로 정렬된 데이터를 들고 있으면 임의접근이 빈번이 일어나는 이진탐색에서 비효율적이다

이진탐색트리

특징

- 데이터를 이진트리에 정렬된 데이터를 갖고 있으면 탐색 속도와 중간 데이터 삽입/삭제, 배열과 리스트의 이점을 모두 만족하는 이진탐색이 가능하다.

- 이진탐색트리를 이용할 경우, 이진 균형 트리 형태일 때 이진탐색이 시간복잡도lon2N으로 동작한다. 한쪽에 데이터가 치우져 있으면 일반 연결리스트와 다를바 없다.

- 이진 균형 트리의 종류에는 avl, red-black tree 등이 있다.

특징

- 길찾기 목적지가 있음

- 목적지가 있기 때문에 탐색 경로를 선정하는 cost 값이 다익스트라랑 달라짐

- cost 값은 F = G + H .

- G : 시작부터 현재 위치까지의 코스트

- H : 현재위치에서 도착지까지의 코스트

Flow

샘플 프로젝트

c++

c#

참고

특징

- 이동 가능한 정점을 찾는 로직을 우선순위 큐를 사용하여 개선 시킬 수 있다.

- 정점(노드) 정보를 배열이 아닌 딕셔너리 형태로 개선 시킬 수 있다.

- 가중치 그래프에 사용 적합

- bfs 길찾기와 마찬가지로 목적지는 따로 지정하지 않는다.

- 엉뚱한 길로 가기 떄문에

- 가장 좋은 후보를 찾을때 우선순위 큐를 통해서 최적화 가능하다

Flow

참고