혼자 공부하면서 노션에 적어둔 내용을 기록할겸 붙여넣기 했습니다 (정리 안 됨 말 그대로 낙서)
우선순위 큐와 힙의 개념
- Priority queue (우선순위 큐)
- 큐와 유사하지만 우선 순위가 높은 아이템이 먼저 처리됨
- insert
- delete
- peek
- heap
- 힙은 주로 이진 트리 기반으로 구현
- 힙은 max heap 과 min heap 이 있음
- max heap
- 부모 노드의 키가 자식노드들의 키보다 크거나 같은 트리
- min heap
- 부모 노드의 키가 자식노드들의 키보다 작거나 같은 트리
- 힙 주요동작
- inser
- delete
- peek
- 우선순위 큐와 힙의 관계
- 힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐 구현체가 된다
- 우선순위 큐와 힙의 사용 사례
- 프로세스 스케줄링
- 힙 정렬
- 힙 메모리와는 관련 없음
배열(array), 동적배열(dynamic array)과 연관배열(associative array)
- Array
- 같은 타입의 데이터들을 저장하는 자료구조
- 연속된 메모리 공간에 데이터들을 저장
- 데이터들 각각은 이름이 없지만 인덱스로 접근가능
- 연속된 메모리 공간에 데이터들을 저장하기 때문에 CPU 캐시를 통해 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있다.
- 동적 배열 (dynamic array)
- 크기가 변할 수 있는 Array
- 데이터를 더하거나 빼는 것이 가능한 자료구조
- resizable array, array list 등등으로 불림
- 연관 배열 (associative array)
- key-value pair 들을 저장하는 ADT
- 같은 키를 가지는 페어는 최대 한개만 존재
- map, dictionaray 라고 불리기도 함
리스트(list), array list 와 linked list 의 개념과 차이
- 리스트
- 값들을 저장하는 추상자료형 (ADT)
- 순서가 있음
- 중복을 허용
- 리스트 구현체
- Array list
- Linked list
- Array List
- 배열을 사용하여 리스트를 구현
- Linked list
- 노드를 연결 시키는 형태로 구현
- 확장팩(?)
- circular linked list - 순환 ( 꼬리와 헤드가 연결)
- doubly linked list - 양방향 : 더 빨리 접근 할 수 잇다
- circular doubly linke list - 순환 양방향
맵(Map) 과 해시테이블 (hash table)
- Map
- key-value pair 들을 저장하는 ADT
- 같은 키를 가지는 페어는 최대 한개만 존재
- associative array, dictionary 라고 불리기도 함
- Map 구현체 → Hash table
- Hash table (hash map)
- 배열과 해시함수를 사용하여 map 을 구현한 자료구조
- (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠름
- hash function
- 임의의 크기를 가지는 타입의 데이터를 고정된 크기를 가지는 타입의 데이터로 변환하는 함수
- 해시 테이블에서 임의의 데이터를 정수로 변환하는 함수
- hash collision (해시 충돌)
- 키는 다른데 해시가 같을 때
- 키도 해시도 다른데 hash % map_capa 결과가 같을 때
- hash collision 해결 방법
- open addressing
- linear probing
- 비어있는 공간 활용
- linear probing
- separate chaining
- 버킷을 linked list로 관리
- open addressing
- hash table resizing
- 데이터가 많이 차게 되면 테이블의 크기를 늘려주어야한다
Set , Hash Set, List vs Set
- Set
- 데이터를 저장하는 추상 자료형 (ADT)
- 순서를 보장하지 않음
- 데이터 중복을 허용하지 않음
- 데이터 조회가 리스트보다 빠름
- 언제 쓰면 좋을까?
- 중복된 데이터를 제거해야 할 때
- 데이터의 존재 여부를 확인해야 할 때
- set 구현체
- hash set
- linked hash set
- tree set
- Hash set
- 해시 테이블을 사용하여 구현
- Hash table
- 일반적으로 테이블의 크기에 상관없이 키를 통해 상수 시간에 빠르게 데이터에 접근 가능
- 해시테이블을 사용하여 구현하기 때문에 크기 상관없이 데이터 조회가 빠름
- 리스트와 셋 중 무엇을 쓸까?
- Set 을 사용하는게 더 적절한 상황이 아니라면, 거의 대부분 리스트를 사용한다고 봐도 무리 없음
- 리스트가 메모리 적게 씀 구현 특성상 리스트가 단순하고 iteration이 더 빠름
트리(tree) 구조의 기본 개념과 용어, 이진트리의 형태에 따른 다양한 종류
- 트리
- 노드들의 집합
- 각 노드는 값과 다른 노드들을 가리키는 레퍼런스로 구성
- 트리 관련 주요 용어
- 간선 (edge)
- 노드와 노드를 연결하는 선
- 구현 관점에서는 레퍼런스를 의미
- a.k.a link, branch
- 루트 노드
- 트리의 최상단에 있는 노드
- 트리의 시작점
- 자녀 노드
- 모든 노드는 0 개 이상의 자녀 노드를 가진다
- 부모 노드
- 자녀 노드를 가지는 노드
- 형제 노드
- 같은 부모를 가지는 노드
- 조상 노드
- 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드
- 자손 노드
- 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
- 내부 노드
- 자녀 노드를 가지는 노드
- 외부 노드
- 자녀 노드가 없는 노드
- a.k.a leaf node, 단말 노드
- 간선 (edge)
- 경로 (path)
- 한 노드에서 다른 노드 사이의 노드들의 시퀀스
- 경로 길이
- 경로에 있는 노드들의 수
- 노드의 높이
- 노드에서 리프 노드까지의 가장 긴 경로 간선 수
- 트리의 높이
- 루트 노드의 높이
- 노드의 깊이 (depth)
- 루트 노드에서 해당 노드까지 경로 간선 수
- 트리의 깊이
- 트리의 있는 노드들의 깊이 중 가장 긴 깊이
- 트리 높이 == 트리 깊이
- 노드의 차수 (degree of node)
- 노드의 자녀 노드 수
- 트리의 차수 (degree of tree
- 트리에 있는 노드들의 차수 중 가장 큰 차수
- 두 노드 사이의 거리
- 두 노드의 최단 경로의 간선 수
- 노드의 레벨
- 노드와 루트 노드 사이의 경로에서 간선의 수
- width
- 임의의 레벨에서 노드의 수
- 노드의 크기
- 자신을 포함한 자손 노드의 수
- 트리의 크기
- 트리의 모든 노드의 수
- 서브 트리
- 각 노드의 자녀 노드들을 재귀적으로 서브 트리를 구성한다
- 트리 구조의 주요 특징
- 루트 노드는 하나만 존재
- 사이클이 존재하지 않음
- 자녀 노드는 하나의 부모 노드만 존재
- 데이터를 순차적으로 저장하지 않는 비선형 구조
- 트리에 서브 트리가 있는 재귀적 구조
- 계층적 구조
- 이진 트리
- 각 노드의 자녀 노드 수가 최대 두 개인 트리
- 형태에 따른 이진 트리의 종류
- full binary tree (정 이진 트리)
- 모든 노드는 자녀 노드가 없거나 두 개인 트리
- Complete binaray tree (완전 이진 트리)
- 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 잇음
- 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져 있는 트리
- perfect binary tree (포화 이진 트리)
- 모든 레벨에서 노드가 빠짐 없이 채워져 있는 트리
- degenerated binary tree (변질 이진 트리)
- 모든 부모 노드는 하나의 자녀 노드만 가지는 트리
- == pathological binary tree
- left skewed binary tree
- 모든 부모 노드는 왼쪽 자녀 노드만 가지는 트리
- right skewed binary tree
- 모든 부모 노드는 오른쪽 자녀 노드만 가지는 트리
- balanced binary tree (균형 이진 트리)
- 모든 노드에서 왼쪽 서브트리와 오른 쪽 서브트리의 높이 차이가 최대 1인 트리
- full binary tree (정 이진 트리)
이진탐색 트리 (binary search tree)
- 이진 탐색 트리
- 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고
- 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가짐
- 최소값
- 트리의 가장 왼쪽
- 최대값
- 트리의 가장 오른쪽
- 중위 순회 (inorder traversal)
- 재귀적으로 왼쪽 서브 트리 순회
- 현재 노드 방문
- 재귀적으로 오른쪽 서브 트리 순회
- 전위 순회 (preorder traversal)
- 현재 노드 방문
- 재귀적으로 왼쪽 서브 트리 순회
- 재귀적으로 오른쪽 서브 트리 순회
- 후위 순회 ( postorder traversal)
- 재귀적으로 왼쪽 서브 트리 순회
- 재귀적으로 오른쪽 서브 트리 순회
- 현재 노드 방문
- 노드의 successor (후임자)
- 해당 노드보다 값이 큰 노드들ㅇ 중에서 가장 값이 작은 노드
- 삽입
- 삭제
- 삭제하려는 노드가 있는지 검색, 있으면 삭제
- 자녀가 없는 노드 삭제
- 삭제 될 노드를 가리키던 레퍼런스를 가리키는 것이 없도록 처리
- 자녀가 하나인 노드 삭제
- 삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀를 가리키게 변경
- 자녀가 두개인 노드 삭제
- 삭제될 노드의 오른쪽 서브 트리에서 제일 값이 작은 노드가 삭제될 노드를 대체한다
- 시간 복잡도best avg wort
insert Θ(1) O(logN) Θ(N) delete Θ(1) O(logN) Θ(N) search Θ(1) O(logN) Θ(N) - 장점
- 삽입 삭제가 유연하다
- 값의 크기에 따라 좌우 서브트리가 나눠지기 때문에 삽입/삭제/검색이 (보통은) 빠르다
- 값의 순서대로 순회 가능하다
- 단점
- 트리가 구조적으로 한쪽으로 편향되면 삽입 삭제 검색 등등 여러 동작들의 수행 시간이 악화된다
