-
자, 오늘은 일요일.
벌써 해도 졌고 빨리 빨리 시작하자.
Part1. 딥러닝을 시작하기전에
CH02-09. 우선순위 큐
&
CH02-10. 그래프의 표현
CH02-09. 우선순위 큐
앞서 스택, 큐, 덱, 이진 탐색 트리를 알아 보았다면 이번에는 우선순위 큐를 알아보고자 한다.
■ 우선순위 큐란?
"우선 순위에 따라서 데이터를 추출하는 자료구조."
컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용된다. / 그리고 힙(heap)을 이용해 구한현다.
힙(heap) 에 대해서 좀 자세히 다뤄줄 줄 알았는데, 난중에 알려주나 보다
(ex. 음악 들으면서 문서작성과 같은 여러 프로그램을 동시에 동작 시킬때, 운영체제가
프로그램의 우선순위를 정하는 경우가 많다!)
★ 복습
자료 구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입 데이터 우선순위 큐 가장 우선순위가 높은 데이터 
■ 우선순위 큐의 특징
- 우선순위 큐 구현방식에 있어 리스트 자료형의 경우 삽입/삭제시간 : O(N)
힙(Heap)의 경우 삽입/삭제시간 : O(logN)
- 일반적인 형태의 큐는 선형적인 구조를 갖지만,
우선순위 큐는 이진트리(binary tree) 구조를 사용하는 것이 일반적(아! 이래서 트리를 배웠구나!)
- 포화이진트리 : 리프 노드(젤 말단)를 제외 모든 노드가 두 자식을 가지고 있는 트리
- 완전이진트리 : 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리
- 높이 균형 트리 : 왼쪽 자식과 오른쪽 자식 트리의 높이가 1 이상 차이나지 않는 트리
(왼쪽과 오른쪽이 대칭한 형태)
■ 갑작스러운 힙(Heap)의 특징
- 힙(heap)은 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
- 최대 힙(Max Heap) : 값이 큰 원소부터 추출
- 최소 힙(Min Heap) : 값이 작은 원소부터 추출
- 힙은 원소의 삽입과 삭제를 위해 O(logN) 수행 시간을 요구
- N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하고, 시간복잡도는 O(NlogN)
(NlogN은 일반적인 힙 정렬이나 병합 정렬과 같은 다른 정렬 알고리즘과 동일한 시간을 가진다 함)
따라서 힙의 특징을 다시한번 알기 쉽게 요약하자면 아래와 같다.
- 힙은 완전 이진 트리 자료구조를 따른다.
- 우선순위가 높은 노드가 루트(root)에 위치한다.
(그니까 부모가 무조건 자식보다 크거나 / 작아야 하니(최대힙, 최소힙) 가운데에 젤 크거나 작은 숫자가 온다)
1. 최대힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크며,
- 위에 따라 루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다.
2. 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.
- 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다.
- Heapify(최소 힙 구성 함수)
: 부모로 거슬러 올라가면서, 부모보다 자신이 더 작은 경우 위치를 교체해버린다.
- 예시 : 힙에서 새로운 원소가 삭제 될때는?
가장 마짐가 노드가 루트 노드의 위치에 오도록 값을 바꿔버린 뒤에, Heapify를 진행하면서
값을 계속 바꿔주면서 내려가면 된다.
- 그래서 삽입과 삭제를 할 때 처리해야 하는 범위에 포함된 원소 개수가 절반씩 줄어드니까
시간 복잡도가 logN인 것이다.
■ 파이썬에서의 힙(Heap)라이브러리
- heapq 라이브러리 삽입 및 삭제에 대한 시간 복잡도는 다 로그 엔!
- 단순한 하나의 빈 리스트를 만들면 그걸 힙 자료구조로 사할 수 있다.
heapq 라이브러리 삽입과 추출 위의 이미지에서 보이는 것처럼 heapq를 이용해서 while 문 안에서 하나씩 자꾸 뽑아 내고 있는데,
우리가 배운 것들을 다 자동으로 알아서 해주는 것이 이건가보다.(정렬이다 말 그대로)
CH02-10. 그래프의 표현
일단, 다양한 알고리즘을 작성하려면 그래프를 잘 알고 있어야 하는데, 오늘은 이 그래프에 대해 알아보자.
그래프란?
"사물을 점점(vertex / node), 간선(edge)으로 나타ㅐ기 위한 도구."
자료구조는 다수의 자료(data)를 담기 위한 구조임.
그래프는 두가지 방법으로 구현할 수가 있는데,
1. 인접행렬(adjacency matrix): 2차원 배열을 사용하는 방식
2. 인접리스트(adjacency list): 연결 리스트를 이용하는 방식
인접행렬이란?
무방향 무가중치 그래프. 모든 간선이 방향성을 가지지 않는 무방향 그래프라고 한다.
가중치가 없는 그래프를 무가중치 그래프라고 한다.
무방향 / 비가중치 그래프가 주어졌을 때, 연결되어 있는 상황을 인접행렬로 출력할 수 있다.
n 제곱만큼 공간이 필요하다. v제곱으로 표현 - 방향 가중치 그래프
간선이 방향을 가지는 그래프를 방향 그래프, 그리고 가중치가 있는 그래프를 가중치 그래프라 하는데,
- 방향 가중치 그래프가 주어졌을 때 연결되는 상황을 인접행렬로 출력할 수 있다.
다만, 메모리 소비가 너무 많다...안쓰는데도!!!
인접리스트란?
위처럼 그래프를 리스트로 표현하는데, 메모리 낭비가 적고, 간선의 개수가 작을 때 아아아아주 효율적이라고 한다.
복잡하지만 이해하기 쉽다. - 저 위에 것을 간단히 풀어서 설명하자면
0:[(1, 3), (2,7)] : 0번 노드 에서 기준으로 / 1번 노드까지는 비용이 3 / 2번 노드까지는 비용이 7이 소모된다.
1:[(0, 3)] : 1번 노드에서 기준으로 / 0번 노드까지는 비용이 3이 소요가 된다.
2:[(0, 7)] : 2번 노드에서 기준으로 / 0번 노드까지는 비용이 7이 소요가 된다.
이렇게 해석하면 쉽다.
무방향 비가중치 그래프가 주어졌을 떄 인접리스트로 출력해볼 수 있고,
방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력 할 수 있다!!
■ 그래프의 시간복잡도
요약하면 위와 같다.
자료구조에서는 일반적으로 트리와 그래프까지 공부하는데 이것들이 실질적으로 어떻게 표현되는지 더 공부를 해야 한다고 한다. 안녕
4일차 끝.
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
'패스트캠퍼스 챌린지' 카테고리의 다른 글