본문 바로가기
728x90

ALGORITHM/개념 정리15

[Algorithm] 그래프 그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 .. 2021. 10. 20.
[Algorithm] 병합 정렬, 퀵 정렬 병합 정렬 (Merge Sort) 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘 활용 자료를 최소 단위까지 나눈 후, 차례대로 정렬하여 최종 결과 얻어냄 top-down 방식 시간 복잡도 : O(nlogn) # 병합 def merge(left, right): # left: [1] # right: [3, 4, 5] result = [] while len(left) > 0 and len(right) > 0: if left[0] 0: result.extend(right) if len(left) > 0: result.extend(left) return result # 분할 def merge_sort(arr): if len(arr) right: break # 만.. 2021. 10. 6.
[Algorithm] 힙 (Heap) 힙(heap) 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰/작은 노드를 찾기 위해서 만든 자료구조 힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있음 최대 힙 (max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 > 자식 노드의 키 값} 루트 노드 : 키 값이 가장 큰 노드 최소 힙 (min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 < 자식 노드의 키 값} 루트 노드 : 키 값이 가장 작은 노드 삽입 연산 삭제 연산 힙에서는 루트 노드의 원소만을 삭제할 수 있음 루트 노드의 원소를 삭제하여 반환 힙의 종류에 따라 최대값 또는 최소값 구할 수 있음 2021. 10. 3.
[Algorithm] Tree 트리 (Tree) 그래프 자료구조 중 하나 그래프와 트리의 차이점 싸이클 존재 여부 : 트리는 싸이클이 없다! 루트 노드가 반드시 하나 부모 노드가 반드시 하나 트리는 일반적인 경우, 암묵적으로 방향 표기x (단방향) 비선형 구조 : 원소들 간에 1 : n 관계 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 용어 정리 트리 : 한 개 이상의 노드로 이루어진 유한 집합 부 트리 (subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리, 최상위 노드를 제외한 나머지 노드들은 분리집합으로 분리가능 -> 이는 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리 노드 (node) : 트리의 원소 (A, B, C, D, E, F, .. 2021. 10. 3.
728x90

티스토리툴바