Graph, DFS, BFS, Dijkstra Graph DFS BFS Dijkstra Graph 요약 정의 : 노드의 상하위 개념이 없고, 노드(혹은 버텍스)와 노드들을 잇는 엣지로 구성되어 있는 자료구조 용어 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) 진출 차수(out-degree): 방향 그래픙에서 외부로.. 2020. 7. 19. Tree, Traversal, Binary Search Tree Tree 정의 : '노드'와 '간선'으로 구성 된 자료구조로, 그래프의 한 종류이다. 용어 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다. 내부(internal) 노드: 단말 노드가 아닌 노드 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름) 형제(sibling): 같은 부모를 가지는 노드 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합 노드의 차수(degree): 하위 트리 .. 2020. 7. 19. Hashing ' 용어 정의 해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 균일하게 매핑할수록 좋은 해시함수이다. 해시 : 해시 함수에 얻어지는 값 해시 테이블 : 해시 값을 인덱스로 하여 데이터를 저장하고 있는 자료구조 Hashing 정의 : 데이터를 담을 해시 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시함수에 의해 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 과정 장점 : 데이터 접근 속도가 빠르다. 단점 : 충돌(collision)발생 - 서로 다른 입격 값에 대해 동일한 해시 테이블 주소를 반환하는 경우 해결법 chaining : 충돌되는 데이터들을 해당 주소에 링크드 리스트로 연결 open addressing : 충돌 발생시 해당 주소에 고정 폭 만큼을 더한.. 2020. 7. 19. 탐색1 : 선형탐색, 이진탐색 탐색의 분류 1. 선형 자료구조 ( 어레이, 리스트, ...) 내에서의 탐색 선형탐색 (linear search) 또는 순차탐색 (sequential search) 이분탐색 (binary search) : 분할정복을 이용한 탐색 해싱 (hashing) 2. 비선형 자료구조 ( 트리, 그래프, ...) 내에서의 탐색 tree traversal DFS BFS 선형탐색, linear Search 정의 : 데이터의 집합을 처음부터 끝까지 차례대로 하나씩 검색하는 방법 장점 : 구현하기 쉽고 데이터 집합이 정렬되어 있지 않아도 된다 단점 : 검색시간이 오래걸린다 시간복잡도 worst : O(n) average : O(n) best : O(1) // 첫번째 인덱스의 값이 찾고자 하는 값인 경우 이분탐색, Binar.. 2020. 7. 19. 정렬3 : heap sort Heap Sort 최대 힙 트리나 최소 힙 트리를 이용해 정렬을 하는 방법 heap : 반정렬 상태 ( 부모노드 >= 자식노드 or 부모노드 2020. 7. 19. 정렬2 : 분할정복을 이용한 정렬 분할정복을 이용한 정렬 Merge Sort Quick Sort Merge Sort merge sort pseudo algorithm 1. 정렬할 데이터 집합을 반으로 나눈다 2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1번 작업을 반복한다 3. 원래 같은 집합에서 나뉘어진 두 개의 하위 데이터 집합의 원소들을 크기 순서에 맞춰 정렬하고 병합. 4. 데이터 집합이 하나가 될 때까지 3번작업을 반복 시간복잡도 worst : O(nlogn) average : O(nlogn) best : O(nlogn) Quick Sort quick sort 분할 정복 알고리즘을 이용한 매우 빠른 수행 속도를 자랑하는 정렬 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게.. 2020. 7. 19. 이전 1 2 3 4 5 6 다음
