목록분류 전체보기 (327)

오늘도 더 나은 코드를 작성하였습니까?

서로소 집합 DSU(Disjoint set - Union) / 합집합 찾기 (Union-Find) kotlin

Disjoint Set(서로소 집합) - 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합 DSU(Disjoint Set Union) - 데이터 구조는 여러개의 서로소 집합(겹치지 않도록) 원소(데이터)를 저장하는 자료구조이다. - union–find 또는 merge-find 라고도 부른다. - 두 서로소 집합을 합쳐 하나의 집합으로 만들 수 있다(union) - 2개의 서로 다른 원소가 같은 집합인지 "대표원소를 통해" 확인할 수 있다(find) 구현 예) 총 원소가 0번 원소부터 7번까지 8개의 원소가 있다고 가정하고, 처음에는 자기 자신만을 포함하는 총 8 개의 집합이 있다고 가정해 보자. 배열로 Index는 해당 원소, value는 속한 집합의 "대표원소" 이다. * 대표원소를 결정하는 방..
Algorithm/개념 2023. 11. 15. 19:47
Hash Collision(해시 충돌) Chaining(체이닝) 및 kotlin 구현

해시 충돌 hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황 Chainning (체이닝) hashTable의 각 슬롯이 연결 리스트의 형태로 데이터를 저장하여, 동일한 출력을 값을 가지는 데이터가 들어 오더라도 같은 hash table의Idx에 저장하여 충돌을 해결한다. 새로운 데이터를 넣을때는 각 해당 슬롯의 가장 앞에 삽입한다. 그러면 항상 O(1)의 시간이 걸린다. 하지만, 검색 및 삭제는 해당 슬롯의 충돌되어 삽입된 갯수에 따라 성능이 좌우된다. 이때, hashFunction을 C-Universal Function을 사용하면, 각 슬롯의 평균적인 연결리스트의 길이는 O(1)이라 이미 증명되어 있다. class ChainingHashTable(private va..
자료구조 2023. 11. 14. 22:29
HashTable Open Addressing(Linear Probing) kotlin 구현

class OpenHashTable(private var initTableSize: Int = DEFAULT_TABLE_SIZE) { companion object { private const val DEFAULT_TABLE_SIZE = 20 private const val FULL = -1 } private enum class State { OCCUPIED, EMPTY } private data class Slot(var state: State, var key: K? = null, var value: V? = null) { var hashCode = key.hashCode() } var size: Int = 0 private var table: Array = Array(initTableSize) { S..
자료구조 2023. 11. 10. 03:19
Hash Collision(해시 충돌) Open Addressing(개방 주소법)

해시 충돌 hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황 Open Addressing(개방 주소법) 해시 충돌이 발생하면 테이블 내의 사용되지 않는 곳을 탐사(Probe) 한 후, 비어있는 곳에 충돌된 데이터를 저장하는 방식 - Linear Probing (선형조사) 비어있는 곳을 선택할 때, 바로 다음 빈 공간으로 한다. 1. 함수의 결과에 따른 index의 슬롯이 비어 있으면 데이터를 저장한다. 2. 비어 있지 않다면, 이전에 저장된 데이터의 key 비교한다. 3. key 값이 같다면, 값을 업데이트한다. 다르면 바로 다음 index를 확인합니다. 3. 빈 슬롯을 찾을때까지 1칸씩 이동하여, 빈 슬롯을 찾으면 데이터를 저장합니다. *저장을 하는 배열은 원형이라..
자료구조 2023. 11. 9. 18:47
이전 Prev 1 ··· 7 8 9 10 11 12 13 ··· 82 Next 다음