Computer Science/Algorithm 썸네일형 리스트형 최소 신장 트리 신장 트리 개념 그래프 내의 모든 정점을 포함하는 트리 n개의 정점으로 이루어진 무방향 그래프에서 n-1개의 간선으로 이루어진 트리 특징 하나의 트리에는 다수의 신장트리가 존재할 수 있음 모든 정점들이 연결되어 있어야 하며, 싸이클을 포함해서는 안된다. 최소 신장 트리 개념 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 특징 가중치의 합이 최소여야 함 n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야함 사이클이 포함되면 안됨 활용 그래프에서 최소 비용을 구할때 활용 ※구현 방법 Prim 알고리즘 개념 하나의 정점에서 출발하여 연결된 간선들 중 하나씩 선택하면서 MST를 만들어나가는 방식 시간 복잡도 O(n^2) 특징 정점 선택 기반 이전의 ms.. 더보기 이진트리 정의 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리 왼쪽 자식 노드 / 오른쪽 자식 노드 두 자식 노드는 서로 완전히 다름 특성 레벨 i에서의 최대 노드 갯수: 2^i개 높이가 h인 이진 트리의 최소,최대 노드 수 : (h+1), (2^(h+1)-1) 종류 포화 이진트리 완전 이진트리 노드의 수가 n개일 때, 노드 1~n까지 빈자리가 없는 이진트리 편향 이진트리 높이 h에 대한 최소 갯우의 노드를 가진 트리 한쪽 방향의 자식 노드만 가진 이진트리 순회 특징 각 노드를 중복 없이 방문 비선형 구조이기 때문에 선후 연결관계를 알 수 없음 방법 전위순회 (VLR) def preorder(T): if T: visit(T.data) preorder(T.left) preorder(T.right) 중.. 더보기 정렬 종류 종류 시간 복잡도 버블 정렬 (Bubble Sort) O(n^2) 선택 정렬 (Selection Sort) O(n^2) 퀵 정렬 (Quick Sort) O(nlogn) 삽입 정렬 (Insert Sort) O(n^2) 병합 정렬 (Merge Sort) O(nlogn) 버블 정렬 (Bubble Sort) 개념 맨 앞에 있는 수부터 기준으로 잡는다. 기준으로 잡은 수를 다음에 있는 수와 비교했을 때, 더 크다면 자리를 서로 바꾸고 계속 다음 수와 비교하면서 정렬하는 방법이다. 뒤에서부터 가장 큰 수가 채워진다. 시간 복잡도 최악의 경우 n-1개의 정점을 기준으로 삼으면서 비교하고, 모두 자리 교환을 해야 하므로 O(n^2)이다. O((n-1) * (n-1)!) = O(n^2-2n+1) = O(n^2) 코.. 더보기 그래프 순회 (DFS & BFS) 종류 탐색방법 구현 방법 활용 시간복잡도 DFS 재귀, Stack 백트래킹 O(V^2) BFS Queue 최단경로 인접 리스트: O(V+E) 인접행렬: O(V^2) DFS (Depth First Search, 깊이 우선 탐색) 개념 한 루트에서 최대한 깊숙이 들어가면서 탐색한 후, 다시 돌아와 다른 루트로 탐색하는 방법 장단점 장점 단점 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 적다 해가 없는 경로에 깊이 빠질 가능성이 있음 목표 노드가 깊은 레벨에 있을 경우 해를 빨리 구할 수 있다. 얻어진 경로가 최단 경로라는 보장이 없다. 따라서, 최단경로를 구하기 위해서는 전체 경로를 다 돌아본 후 비교해야 한다. 구현 방법 재귀: 스택보다 속도는 빠르나 깊이가 너무 깊어지면 재귀 한도를 초과할 .. 더보기 이전 1 다음
