본문 바로가기

computer science/자료구조6

[자료구조] 그래프(Graph) 이번시간에는 그래프에 대해 공부해 보겠습니다. 그래프란 ? 그래프는 정점(Vertex)간의 관계를 표현하는 자료구조 입니다. 그래프 G = (V,E)로 정의하는데, V(Vertex)는 그래프에 있는 정점들의 집합을 의미하고 E(Edge)는 정점을 연결하는 간선들의 집합을 의미합니다. 사실 일상생활에서 그래프의 개념은 많이 사용되고 있습니다. 그 중에 가장 대표적인 것이 지하철노선도 인데요, 각 지하철역과 그 들을 연결하는 호선간의 관계를 그래프로 표현할 수 있습니다. 그래프와 트리의 차이 그래프의 종류 무방향 그래프(Undirected Graph) 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 v1와 v2를 연결하는 간선을 [v1, v2]라고 하면, 이때 [v1, v2]와 [v.. 2019. 7. 17.
[자료구조] 힙(Heap) 이번시간에는 힙에 대해서 공부해보겠습니다. 힙은 최댓값과 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(마지막 레벨-1은 모두 채워져 있고, 마지막 레벨은 노드가 왼쪽부터 구조를 기본으로 한 자료구조) 입니다. 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지니고 있습니다. 힙에서 부모의 값은 항상 자식(들)의 값보다 크거나(Max Heap, 최대힙), 작아야(Min Heap, 최소힙)하는 규칙이 있습니다. 따라서 루트 노드에는 항상 데이터들 중 가장 큰 값, 혹은 가장 작은 값이 저장되어 있기 때문에 최대값,최솟값을 O(1)만에 찾을 수 있습니다. 단순히 최대값,최솟값을 O(1)안에 찾기 위해서라면 "항상 완전 이진 트리의 형태여야 한다"는 조건을 만족시킬 필요.. 2019. 7. 11.
[자료구조] 트리(Tree) 이번시간에는 트리에 대해 공부해보겠습니다. 앞서 올린 포스팅 스택, 큐, 배열은 모두 선형구조입니다. 자료들이 모두 선의 형태로 나열되어 있죠. 하지만 트리의 경우는 비선형 자료구조인데, 그 중에서도 자료들 간에 계층관계를 가진 계층형 자료구조라고 부릅니다. 루트(root) : 부모가 없는 노드, 그림에서는 A노드 입니다. 간선(edge) : 노드를 연결하는 선 노드의 차수 : 한 노드가 가지는 서브 트리의 수, 즉 자식 노드의 수. A의 차수는 3, B의 차수는 2 트리의 차수 : 트리에 속한 노드의 최대 차수 레벨 : 트리의 각 층에 매겨진 번호, 처음부터 0,1,2,3...레벨 높이 : 트리의 속한 노드들의 레벨 포레스트 : 트리의 집합. [F,K,L], [G,L], [B,E,F,J,K].....등.. 2019. 7. 2.
[자료구조] 큐(Queue) 이번시간에는 Queue에 대해서 공부해보겠습니다. Queue의 개념은 일상생활에서도 많이 사용됩니다. 예를들어, 은행에서 창구수에 비해 오는 고객들이 많으니, 이들 고객에는 순서가 필요합니다. 그래서 나온 것이, 대기순번이죠. 내가 일찍왔으면 내가 먼저 상담을 받고, 늦게 오면 늦게 온 대로 상담을 받습니다. 만약 내가 늦게 왔는데 일찍하려고 하면 싸움이 나기 시작하죠. 바로 이 개념이 Queue입니다. 앞서 배운 스택은 "LIFO", 먼저 들어간 놈이 늦게 나오는 구조입니다. 저희가 은행에 먼저 갔는데, 저희 순서가 가장 마지막번쨰라뇨? 저희의 직관과는 잘 맞지 않습니다. 반면에 Queue는 먼저 온 놈이 먼저 나갑니다. FIFO(First In First Out)이죠. 게임을 좋아하시는 분이라면, 사.. 2019. 6. 20.

티스토리툴바