Part 2. 알고리즘 - 7장 정렬 알고리즘

알고리즘이 중복 데이터를 빠르게 식별하거나 필요한 데이터를 빠르게 찾기 위해서 데이터를 정렬 한다. 책에서 내용은 유형 별로 나와있어서 시간복잡도를 따로 표로 첨부해왔다. 참고하고 외우도록. 기수 정렬 O(dn) 에서 d 는 정렬하고자 하는 요소의 자리수를 의미한다. 삽입정렬 선택 정렬 버블 정렬 힙 정렬 : 힙 데이터 구조와 각 노드를 최대 힙 또는 최소 힙 상태로 정렬 하는 방법을 뜻함. 병합정렬 : 데이터를 반으로 나누어 정렬을 수행, 분할 정복이라고도 함 퀵 정렬 : 피벗과, 왼쪽, 오른쪽 마커로 정렬 셀 정렬 :요소를 묶는 단위를 줄여가며 삽입 정렬을 실행 버킷 정렬 : 특정한 기준의 버킷별로 정렬 기수 정렬 : 기수별로 나눔

2022.10.30

Part 1. 데이터 구조 - 4장 해시 데이터 구조

4장에서 다루는 것은 해시 함수를 사용하여 사용하는 동작하는 해시 테이블 이다. 특히 컴퓨터 보안의 암호화와 체크섬은 해싱에 크게 의존한다. 해시는 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것이다. 해시 함수는 이 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 상자를 뜻한다. 해시 함수 특징 : 입력되는 데이터가 무엇이든지 출력되는 해시의 값의 길이가 항상 고정되어 있다. 일반 함수는 정의역 요소 하나에 정확히 하나의 치역 요소가 대응 되지만 해시함수는 서로다른 입력 2개가 같은 해시값을 생성할 가능성 ( 해시 충돌 ) 이 있다. 다만 흔치않은 일이다. 해싱 ( 해시 테이블을 이용하는 탐색) 할대 사용하며, 이때 해시 함수는 해시 테이블 데이터 구조에서 중요한 부..

2022.10.30

Part 1. 데이터 구조 - 3장 트리 데이터 구조

트리 데이터 구조 뒤집혀 있는 나무 처럼 보인다. 키-값 유형의 구조 트리를 탐색하는 과정을 순회 (traversal) 라고 한다. 이진 트리 : 가장 많이 사용 되는 데이터 구조. 각 부모 노드가 항상 2개의 자식 노드와 연결 되어 있다. 이진 트리의 가장 일반적인 유형은 이진탐색트리이다. 이진 탐색 트리에서 모든 노드의 키는 왼쪽 서브 트리보다 크고 오른쪽 서브 트리보다 작다. 트리에 노드 추가, 트리에서 노드 삭제, 노드를 선택해 탐색하고자 하는 키가 존재하는지 확인 가능 Adelson-Velsky and Landis 불균형 이진트리, 단 하나의 자식 노드를 갖는 구조. 트리의 균형을 조정하는 과정은 트리의 역할을 유지하되 가능한 한 최소 높이(자식 노드의 계층이 최소) 로 만드는 것이다. 서브 트..

2022.10.30