Algorithms & Data Structure

수리과학의 여러 분야에서 함수의 증감 추세를 비교하는 표기법이다. 컴퓨터 과학에서는 일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다.프로그램이 돌아가는 정확한 표기법을 결정하는 작업은 매우 어려우며, 난해하여 직관적이지 않기 때문에 이것을 간략하게 표기하기 위해

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.문제, 즉 알고리즘의 시간 복잡도는 주로 Big-O표기법을 사용하여 나타내며, 이전 포스팅에서 알아봤듯이 이 Big-O표기법은 계수와 낮은 차수의 항을 제외시켜 직관성이 높은(대략적인) 표현방법이다.간략한 예

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리라 한다.서브 트리는 공집합일 수 있다.서브 트리 간의 순서가 존재해 왼쪽 서브 트리와 오른쪽 서브 트리로 구별된다. n개의 노드를 가진 이진트리는 정확히 n-1개의 간선을 가진다.높이가 h인 이진트리의 경우,

서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합.모든 집합들 사이에 공통된 원소가 존재하지 않는다모든 원소들이 자신이 속해있는 유일한 집합만을 가진다.분리집합(Disjoint Set) 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해 있는지, 혹은 속해

최소 신장 트리(MST, Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm) > 가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘 예) 도시가 여러 개 있을 때 각 도시를 도로로 연결하고자 할 때 비용을 최소화하는 방법

문제 전체코드

문제 전체코드

포인터를 사용하는 단순한 자료구조를 통해 동적인 집합을 표현하는 방법에 대한 고찰Stack & Queue, Linked List, Tree단순한 배열을 이용하여 구현해본다.가장 최근에 삽입된 원소가 먼저 삭제되는 구조후입선출(LIFO, last in first out)