자료구조12 [자료구조] 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. [자료구조] 1201 (1) 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.9 기수 정렬 (Radix Sort) : 레코드를 비교하지 않고 정렬을 수행한다. 시간 복잡도: O(dn) --> n*log(n)을 능가하는 빠른 정렬 방법! - d: 자릿수 : 낮은 자릿수 먼저 분류한 다음, 순서대로 읽어서 다시 높은 자릿수를 분류한다. --> 뒷자리가 정렬되었기 때문에, 앞자리 정렬로 전체 정렬이 가능하다. 버킷(추가 공간): 큐로 구현한다. factor: 몇 번째 자릿수를 추출할지 결정한다. 12.10 정렬 알고리즘의 비교 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 12. 5. [자료구조] 1124 12. 정렬정렬이란?선택 정렬삽입 정렬버블 정렬셸 정렬12.1 정렬이란?정렬 알고리즘 분류(1) 단순하지만 비효율적인 방법 vs. 복잡하지만 효율적인 방법 (2) 내부 정렬 vs. 외부 정렬우리는 내부 정렬만을 다룬다.Space complexity: 새로운 공간이 필요한가? (3) 안정성 (stability): 나중에도 순서가 유지될 애들은 처음부터 순서를 유지하면서 정렬하는가?▶ Stable sort:삽입정렬 (insertion sort): 정렬되지 않은 곳에서 정렬된 곳으로 삽입한다. (정렬된 곳에서 비교한다.)버블정렬 (bubble sort): 2개의 레코드를 비교해서 순서를 바꾼다. 따라서 한 단계마다 가장 큰 레코드의 순서는 정해진다.합병정렬 (merge sort): 부분 리스트로 분할해서 정렬.. 2023. 12. 2. [자료구조] 1121 (2) - 12. 정렬 12. 정렬 정렬이란? 선택 정렬 삽입 정렬 버블 정렬 셸 정렬 합병 정렬 퀵 정렬 히프 정렬 기수 정렬 정렬 알고리즘의 비교 12.1 정렬이란? : 데이터들을 특정 순서(오름차순, 내림차순 등)로 정리하는 것 정렬의 대상 : 일반적으로 정렬시켜야 될 대상은 레코드(record)이다. 정렬 알고리즘 개요 출처: 이화여자대학교 이숙영교수님 자료구조 2023. 11. 28. [자료구조] 1121 (1) 11. 그래프(2) 최소 비용 신장 트리 (MST: Minimum Spanning Tree) Kruscal의 MST 알고리즘 Prim의 MST 알고리즘 최단 경로 Dijkstra의 최단 경로 알고리즘 Floyd의 최단 경로 알고리즘 위상 정렬 11.5 Dijkstra의 최단 경로 알고리즘 Dijkstra's 최단경로 프로그램 Dijkstra's 최단경로 알고리즘 복잡도 : 네트워크에 n개의 정점이 있다면, Dijkstra의 최단경로 알고리즘은 주 반복문을 n번 반복하고, 내부 반복문을 2n번 반복하므로, O(n^2)의 복잡도를 가진다. 11.6 Floyd의 최단 경로 알고리즘 Floyd의 최단경로 알고리즘 : 모든 정점과 정점 사이의 최단경로를 찾는다. Floyd의 최단경로 알고리즘 아이디어 A^k[i].. 2023. 11. 28. 이전 1 2 다음
