programmingu

버블 정렬 알고리즘의 개념 서로 인접한 두 원소를 검사해 정렬하는 알고리즘 ⇒ 인접한 2개의 원소의 대소를 비교해 크기가 원하는 순서대로 (오름/내림차순 혹은 사용자가 정의한 Comparator) 되어 있지 않으면 서로 교환 제자리 정렬 : 정렬하고자 하는 배열 안에서 교환하는 방식. 입력 배열 (정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 ⇒ 공간복잡도 O(N) 과정 설명 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동 ⇒ 1 회전에서는 맨 끝에 있는 자료는 정렬에..

최소 신장 트리(MST) 그래프의 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 찾기! 어디에서 시작하는 지 상관없이 모든 정점이 다 이어질 수 있도록 팔을 뻗는다고 생각하면 된다. 간선이 적을 때 => KRUSKAL(간선 중심) 간선이 많을 때 => PRIM(정점 중심) Kruskal 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 모든 간선을 가중치에 따라 오름차순으로 정렬 (최초 한번) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 *** 사이클을 형성하는 간선은 선택 x!** ⇒ union-find 알고리즘을 이용한다. n-1 개의 간선이 선택될 때까지 반복해서 선택 사이클을 형성하는 방법 ⇒ union-find 추가하고자하는 간선의 양끝 정점이 같이 집합에 속해있..