자료구조6 [자료구조] hashing, hash function, map, hash table, hash set | 종합 선물 세트..? 모의면접에서 hash 파트 정확하게 잘 모르는 걸 어떻게 알았는지... 해시(스터디원)가... 자꾸 해시를 물어봤다... 가만안도오. 😫 이번엔 제대로 대답한다.. 가보자 해시 나라로. 자료구조 공부에서 기본은 해당 자료구조의 특징과 문제점. 그리고 구체적으로 어느 곳에서 사용되는지(use case)를 아는 것이다! 거기서 추가적으로 대답의 깊이를 가져가기 위해서는 hash 자료구조 같은 경우에는 hash function을 만들 때 고려할 점과 collision 상황 해결 방법에 대해서 알면 좋다! DFS : 좁고 깊게 vs BFS : 얕고 넓게 10개의 질문에 BFS로 대답하는 것보다 1개라도 DFS로 대답하자!!! 다시 한 번 다짐하며! 정말 출~발~ 💫 hash 대략적인 개념들부터 살펴보자. [ 해.. 2023. 4. 18. [자료구조] Red-Black 트리 [ 이진 탐색 트리(BST, Binary Search Tree)의 단점 ] 균등 트리 : 노드 개수가 N개일 때 O(logN) 편향 트리 : 노드 개수가 N개일 때 O(N) 이진 탐색 트리는 최악의 경우 한쪽으로 편향된 트리일 때 O(N) 시간이 걸린다. 이 말은 모든 노드를 한 번씩 다 확인해줘야 한다는 의미이다. 이러한 단점을 개선한 균형 트리인 Red-Black 트리에 대해서 알아보자. 🔴 Red-Black 트리 ⚫️ 이진 탐색 트리의 단점을 개선하기 위한 자료구조 이진 탐색 트리(BST)의 한 종류 스스로 균형(balancing) 잡는 트리 BST의 worst case의 단점을 개선해서 모든 경우에 O(logN) 모든 노드는 red 혹은 black ✔️ 5가지 속성 모든 노드는 red 혹은 bla.. 2023. 3. 2. [자료구조] 서로소 집합 (Disjoint Sets), 사이클 판별 알고리즘 서로소 집합: 공통 원소가 없는 두 집합을 의미한다. 1. 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 합치기 찾기(Union-find) 자료구조라고 부르기도 한다. ✔️연산 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 ✔️ 동작 예시 1) 합치기 연산 1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. 1) A와 B의 루트 노드 A', B'를 각각 찾습니다. 2) A'를 B'의 부모 노드로 설정합니다. 2. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복합니다. ✔️ 기본 소스 코드 예제 #.. 2022. 8. 8. [자료구조] 그래프(Graph) 1. 그래프(Graph) - 연결되어 있는 객체 간의 관계를 표현하는 자료 구조 - 그래프는 정점(Vertex)과 이들을 연결하는 간선(Edge)들의 집합으로 구성된다. - N:N 관계 표현이 용이하다. ✔️ 종류 : 간선(edge)의 종류에 따라 구분 무향 그래프 (Undirected Graph) 양 방향으로 이동 ex) (A,B) (B,A) 유향 그래프 (Directed Graph) 간선의 방향으로만 이동 가능 ex) 가중치 그래프 (Weighted Graph) 간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프 ex) 네트워크 사이클 (Cycle) 시작 정점과 종료 정점이 동일한 그래프 비순환 그래프 (Acyclic Graph) 사이클이 없는 그래프 완전 그래프 (Complete Gr.. 2022. 8. 1. [자료구조] 트리 (Tree) 비선형 구조, 그래프의 특수한 형태 중 하나이다. 1. 개념 그래프 정점(vertex)과 간선(edge)로 이루어져 있는 자료구조 방향이 있는 간선을 포함한 그래프를 유향 그래프 처음 시작한 정점으로 다시 돌아오는 경로를 '사이클' 트리 특별한 성질을 갖는 그래프를 트리로 각 노드가 하나의 부모 노드와 간선으로 연결되어있는 자료구조 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개. • 트리의 간선들은 모두 방향성을 갖는다. • 어떤 정점을 가리키는 정점의 개수는 최대 1개이다. • 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다. • 트리는 사이클을 갖지 않는다. 디렉터리(폴더) -> 트리 구조 예시 이진 탐색 트리 (Bi.. 2022. 7. 29. [자료구조] 연결 리스트 (Linked list) 0. 개요 순차 리스트 연결 리스트 장점 i 번째 원소의 값 접근이 빠름 연속된 값 읽기가 빠름 원소의 삽입 / 삭제가 빠름 단점 원소의 삽입 / 삭제가 느림 i 번째 원소의 값 접근이 느림 연속된 값 읽기가 느림 ✔️ 메모리 컴퓨터에는 3가지 중요한 부품 CPU 메모리(memory) : RAM 스토리지(storage) : HDD/SSD 메모리 : 속도 빠르다. 용량이 작다. 전기를 끄면 데이터가 사라진다. 스토리지 : 속도 느리다. 용량이 크다. 전기를 꺼도 데이터가 남아있다. 따라서 데이터는 기본적으로 스토리지에 저장되고 프로그램을 실행할 땐 프로그램과 데이터는 메모리로 옮겨져 CPU는 메모리에 로드된 데이터로 작업을 한다. 🚩 자료구조를 공부하는 이유: 메모리의 효율적인 사용 1. 구조 node (.. 2022. 7. 27. 이전 1 다음 반응형
