본문 바로가기

자료구조7

[알고리즘] Graph (2) - Depth-first search(DFS) [2. Depth-first search 깊이우선탐색] 1. 깊이우선탐색 - 무방향그래프 → 그래프의 탐색을 위해 Recursive call을 활용한다. → 가능한 연결되어 있는 노드들을 방문하며 → 방문 순서는 특별한 지시가 없을 경우 오름차순을 따른다. → 각 vertex v에서 탐색을 시작할 경우 → v는 이미 방문한 것으로 표시(visit[v]=1) → v에 연결된 vertex w중에서 아직 방문하지 않은(visit[w]=0인) vertex 방문 → 더이상 방문할 vertex가 없으면 직전 노드로 return Ex) 2. Spanning Tree (DFS Tree) → 주어진 그래프에서 방문되는 n-1개의 간선들로 모든 개체를 연결한 서브그래프 → DFS tree에서 root node에 다른 노드.. 2022. 11. 15.
[알고리즘] Graph (1) - Prologue [1. Prologue 개요] 1. 그래프란? → Graph : 개체와 개체들 사이의 링크로 연결된 1:1 관계를 시각적으로 나타내는 수학적 표시, 개체와 그 개체를 연결하는 링크의 집합 → vertex : 개체 → edge : 개체를 연결하는 링크, 개체간 관계를 나타냄 → G = (V, E), 그래프는 두 개의 요소(개체, 관계)를 가짐 2. 그래프의 종류 → 방항성 : 링크의 방향이 정해진 그래프 / 방향이 정해지지 않은 그래프 → 가중치 : 링크의 가중치가 정해진 그래프 / 가중치가 정해지지 않은 그래프 → 방향x, 가중치x : 무방향 그래프 → 방향x, 가중치o : 가중치 그래프 → 방향o, 가중치x : 방향그래프 → 방향o, 가중치o : 방향가중치 그래프 3. 그래프의 표현 (1) Edge l.. 2022. 11. 8.
[알고리즘] Divide & Conquer (3) - Quick sort [3. Quick sort, 쾌속 정렬] ● 방식 → 집합 A의 원소들을 오름차순으로 정렬하고자 할 때(또는 내림차순) → 집합 내의 원소 중 하나를 무작위로 골라 (주로 A[0]=pivot) → pivot을 기준으로 pivot보다 작은 원소는 pivot의 앞에 → pivot보다 큰 원소는 pivot의 뒤에 배치한다. → 이 때, pivot을 제외한 맨 앞과 맨 뒤의 값들을 서로 비교하여 → 앞의 값이 뒤의 값보다 클 경우, 자리를 서로 바꾼다. → 배열을 두 개로 분할한다는 점에서 합병정렬과 비슷하지만, 결합하지 않으므로 합병정렬의 발전형이라 할 수 있다. ● 알고리즘 → Divide : m=Partition() → Conquer : Quick_sort(s, m-1, A), Quick_sort(m+1,.. 2022. 11. 8.
[알고리즘] Divide & Conquer (2) - Merge sort [2. Merge sort, 합병정렬] ※ 배열의 요소들을 정렬할 때 인접한 각 요소들을 비교하는 방식(bubble sort 등)의 성능 : O(n²) 따라서, 더 효율적일 수 있는 방법은 "분할정복" ● 방식 → 정렬되지 않은 상태로 나열된 요소들의 집합을 절반으로 나누고 → 각각의 분할된 집합을 정렬한 다음 → 다시 결합한다 ● 알고리즘 → Divide : m = (s+e)/2 를 기준으로 더이상 분할할 수 없을때까지 절반으로 분할 O(n) → Conquer : 더 이상 분할할 수 없을 때 원소가 하나인 집합이므로, 정렬된 것으로 간주 → Combine : 분할 후 각 집합들을 결합 O(logn) → Degenerate case : 원소가 하나인 경우 (s==e) (* 배열A내에 원소가 n개인 경우 .. 2022. 11. 8.
[알고리즘] Divide & Conquer (1) - Binary search [1. Binary search, 이진탐색] ● 방식 → A를 오름차순으로 정렬된 n개 요소들의 리스트라고 할 때, → 찾으려는 값 x가 A내에 몇 번째에 존재하는지 확인하는 알고리즘이다. → x를 A내의 요소들의 중앙값(A[m])과 비교하여 → x = A[m]이면 m을 반환, → x A[m]이면 다시 x를 A[m+1 ~ e]에서 탐색하는 방식이다. (* A내에 n개의 원소가 있다면 s=0, e=n-1) ● 알고리즘 → Divide : m = (s+e)/2를 기준으로 배열을 분할 → Conquer : A[s, m-1] 또는 A[m+1, e] → Degenerate case : A 또는 분할된 A 내에 원소가 하나인 경우 (s==e) ● .. 2022. 11. 5.
[알고리즘] Prologue - Recurrence relation, master theorm 1. 점화식 표현 → 수열의 어떠한 항을 표현할 때, 그 이전의 항들을 활용하는 것 Ex) 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, ... → f(n) = f(n-1) + f(n-2) → 위와 같은 표현을 '점화식 표현'이라 한다. 2. Master theorm 3. Fibonacci sequence → 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ● 구현 (1) recursive call 방식 #include int Fibonacci(int n) { if (n == 0 || n == 1)//degenerate_case return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } (2) 배열+반복.. 2022. 11. 5.

티스토리툴바