2JINISHAPPY 2JINISHAPPY

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

이진트리에는 여러 종류가 있다 트리 중에서도 가장 많이 사용하는 것이 이진트리이지만, 이진 트리들에도 명칭이 존재한다 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를 하나씩 가졌..

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

Quick Sort란, Divide And Conquer 방식을 사용하는 정렬 알고리즘이다 Merge Sort와 함께 많이 쓰이면서, 시간 복잡도가 O(nlog n)으로 실용적이고 빠르다 🤗 1️⃣ Array의 Size가 1이면 해당 Array를 return 2️⃣ Size가 2 이상이면 pivot element를 하나 정한다 3️⃣ A1을 Array에서 pivot보다 작은 element, A2를 Array에서 pivot과 크기가 같은 element, A3를 A에서 pivot보다 큰 element를 담은 Array로 Divide한다 4️⃣ A1, A2, A3를 Quick Sort한 다음 return된 A1, A2, A3 순서대로 이어 붙인다(Conquer and Merge) 위와 같이 Divide 해준 ..