2024-02-25 WIL

최소 신장 트리

• 크루스칼 알고리즘
  • 간선의 가중치를 기준으로 그래프를 다시 생성하여 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 재귀를 통하여 구현된다.
• 첫 값과 끝값을 알아야 하며, 데이터의 중앙값을 알 수 있어야 한다.