[컴퓨터 과학자 스터디]/자료구조

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다. 1. 그래프의 이해와 종류그래프 이해와 종류연결 관계에 있어 방향성이 없는 그래프를 무방향 그래프라 함.간선에 방향 정보가 포함된 그래프를 방향 그래프라 함.완전 그래프(complete graph): 각각의 정점에서 다른 모든 정점을 연결한 그래프 가중치 그래프(weight graph)와 부분 그래프(Sub graph)가중치는 두 정점 사이의 거리나 소요 시간 같은 정보가 될 수 있음.부분 그래프는 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프를 뜻함.그래프의 집합 표현그래프 G의 정점 집합 → V(G)그래프 G의 간선 집합 → E(G)V(G1) = {A, B, C, D}, E(G1) = {(A,B), (A,C), ..

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다. 1. 빠른 탐색을 보이는 해쉬 테이블테이블(Table) 자료구조의 이해테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보임.저장되는 데이터는 키(key)와 값(value)가 하나의 쌍을 이루며 모든 키는 중복되지 않음테이블은 사전 구조라고도 불리며 맵(map)이라고도 불림.테이블에 의미를 부여하는 해쉬 함수와 충돌 문제배열을 기반으로 한 테이블의 문제점 ex) 직원 테이블직원 고유번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않음직원 고유번호의 범위를 수용할 수 있는 매우 큰 배열이 필요함.해쉬 함수(hash function): 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 함.8자리 고유번호를 2..

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해⚠️ 이진탐색 트리의 문제점과 AVL 트리이진 탐색 트리의 탐색 연산은 O(logn)의 시간 복잡도를 가짐하지만 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보임.이진 탐색 트리의 단점을 해결한 트리를 ‘균형 잡힌 이진 트리’라 하며 그 종류는 대략 이렇다AVL 트리2-3 트리2-3-4 트리Red-Black 트리B 트리⚖️ 자동으로 균형을 잡는 AVL 트리와 균형 인수(Balance Factor)Adelson-Velskii와 Landis에 의해 고안되어 이름도 이들의 이름을 땄음.노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 ..

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.1. 탐색의 이해와 보간 탐색❓ 탐색의 이해데이터를 찾는 방법을 말함.효율적인 탐색은 대부분 트리의 연장성상에서 이루어짐.🚨 보간 탐색(interpolation Search)보간 탐색은 이진 탐색의 비효율성을 개선시킨 알고리즘이다.보간 탐색은 이진 탐색과 마찬가지로 모두 정렬이 완료된 데이터를 대상으로 진행함.“이진 탐색처럼 그냥 중앙에서 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작하자!”비례식을 구성하여 탐색 위치의 인덱스 값을 계산한다.다만 오차율을 최소화하기 위해 실수형 나눗셈을 진행한다.🔑 탐색 키(Search Key)와 탐색 데이터(Search Data)typedef int Key; ..

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다. 1. 단순한 정렬 알고리즘🫧 버블 정렬(Bubble Sort)1. 이해와 구현배열을 오름차순으로 정렬하는 과정버블 정렬은 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식정렬의 우선순위가 가장 낮은 제일 큰 값을 맨 뒤로 보내는 방식앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 이름이 지어짐🧑🏻‍💻 코드void BubbleSort(int arr[], int n){ int i,j; int temp; for(i=0; i arr[j+1]) { // 데이터 교환 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; ..

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다. 1. 우선순위 큐의 이해1.1. 우선순위 큐와 우선순위의 이해우선순위 큐도 enqueue와 dequeue가 일반 큐와 같음하지만 우선순위 큐의 결과는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옴1.2. 우선순위 큐의 구현 방법배열 기반으로 구하는 방법연결 리스트를 기반으로 구현하는 방법힙(heap)을 이용하는 방법배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킴데이터 반환 및 소멸은 쉽지만 데이터를 삽입 및 삭제하는 과정에서 데이터를 계속 한 칸씩 뒤로 밀거나 당기는 연산을 수반해야 하는 문제가 생김삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야 할 ..