본문 바로가기
반응형

분류 전체보기363

초보 자바 프로그래밍(30) - 개방주소법 (Open Addressing) 🔖 INDEX   개방 주소법(Open Addressing)은 모든 키-값 쌍을 해시 테이블 자체에 직접 저장하는 방법입니다. 충돌이 발생하면, 다른 버킷에 키-값 쌍을 저장하는 방법을 사용합니다. 개방 주소법에는 선형 탐사(linear probing), 이차 탐사(quadratic probing), 더블 해싱(double hashing) 등의 충돌 해결 방식이 있습니다. 개방 주소법의 특징개방 주소법의 장점은 다음과 같습니다:해시 테이블 외부에 추가적인 메모리를 사용하지 않으므로 공간 효율성이 높습니다.캐시 지역성이 좋아서 연속된 메모리 위치에 데이터를 저장할 수 있습니다. ​ 개방 주소법의 단점은 다음과 같습니다:해시 테이블의 로드 팩터가 높아지면 성능 저하가 심해집니다. 일반적으로 로드 팩터가 0.. 2023. 5. 2.
초보 자바 프로그래밍(29) - 개별체이닝 (Separate Chaining) 🔖 INDEX   개별 체이닝은 각 해시 버킷에 연결 리스트(linked list) 또는 트리와 같은 자료 구조를 사용하여 키-값 쌍을 저장하는 방법입니다. 충돌이 발생하면, 해당 버킷에 있는 연결 리스트에 새로운 키-값 쌍을 추가합니다. 개별 체이닝의 특징개별 체이닝의 장점은 다음과 같습니다:해시 테이블의 크기와 상관없이 삽입, 삭제, 검색 연산이 상수 시간에 가능합니다(연결 리스트의 길이가 작은 경우).해시 테이블의 로드 팩터가 높아져도 성능 저하가 덜 합니다. ​ 개별 체이닝의 단점은 다음과 같습니다:연결 리스트를 사용하므로, 메모리 할당 및 해제에 추가적인 오버헤드가 발생합니다.연결 리스트를 사용하기 때문에 캐시 지역성이 떨어져 성능이 저하될 수 있습니다.  개별 체이닝 구현 예제개별 체이닝 방.. 2023. 5. 2.
초보 자바 프로그래밍(28) - 해시검색 (Hash Search) 🔖 INDEX   해시 검색(hash search)은 해시 테이블(hash table)이라는 자료 구조를 사용하여 빠르게 원하는 값을 찾을 수 있는 검색 방법입니다. 해시 테이블은 키(key)와 값(value)을 저장하는 데 사용되며, 해시 함수(hash function)를 사용하여 키를 해시 값으로 변환합니다. 해시 값은 해시 테이블 내의 인덱스로 사용되어 효율적인 검색, 삽입 및 삭제를 가능하게 합니다. 해시 검색의 작동 방식 및 구현 예제해시 검색의 작동 방식은 다음과 같습니다:해시 함수를 사용하여 키를 해시 값으로 변환합니다.해시 값으로 해시 테이블 내의 인덱스를 찾습니다.인덱스에 저장된 값을 검색, 삽입 또는 삭제합니다.자바에서 해시 검색 알고리즘을 구현할 때, HashMap 클래스를 사용할 .. 2023. 5. 2.
초보 자바 프로그래밍(27) - 이진검색 (Binary Search) 🔖 INDEX   이진 검색 (Binary Search)은 정렬된 배열에서 효율적으로 값을 찾는 알고리즘입니다. 이진 검색은 배열의 중간 요소를 확인하여 찾고자 하는 값이 중간 요소보다 큰지 작은지를 판단합니다. 찾고자 하는 값이 중간 요소보다 작으면 중간 요소 왼쪽의 절반을 검색하고, 찾고자 하는 값이 중간 요소보다 크면 중간 요소 오른쪽의 절반을 검색합니다. 이 과정을 반복하면서 원하는 값을 찾습니다. 이진 검색의 작동 방식이진 검색의 작동 방식은 다음과 같습니다:배열의 가운데 요소를 확인합니다.가운데 요소가 원하는 값과 일치하면 해당 요소의 인덱스를 반환합니다.가운데 요소가 원하는 값보다 크면, 배열의 왼쪽 절반(가운데 요소보다 작은 값들)에서 검색을 계속합니다.가운데 요소가 원하는 값보다 작으면.. 2023. 5. 2.
초보 자바 프로그래밍(26) - 선형검색 (Linear Search) 🔖 INDEX   선형 검색은 가장 간단한 검색 알고리즘입니다. 배열의 처음부터 끝까지 순차적으로 원하는 값을 찾을 때까지 각 요소를 검사합니다. 선형 검색은 정렬되지 않은 배열 또는 연결 리스트와 같은 자료 구조에서 사용할 수 있습니다. 선형 검색의 작동 방식선형 검색의 작동 방식은 다음과 같습니다:배열의 첫 번째 요소부터 시작하여 원하는 값과 비교합니다.원하는 값과 일치하는 요소를 찾을 때까지 배열의 요소를 순차적으로 검사합니다.원하는 값과 일치하는 요소를 찾으면 해당 요소의 인덱스를 반환합니다.배열의 마지막 요소까지 검사했음에도 원하는 값과 일치하는 요소를 찾지 못한 경우, 값이 배열에 없다고 판단하여 -1 또는 적절한 오류 코드를 반환합니다. 선형 검색의 특징선형 검색의 장점은 다음과 같습니다:.. 2023. 5. 2.
초보 자바 프로그래밍(25) - 팀정렬 (Tim Sort) 🔖 INDEX   팀 정렬(Tim Sort)은 파이썬에서 기본 정렬 알고리즘으로 사용되는 안정적인 비교 기반 정렬 알고리즘입니다. 팀 정렬은 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 아이디어를 결합한 하이브리드 알고리즘으로, 실제 데이터의 특성을 고려해 높은 성능을 발휘합니다. 팀 정렬의 작동 원리팀 정렬의 작동 원리는 다음과 같습니다: ​배열을 연속된 작은 부분 배열(subarrays)로 분할합니다. 이 부분 배열들은 이미 정렬되어 있거나 거의 정렬된 상태일 수 있습니다. 이러한 부분 배열을 '런(run)'이라고 합니다.삽입 정렬을 사용하여 각 런을 정렬합니다. 작은 크기의 런에서는 삽입 정렬이 상대적으로 빠른 속도를 보입니다.병합 정렬의 병합 과정을 사용하여 인접한.. 2023. 5. 2.
반응형

티스토리툴바