set
-
HashSetJAVA/Collection Framework 2020. 10. 8. 17:44
Collections Framework - 배열의 단점을 개선한 클래스로 객체만 저장할 수 있다. - 배열의 단점인 메모리 낭비를 피할수 있는 구조이다. - 동적인 크기 변경이 가능하다. - 자료를 효율적으로 정리하는것을 자료구조(Data structure)라 한다. - 자료구조 방법에는 Set계열, List계열, Map계열이 있다. - java는 java.util 패키지의 자바 컬렉션(JCF)에서 자료구조 방법을 제공한다. Set - 순서가 없고 중복안됨 Set의 종류 - HashSet, TreeSet Set은 순서가 없고, 데이터의 중복이 안되는 것이 특징이다. 프로그램 실행결과 소스 파일 다른 예제 프로그램 실행결과 소스 파일
-
Set - 경로 압축C 자료구조/Set 2020. 7. 2. 23:52
인용 앞에서 만든 집합을 그대로 가지고 와서 구현. 1. 개념 경로압축은 FindSet을 행하는 과정에서 경로의 길이를 줄이는 아이디어를 넣은 것. FindSet을 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾸어준다. 이렇게 함으로써, 트리의 랭크(높이)를 줄일 가능성이 높다. 아래와 같이 임의의 트리가 있다고 가정해보자. [그림 1] 위의 그림에서 FindSet(G)를 하면 아래와 같은 그림이 나오는 것을 의미한다. [그림 2] 위의 그림과 같이, 노드G에서 루트에 이르는 경로 상에 있는 모든 노드들이 직접 루트 노드를 가리키도록 바뀌었다. 이 알고리즘에서는 함수의 리턴값을 이용하여 포인터를 갱신하고 있다. FindSet(x)를 경로압축한 의사..
-
Set - BasicC 자료구조/Set 2020. 6. 29. 19:26
인용 1. 개념 여기서는 각 집합을 하나의 트리로 표현하는 방법을 배울것이다. 흔히 다루는 트리와는 조금 다른 방식의 표현을 쓴다. 트리를 나타낼 때, 보통은 부모 노드가 자식 노드를 가리키도록 하지만 여기서는 자식 노드가 부모 노드를 가리키도록 한다. 아래 [그림 0 ]은 트리를 이용한 집합 표현의 예로, 8개의 원소로 이루어진 집합이 트리로 표현되었다. 임의의 노드에서 부모를 가리키는 포인터를 계속 따라가다 보면 자신이 속한 트리의 루트 노드를 만나게 된다. 이 루트 노드가 집합의 대표 노드이다. 트리를 이용한 처리에서 루트 노드의 부모 노드 포인터는 아래 [그림 0 ]과 같이 자신을 가리킨다. [ 그림 0 ] 트리를 이용한 표현에는 두 집합을 합하는 작업은 연결 리스..