일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- CPP
- 추천 시스템
- neural network
- petal to metal
- C++
- 컴퓨터 비전
- 신경망
- SVM
- cs231n
- Vision
- 비용함수
- recommender system
- Kaggle
- logistic regression
- 파이썬
- Unsupervised learning
- Computer Vision
- Support Vector Machine
- 백준
- Regularization
- OpenGL
- 머신러닝
- CNN
- 그래픽스
- SGD
- 딥러닝
- 인공지능
- 로지스틱 회귀
- 컴퓨터 그래픽스
- pre-trained
- Today
- Total
kwan's note
9-11주차- heap, graphs (힙과 그래프) 본문
9-11주차- heap, graphs (힙과 그래프)
kwan's note 2020. 12. 28. 03:09수강기간: 2020.09-2020.12
출처: 고려대학교 정연돈교수님 자료구조 수업
힙은 binary 트리이지만 bst와는 다르게 노드의 크기를 기준으로 좌우로 크기를 나눈것이 아닌 매 루트의 크기가 전체 트리에서 가장 작거나 가장 큰 tree를 말한다.
그림으로 차이를 보면 다음과 같다.
MIN heap은 루트가 가장 작은경우
MAX heap은 루트가 가장 큰 경우를 말한다.
힙의 장점은 가장 크거나 작은 값을 바로 찾을 수 있다.
힙은 array를 통해서도 비교적 효과적으로 구성할 수 있다.
complete tree이므로 2n+1이 왼쪽자식 2n+2가 오른쪽 자식 노드가 된다.
힙의경우 insert, delete의 과정에서
다시 힙으로 만드는 reheap의 과정이 필요하다.
힙에 insert하는경우의 reheap up 과정은 다음과 같다.
마지막 자리에 insert한 후 부모노드와 비교하며 올라간다.
recursive한 방법으로 구현한 코드는 아래와 같다.
힙의 첫번째 노드를 delete 하는경우의 reheap down 과정은 다음과 같다.
빈 자리에 left노드 또는 right노드를 넣고 reheap down과정을 반복한다.
그래프는 tree보다 일반적인 형태로 노드와 엣지의 집합이다.
방향이 존재할수도 없을수도 있으며 엣지의 크기도 존재할 수 있다.
연결성을 기준으로 강하게연결, 약하게연결, 떨어진 그래프 등으로 나타낸다.
그래프의 연결을 matrix로 표현하기도 하는데 이를 adjacency matrix라고 한다.
연결된 부분(갈 수 있는 방향)을 1로 표시한다.
그래프의 깊이우선탐색 순서는 다음과 같다.
Spanning트리는 각 엣지간에 단일연결로 된 트리를 말한다.
그중에서도 MST(minimum spanning tree는 cost가 가장 낮은 spanning tree를 말한다)
이를 만드는 방식으로는 크루스칼의 방법
프림의 방법
솔린의 방법등이 있다.
세 방법 모두 greedy 한 방식으로(각 회차마다 단기적으로 최선의 방식을 취하여 최종적으로 합함)구한다,
그중 프림의 알고리즘은 다음과 같다.
1. 한 노드를 선택하고 완성집합에 삽입한다.
2. 선택된 노드에 연결된 엣지들을 엣지 리스트에 삽입한다.
3. 엣지 리스트에서 최소거리를 가지고 해당 엣지에 연결된 인접 노드들이 완성집합에 들어있다면, continue
들어있지 않다면, 해당 엣지를 선택 후 해당 엣지 정보를 '최소 신장 트리'에 삽입한다.
4. 추출한 엣지를 엣지리스트에서 제거한다.
5. 더이상 진행을 할 수 없을때까지 반복한다.
'Computer Programming > Data Structure -Korea Univ' 카테고리의 다른 글
6-8주차 트리(tree, bst, avl tree) (0) | 2020.12.28 |
---|---|
3,4주차 -stack queue (0) | 2020.12.27 |
2주차-recursion (재귀함수) (0) | 2020.12.27 |
1주차 - 자료구조 개요 (0) | 2020.12.27 |
자료구조 강의 (0) | 2020.12.27 |