최소 신장 트리
- 크루스칼 알고리즘
- 간선의 가중치를 기준으로 그래프를 다시 생성하여 MST를 생성.
- 간선을 가중치 순서대로 선택하면서 사이클을 만들지 않도록 한다.
- 시간복잡도는 O(ElogE)이다
- 프림 알고리즘
- 크루스칼 알고리즘과 달리 정점을 기준으로 최소 비용 신장 트리를 생성.
- 임의의 정점을 선택하고, 해당 정점과 연결된 정점의 거리를 갱신하여 짧은 정점을 선택한다.
- 시간복잡도는 O(V^2)이다.
- 솔린 알고리즘
- 그리드 알고리즘이다.
- 그래프의 각 정점에 인접한 최소 가중치 간선을 찾아서 그 간선들을 숲에 추가
- 현재까지 구성된 각 트리에서 다른 트리로의 최소 가중치 간선을 찾아서 그 간선들을 숲에 추가하는 유사한 과정을 반복
- 각 반복마다 그래프의 각 연결 구성 요소 내에서 트리의 수를 이전 값의 최대 절반으로 줄인다.
- 시간복잡도는 O(E log V)이다.
- E >> V일 경우 크루스칼 알고리즘보다 유리하다.
구현 + 시뮬레이션
- 여러 메인함수에 부속이 서브함수들을 알맞게 생성하면서 기능이 유기적으로 잘 작동되게 코드를 작성하는 것이 중요하다.
정렬
- bubble sort: O(n^2) for문을 순회하면서 자신보다 큰 값들 뒤로 원소 이동
- merge sort: O(nlogn) while or 재귀를 사용하여 리스트를 반으로 계속 쪼갠 후 다시 merge해주는 함수
- quick sort: 평균적으로 O(n log n), 최악의 경우 O(n^2), 분할 정복 기법으로 정렬한다. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한 후 각각에 대해 재귀적으로 정렬한다.
- heap sort: 스트를 힙으로 만든 후, 최상단의 루트 노드를 빼내고 남은 요소들을 다시 힙으로 만들어 정렬을 진행한다.
- Tim sort: 병합 정렬과 삽입 정렬의 결합한 함수이다.
그리디 알고리즘
- 그리디 알고리즘은 각 단계에서 최적의 선택을 한다.
- 이 선택은 그 순간에는 최적이지만, 전체적으로 보면 항상 최적해를 보장하지는 않는다.
- 왜 그 선택이 정당한지를 증명하는 것이 중요하며, 실제 구현 자체는 어렵지 않은 편이다.
이진 탐색
- 정렬된 자료에서만 사용할 수 있다.
- 반복문 or 재귀를 통하여 구현된다.
- 첫 값과 끝값을 알아야 하며, 데이터의 중앙값을 알 수 있어야 한다.
'Diary > WIL' 카테고리의 다른 글
2024-03-17 WIL - Websocket 에 대해서 (0) | 2024.03.17 |
---|---|
2024-03-10 WIL (0) | 2024.03.10 |
2024-03-03 Spring Boot JPA를 사용하기 위해서 (0) | 2024.03.03 |
2024-02-18 WIL (0) | 2024.02.18 |
2024-02-11 WIL (0) | 2024.02.11 |