IT/알고리즘 공부( Coursera )
-
5week] Balanced Search TreesIT/알고리즘 공부( Coursera ) 2021. 4. 2. 00:05
2-3 Search Trees 균형 탐색트리로 자식노드를 2, 3개를 가지고 있는 형태를 가진다. 2-node : 1개의 key, 2개의 자식노드 3-node : 2개의 key, 3개의 자식노드 예제에서 보듯 기본 BST와 같이 정렬되어 트리를 구성한다. 특징 : root→leaf(null link)까지의 거리가 모두 같아 완벽한 균형을 이룬다. Search 2-node key보다 작으면 → left 자식 key보다 크면 → right 자식 3-node 두 key보다 작으면 → left 자식 두 key의 사이면 → middle 자식 두 key보다 크면 → right 자식 Insert 삽입할 target node가 2-node일 때 3-node로 교체 삽입할 target node가 3-node일 때 임의의..
-
1 Week ] Union findIT/알고리즘 공부( Coursera ) 2021. 1. 28. 21:28
코세라 수업을 듣고 내가 정리한 내용이다. Union find 알고리즘에 대해서 공부한 내용이다. 목차는 아래와 같이 5개이다. 1. dynamic connectivity 2. quick find 3. quick union 4. improvements #5. applications # Union find 를 활용한 사례 1. dynamic connectivity 먼저 주어지는 N은 노드의 개수로 총 노드의 개수가 주어지고 이 노드들의 연결 정보가 입력값으로 주어진다. 이를 연결해주는 Union이라는 함수와 연결이 되어있는지 검사하는 find,connected 라는 함수를 만들어준다. 대략적인 클래스 모양은 아래와 같다. public class UF // Union Find UF( int n ) // n개..