자료구조21 [자료구조] 13. 탐색 탐색이란? 탐색키: 항목과 항목을 구별해주는 키 정렬되지 않은 배열에서의 탐색 순차탐색(sequential search) : 정렬되지 않은 sequence에서 처음부터 마지막까지 순차적으로 하나씩 검사하는 방법 --> O(n) 정렬된 배열에서의 탐색 이진탐색(binary search) : 정렬된 배열의 중앙에 있는 값을 조사하여, 찾고자 하는 항목이 그 값보다 작은지 큰지 판단하여, 탐색의 범위를 반으로 줄여가며 탐색한다. --> O(log(n)) 색인 순차탐색(indexed sequential search) : 인덱스 테이블을 먼저 검사하여, 탐색키가 속한 범위를 알아낸 후, 순차탐색한다. 보간탐색(interpolation search) : 배열[0]과 배열[n-1] 값을 통해 탐색키가 존재할 위치를 .. 2023. 12. 14. [자료구조] 12. 정렬 선택정렬(selection sort) : 정렬되지 않은 곳에서 비교하여, 가장 작은 애와 배열의 맨 앞의 애를 교환한다. - 시간복잡도: O(n^2) - unstable sort - in-place sort 비교연산: 정렬되지 않은 곳에서 제일 작은 애 이동연산: 교환 --> unstable sort 삽입정렬(insertion sort) : 정렬되지 않은 곳의 맨 앞의 애를, 정렬된 곳에서 비교하여 적절한 자리에 삽입한다. - 시간복잡도: 최악의 경우는 O(n^2), 최선의 경우는 O(n); 대부분 정렬되어 있으면 매우 효과적이다. - stable sort - in-place sort key값에 정렬되지 않은 부분의 맨 앞의 애를 넣는다. --> 공간복잡도: O(1): in-place sort 비교연산:.. 2023. 12. 14. [자료구조] 11. 그래프(2) 최소비용 신장트리(MST: Minimum Spanning Tree) 신장트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리 (사이클 x) 최소비용 신장트리(MST): 모든 정점들을 가장 작은 비용으로 연결하는 트리 Kruscal의 MST 알고리즘 : 모든 edge를 검사하여, least-weight edge를 찾고, 그 edge가 사이클을 만들지 않으면, 추가한다. => 시간복잡도: O(e*log(e)), 모든 edge들의 weight를 한번에 비교하므로, 희박한 그래프에서 유리하다. Union-Find 알고리즘: 사이클을 만드는지 검사하는 알고리즘 Find: 어떤 두 노드의 root를 찾아낸다. root가 서로 다르다면, 두 노드 사이의 edge는 bridge이므로, 그 edge는.. 2023. 12. 14. [자료구조] 10. 그래프(1) 그래프 그래프 용어 그래프 정의 무방향 그래프, 방향 그래프 가중치 그래프 부분 그래프 그래프 용어 인접 정점 정점의 차수 진입 차수(in-degree) 진출 차수(out-degree) 경로(path) 단순 경로(simple cycle): 반복되는 정점 없음 사이클(cycle): 시작 정점 = 종료 정점 단순 사이클(simple cycle) 오일러 사이클: 모든 edge 한번씩만 거쳐서 제자리로으로 돌아온다. (단순 사이클 x) 헤밀턴 사이클: 모든 node 한번씩만 거쳐서 제자리로 돌아온다. (단순 사이클) 그래프 연결 정도 연결 그래프 비연결 그래프 완전 그래프: 모든 정점이 연결되어 있는 그래프 그래프의 표현 방법 인접 행렬(adjacent matrix) 인접 리스트(adjacent list) 그래.. 2023. 12. 14. [자료구조] 1205 (2) 14. 해싱 14. 해싱 해싱이란? 추상 자료형 사전 해싱의 구조 해시함수 개방 주소법 체이닝 해싱의 성능 분석 14.1 해싱이란? : 키(key: 저장할 값) --> 해시함수 --> 해시 값 해시 테이블의 구조 나쁜 해시함수 - 예 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 12. 7. [자료구조] 1205 (1) 13. 탐색 (sorting) 탐색이란? 정렬되지 않은 배열에서의 탐색 정렬된 배열에서의 탐색 이진 탐색 트리 AVL 트리 2-3 트리 13.4 이진탐색 트리 (BST: Binary Search Tree) ▶ 이진탐색 vs. 이진탐색 트리 : 근본적으로 같은 원리에 의한 탐색 구조이다. 이진탐색(binary search): 자료들이 순차적으로 저장되어 있다. --> 삽입/삭제가 비효율적이다. 이진탐색 트리(binary search tree): 삽입/삭제가 빠르다. (삽입: leaf에서!) Q. 이진탐색의 경우 자료들이 순차적으로 저장되어 있어서 삽입이 비효율적이다. 이진탐색 트리의 경우 항상 leaf에서 삽입을 하기 때문에 삽입이 효율적이다. 그런데 삭제의 경우, 이진탐색과 이진탐색 트리 모두 정렬된 배.. 2023. 12. 7. [자료구조] 1201 (2) 13. 탐색 13. 탐색 (searching) 탐색이란? 정렬되지 않은 배열에서의 탐색 정렬된 배열에서의 탐색 이진 탐색 트리 AVL 트리 2-3 트리 13.1 탐색이란? : 여러 개의 자료 중에서 원하는 자료를 찾아내는 작업 탐색키(search key): 항목과 항목을 구별해주는 키 13.2 정렬되지 않은 배열에서의 탐색 순차 탐색(sequential search) 순차 탐색(sequential search) : 정렬되지 않은 sequence, si를 처음부터 마지막까지 순차적으로 하나씩 검사하는 방법 개선된 순차 탐색 : 리스트 끝에 탐색키를 저장한다. --> 탐색에 실패하면, 키 값의 인덱스를 반환한다. (개선된 거 아님...) 13.3 정렬된 배열에서의 탐색 이진 탐색(binary search) 색인 순차탐색.. 2023. 12. 6. [자료구조] 1201 (1) 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.9 기수 정렬 (Radix Sort) : 레코드를 비교하지 않고 정렬을 수행한다. 시간 복잡도: O(dn) --> n*log(n)을 능가하는 빠른 정렬 방법! - d: 자릿수 : 낮은 자릿수 먼저 분류한 다음, 순서대로 읽어서 다시 높은 자릿수를 분류한다. --> 뒷자리가 정렬되었기 때문에, 앞자리 정렬로 전체 정렬이 가능하다. 버킷(추가 공간): 큐로 구현한다. factor: 몇 번째 자릿수를 추출할지 결정한다. 12.10 정렬 알고리즘의 비교 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 12. 5. [자료구조] 1128 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.6 합병 정렬 : 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한다. 분할: Data set 크기가 1이 될 때까지 분할한다. 합병: 비교하여, 정렬한다. **합병 시, sorted 배열(임시 추가 공간)을 list 배열(원래 공간)로 복사해야한다! : 분할된 두 배열을 비교하여, 작은 것을 새로운 배열에 넣는다. (Shorted 배열) 추가 공간이 필요하다. (in-place 아님!) **엔트리 개수가 짝수 개인 경우, mid 계산 주의!! Stable sorting Not in-place (임시 추가 공간 필요하다.) 시간 복잡도: O(n*log(.. 2023. 12. 5. 이전 1 2 3 다음
