최소 비용 신장 트리(MST) 최소비용신장트리란 아래의 사진에서 각 노드들이 최소의 비용으로 모든 노드들이 연결되어야 하는 경우를 말한다. 자세히 보면 무방향 가중치 그래프이다. 각 노드사이에 방향성은 없고 노드 사이에 가중치가 존재하는 형태이다. 아래와 같은 사진을 보면 굵을 곡선으로 이루어진 트리가 최소비용신장트리이다. 하지만 사진을 자세히 보면 알 수 있듯이 최소비용신장트리는 유일하지 않다. 만약 b와 c의 연결고리 대신 a와 h를 선택해도 같은 가중치에 모든 노드들이 연결되었을 것이다. 위의 내용들을 정리해보자면 무방향 가중치 그래프이다. 각 에지에 대한 가중치는 w(u, v)와 같이 표현가능하다. 조건 - T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다. - 가중치의 합이 최소가된..

Hashing의 권오흠 교수님의 수업을 들으며 교수님께서 말하긴 이 친구는 너네 식으로 말하면 치트키다라는 말씀이 인상깊었다. 그럼 왜 그런말을 했는지 알아보자!! Binary Search Tree는 Hashing과 비슷한 Dynamic Set이다. Dynamic Set은 동적으로 데이터가 저장되고 삭제되고 검색하는 것을 뜻한다. Binary Search Tree는 높이에 비례하기 때문에 insert, search, delete는 O(n)이고 red black은 O(logn)입니다. 그렇지만 Hashing은 O(1)의 시간이 소요된다. 혹은 최악으로 O(n)이 소요된다. 왜 이렇게 되는지 알아보자!! 기본적으로 key와 value의 조합으로 이루어 져있으며 (key, "hoony) 이러한 형태로 이루어 ..

이진 탐색 트리 1. 이진트리의 조건을 유지하면서 2. 자기 부모나 루트보다 작거나 같은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보내버리는 이진트리를 의미한다. 3. 이에 대응하는 서브트리들도 이 조건들을 모두 만족해야한다. 그림으로 만들어보면 아래와 같이 볼 수 있을 것이다. 특정한 값을 검색하고 찾는데 더 효율적일 것이다. 입력, 탐색, 삭제 모두 높이에 비래해서 시간복잡도가 걸린다. O(n)이다. 입력은 특정한 값이 들어오면 루트나 부모와 비교하여 왼쪽 혹은 오른쪽으로 이동하게 만들어준다. 계속 자기의 자리를 찾아가다 자리를 완전히 찾게되면 node를 반환해준다. 트리는 누가봐도 재귀를 사용하시요 같은 구조이다. 그래서 값을 비교하여 재귀를 통해 값을 넣어줄 수 있다. Node* addNode(Nod..

특징 1. 트리는 하나의 루트 노드를 갖고있다. 2. 루트 노드는 2개 이하의 자식노드를 갖고 있다. 3. 그자식 또한 2개 이하의 자식노드를 갖고있고 이는 반복적으로 정의 된다. 노드들과 다른 노드들을 연결하는 간선으로 구성되어있다. 일반적으로 아래와 같은 모습으로 이루어져있다. 자식은 2개가 있어도 되고 없어도 되고 한개만 있어도 된다. 모든 노드들에 상응한다. 방법은 일반적으로 배열과 연결리스트 와 같은 방식으로 구성된다. 배열은 크기가 제한적이고 빈칸이 생길 수 있다. 그렇지만 쉽고 간단하게 표현할 수 있다. 용어 정리 Root: 제일 상위 노드 부모-자식 관계: 노드의 상위 노드가 부모이고 그 밑의 노드를 자식이라고 한다. 형제: 부모가 동일한 노드들을 형제라고 부른다. leaf: 자식이 없는 ..

에스토라네스의 체 에스토라네스의 체는 소수의 배수들을 모두 지움으로써 소수를 구할 수 있는 알고리즘이다. 그렇게 어렵지 않으니 코드로 설명하겠습니다. 백준 1929번을 통해 코드를 만들어 보겠다. 코드를 보면 2부터 입력값의 제곱근 까지 나누어서 나머지가 0이되면 소수가 아니게 된다. 만약에 2를 넣었는데 2의 제곱근은 1.414정도 임으로 반복문이 돌지 않고 소수로 판단하여 출력하게 됩니다. 그리고 만약에 9가 들어가게 된다면 9의 제곱근은 3이기 때문에 3으로 나누어져 나머지가 0임으로 결국 소수가 아니라고 판단하게 됩니다.