union-find란? - 서로소로 이루어진 부분 집합들의 상관관계를 이용하여 효율적인 상관관계(각 집합 별 루트 노드를 갖도록)를 이루도록 하는 알고리즘 - union 연산 : 연결된 노드를 확인해 하나의 집합(트리)로 합치는 연산 - find 연산 : 각 집합이 어떤 값과 연관되어 있는지 찾는 연산(루트 노드를 찾아주는 연산) - find 연산을 집합의 정의로 해석하면 어떤 집합에 속해있는지 찾아주는 연산이라 정의 가능 추상적 구현 - union 함수는 두 원소를 값으로 갖는다. 인수로 받은 원소들을 find 함수를 이용해 루트 노드의 값을 얻고, 크기 비교를 통해 값을 갱신. (ex - [1, 4]의 값을 입력받았는데 4의 루트 노드가 2라면, 1과 2를 연결해주기 위해 tree[2] = 1 연산)..
힙 정렬이란? - 루트 노드에 최대/최소 값만 위치할 수 있는 힙의 특성을 이용해서 인덱스를 제한해나가면서 정렬. 추상적 구현 - 리프 노드가 아닌 노드들부터 heapify()를 이용해 느슨한 정렬 유지. - 마지막 인덱스 ~ 루트 노드 직전 인덱스까지 최대/최소 값인 루트 노드 값과 끝 값 위치 교환하며 heapify() 반복. # PYTHON CODE n = int(input('정렬할 리스트 원소의 수를 입력하시오: ')) seq = [] for _ in range(n): a = int(input('리스트의 원소를 입력하시오: ')) if a == - 1: break seq.append(a) def heap_sort(seq): for i in range(n // 2 - 1, -1, -1): # 리프 ..
힙이란? - 완전 이진트리의 한 종류이며, 느슨한 정렬을 이루고 있는 자료구조. - 느슨한 정렬이란 리프 노드들 간에는 큰 특징이 없으며 루트 - 서브 간의 위계만 존재한 정렬을 의미함. - 최대/최소 힙 두 형태가 있으며 느슨한 정렬을 이루고 있기 때문에 순회나 특정 원소가 필요한 연산은 적절치 않음. - 우선순위 큐/힙정렬 등의 알고리즘에 주로 사용됨. 추상적 구현 - 힙 클래스 생성 후 값 추가, 삭제의 기능을 갖는 함수 부여. - 값 추가하는 함수 : 트리의 맨 끝에 값 append, 마지막 인덱스 // 2 값이 0보다 클 동안 값 비교. - 값 제거하는 함수 : 특정 값은 제거 불가능, 루트 노드 값을 제거, 맨 끝 값을 루트 노드로 올려준 뒤, heapify()를 통해 정리. - heapify..
