본문 바로가기

Data structure8

[자료구조] 인덱스와 파일구조 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 인덱스데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다. 인덱스를 관리하기 위한 추가 작업과 저장공간이 필요하기 때문에 잘못 사용할 경우 성능저하가 발생할 수 있다. 데이터베이스는 말그대로 데이터가 저장되어있는 집합체이다. 어떤 단체나 회사냐에 따라 데이터베이스의 내용물은 다르다.유저가 Query(질의)를 전달하면 DataBase에서 해당하는 데이터를 찾아서 유저에게 전달해주는데이 때 인덱스가 데이터마다 고유의 주소값(pointer)를 저장하고 기억해 데이터를 찾기 더 수월하게 만들어준다. 인덱스를 구성하기 위한 자료구조로는 B-Tree, B+Tree, Hash Table 가 있다. (1) .. 2025. 6. 16.
[자료구조] 해싱 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 해싱 (Hashing) 이란?각각의 데이터를 고유한 숫자 값으로 표현하고, 이를 통하여 기억저장소에 저장하거나 검색 작업을 수행하는 방식을 말한다. Hash Function을 통하여 Hash Table에 인덱스를 계산한다.다른 방식에 비해 검색속도가 가장 빠르다.삽입, 삭제의 빈도가 많을 때 유리하다. Key-Value 변환 방법 사용 : Hash Table은 (Key,Value) 구조로 데이터를 저장함 데이터 검색과 저장 뿐만 아니라 데이터 무결성 검사, 암호화에도 활용된다. 데이터 무결성 검사 : 데이터가 손상되거나 변경되지 않았는지 확인하는 과정이다 해시 함수(Hash Function) : 임의의 길이를 가진.. 2025. 6. 13.
[자료구조] 탐색 (Search) 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 탐색이란?기억공간에 저장된 특정 데이터를 착아내는 작업을 말한다.순차 탐색 : 순서화 되어 있지 않은 데이터를 첫 번째부터 차례대로 탐색하는 방식제어 탐색 : 반드시 순서화 되어있는 데이터를 탐색하는 방식 비유하자면 어지럽혀진 창고에서 물건을 찾는 것이 순차 탐색, 정돈된 도서관에서 책을 찾는 것이 제어 탐색이라 볼 수 있다.제어탐색 즉 앞서 배웠던 정렬을 토대로 한 번 순서화된 데이터에서 탐색하는 방식을 제어 탐색이라한다.제어 탐색 방식은 아무리 빨라도 시간 복잡도가 O(logN)이라는 특징을 가진다. 이진 탐색 (Binary Search)피보나치 탐색 (Fibonacci Search)보간 탐색 (Interp.. 2025. 6. 9.
[자료구조] 정렬 (sorting) - 퀵, 힙, 병합, 기수 정렬 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 복습 앞서 학습했던 Big-O 표기법을 숙지해가며 공부하자. 스택(LIFO) : 가장 나중에 들어온 데이터가 먼저 삭제 큐(FIFO) : 가장 먼저 들어온 데이터가 먼저 삭제 퀵 정렬 (Quick Sort)데이터들을 피벗(키)으로 부분적으로 나누어 가며 정렬하는 방법앞서 살펴본 정렬들과 달리 평균 시간복잡도는 O(n log n)이다. 최악 시간복잡도는 여전히 O(n^2) Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할프로그램을 Recall해야하므로 Stack 요구분할(Divide)와 정복(Conquer)을 활용 ex) 초기값 : 15 30 60 5 35 18예시에서는 가장 오른쪽 수인 18.. 2025. 6. 9.
[자료구조] 정렬 (sorting) - 버블 ,선택, 삽입, 쉘 알고리즘 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 정렬의 개념각 데이터를 특정 항목으로 오름차순 혹은 내림차순으로 재배열하는 작업을 말한다.정렬의 종류내부 정렬 : 삽입법, 교환법, 선택법, 병합법, 분배법 등 데이터량이 적을 때 RAM과 같은 주기억장치에 정렬하는 방법을 말한다.RAM은 속도가 빠른 대신에 용량이 작다. 외부 정렬 : 밸런스 병합 정렬, 캐스케이드 병합 정렬, 폴리파즈 병합 정렬, 오실레이팅 병합 정렬 대용량의 데이터를 HDD, SSD와 같은 보조기억장치에서 기억시켜서 정렬하는 방법을 말한다.내부정렬과는 반대로 속도가 느린 대신 용량이 크다. 컴퓨팅에서는 주기억장치가 내부 정렬 : 버블 정렬두 개의 데이터를 비교하여 크기에 따라 위치를 서로 .. 2025. 6. 5.
[자료구조] 비선형 자료구조 : 트리, 그래프 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 선형구조가 주로 자료에서 input-output하는 것에 초첨이 맞춰져있다면 비선형 자료구조 자료 뒤에 여러 자료가 존재하는 형태를 보인다. 비선형 자료구조 : 트리 트리의 개념 노드들이 나뭇가지처럼 연결된 계층적인 자료구조를 가리키며 주로 조직 구조도, 연산 수식을 표현하는데 적합하다.노드 : 자료 항목을 가지는 트리를 구성하는 기본 요소 루트 노드 : 트리의 가장 맨 상단에 있는 노드차수(Degree) : 각 노드에서 뻗어나온 가지 수 리프 노드 : 자식이 하나도 없는, 차수가 0인 노드. 보통 마지막 노드가 이에 해당한다. 트리 뎁스 : 트리의 최대 깊이 트리 데그리 : 노드 차수 중 최대 차수 이진 트리 .. 2025. 6. 4.
[자료구조] 선형 자료구조 : List, Stack, Queue, DeQue 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 선형구조 : List1. 선형 리스트(Linear List)연속되는 기억장치에 저장되느 자료구조로, 대표적으로 배열(array)이 있다. 원하는 정보가 있으면 해당하는 Index에 바로 찾아가면 되므로 접근속도가 빠르다는게 특징이다.단, 데이터 삽입-삭제시 데이터를 이동해주어야하므로 번거롭다. 2. 연결 리스트(Linked List)자료를 임의의 공간에 기억시키고, 순서에 따라 포인터로 연결시킨 자료구조이다.기억공간이 연속적이지 않고, 포인터를 통해 사슬처럼 앞뒤가 연결되어있는 것이 특징이다. 따라서 배열과 같은 선형 리스트와 비교했을 때 데이터(원소)의 삽입과 제거가 용이하지만 접근 속도가 느리다는 단점도 존.. 2025. 5. 9.
[자료구조] 시간복잡도와 Big-O 표기 공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 좋은 알고리즘을 평가하는 척도 : 시간복잡도와 공간복잡도 기본적으로 시간복잡도, 즉 속도가 얼마나 빠르냐에 따라서 좋은 알고리즘을 평가하게 된다.그리고 시간복잡도를 측정하기 위해서 데이터에서 연산 횟수가 얼마나 되는지를 연산해야하는데이를 알아보는 지표 빅오, 빅오메가, 빅세타 표기법이라고 한다. 각자 최악-최선-평균을 구하는 표기법이다. 빅오(Big-O) 표기법시간복잡도를 통한 성능을 측정하기 위해서 보통 빅오(Big-O)를 지표로 삼게되는데,최악인 상황에서 잘 작동한다는건 결국 어떤 상황에서도 수행이 보장됨을 의미하기 때문이다. 빅 오 표기법은 ‘n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는가’ 를 잘.. 2025. 5. 9.

티스토리툴바