2JINISHAPPY 2JINISHAPPY

트리란 그래프 이론 상 Connected+Acyclic의 성질을 가지고 있는 그래프의 한 형태이다. 위와 같은 트리에서 edge(5,6)이 제거되면 모든 Vertex가 연결되어 있어야 한다는 Connected 성질을 만족하지 못한다. 또한 edge(4,6)이 추가된다면, 4-5-6 사이에 Cycle이 생겨 Acyclic 성질을 만족하지 못한다. 자료구조에서 구현하는 트리는 보통 Rooted Tree를 의미한다. Rooted Tree의 Non-Recursive한 정의 데이터를 지닌 노드와, 노드들을 연결해주는 Directed Edge의 집합으로 이루어진다. Edge의 방향은 Parent Node에서 Child Node로 향한다. Tree 상의 노드 중 In-degree가 0인 Node를 Root Node라..

List(순서가 있는 데이터 set)을 구현하기 위한 방법으로는 Array와 Linked List가 있다. 두 자료구조에는 결정적인 차이가 있는데, Size의 고정 여부와 메모리가 연속적으로 할당되어 있는지의 여부가 다르다. Array는 선언 시 Size가 고정되어 있으며, 연속적인 메모리 공간에 배열이 할당되게 된다. 따라서 Array의 각 element를 접근하기 위해서는 0번째 index의 주소값만 알면 되므로 Linked List에 비해 월등히 빠른 접근 시간을 가진다. Linked List는 insert, delete연산을 수행할 때 마다 size가 변화하며, 각각의 element들은 독립적인 메모리 공간에 할당되기 때문에 element 자체에서 다음(+이전) element의 주소값을 가지고 있..

PS를 하면 종종 Circular Array의 필요성을 느낄 때가 있다아래의 문제들은 내가 circular 배열을 이용해서 푼 문제들의 목록이다더보기문제www.acmicpc.net/problem/2005520055번: 컨베이어 벨트 위의 로봇길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부www.acmicpc.netwww.acmicpc.net/problem/1489114891번: 톱니바퀴총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데..

이진트리에는 여러 종류가 있다 트리 중에서도 가장 많이 사용하는 것이 이진트리이지만, 이진 트리들에도 명칭이 존재한다 Binary Tree의 종류에는 1️⃣Full Binary Tree 2️⃣Perfect Binary Tree 3️⃣Complete Binary Tree 가 있다 세 가지 트리를 한글로 번역하면... 그렇다 트리들의 이름만으로는 분간이 안 간다 그럼 세 가지 트리는 어떤 특징을 가지고 있고, 어떻게 다를까? 1️⃣ Full Binary Tree full binary tree는 모든 node의 child가 2개 or 0개인 트리를 말한다. 즉, leaf node가 아닌 node는 child를 두 개 가져야만 한다는 뜻이다 😄 그림의 오른쪽 트리에서, '2'와 '4'는 child를 하나씩 가졌..

스택 실생활에서도 정말많이 사용하는 자료구조이다 물론 Computer Science에서도 정말정말정말 중요하고 몰라서는 안될 자료구조이기도 하다 인터넷 방문 기록(뒤로가기)의 구현에도, 함수의 재귀 호출에도 스택이 사용된다 하지만 스택에 대해서 음 후입선출~ 정도까지만 간략히 알고있는 경우가 많다 또 스택이면 스택이지 ADT 스택은 뭘까? 우선 스택에 대해 간략하게 알아보자면 스택에는 데이터들이 저장되어 있다. 가장 위(마지막)에 저장한 데이터의 위치를 스택의 탑이라고 한다. 데이터의 추가/삭제는 오직 스택의 탑 위치에서만 가능하다. ADT Stack은 어떠한 자료의 형태에 'Stack'이라고 명명할 수 있게 하는 자료의 형태와 연산을 정의한 것을 말한다. 즉, 이것을 만족하지 않는 자료는 스택이라고 할..

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다. 연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다. 그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다. 그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때, 아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다. 1️⃣ G'은 Connected하다. 2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다. 해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때..

Heap은 자료구조의 한 종류로써, 특정 property를 만족하는 Complete Binary Tree를 말한다 Heap의 어떤 node p에 대해, p의 parent node를 q라 하면 q의 value는 p의 value보다 작다 ❗❗ 이런 property를 만족하는 힙은 Min-Heap이라고 하며, 반대(q.value>p.value)의 경우에는 Max-Heap이라고 한다 Heap은 보통 Priority Queue 혹은 Heap Sort를 구현하는데에 사용된다 그리고 Complete Binary Tree의 한 종류이기 때문에, Linked List보다는 Array로 구현하는 것이 효율적이다 😉 (중간에 낭비되는 공간이 없기 때문) 이 때, Heap의 대표적인 연산은 min(max)반환/insert/d..

BST는 (sorted array라는 가정하에) 시간복잡도가 O(log n)이 걸리는 Binary Search를 활용한 트리 형태이다 하지만 그러한 Binary Search를 굳이 배열이 아닌 트리를 이용해서 구현하는 이유는? - 다른 element에 비해 특정 element에 대한 검색을 많이 할 경우 ➡ 해당 element를 root에 가깝게 위치시키면 시간을 절약할 수 있음(ADT BST) - Array에 element를 삽입 혹은 삭제하는 경우 ➡ 최악의 경우 O(n)시간이 소모된다 이러한 이유로 ㅇㅣ진 탐색트리를 이용한다 다시 정확하게 정의하자면, Binary Search Tree: 자식이 최대 2명이고, Binary Search를 가이드하는 형태를 띤 트리 BST의 가장 큰 특징은 key값 k..