본문 바로가기

C언어/알고리즘

 (17)
[알고리즘] ch 8. 정렬(2) - 퀵 정렬 8.4 퀵 정렬 - 분할 정복(Divide and Conquer)에 바탕을 둔 알고리즘 1) 기준 요소 선정 및 정렬 대상 분류 - 자료구조에서 기준이 될 요소를 임의로 선정하고 기준 요소(Pivot)의 값보다 작은 값을 가진 요소는 기준 요소의 왼쪽으로, 큰 값을 가진 요소는 오른쪽으로 옮김 2) 정렬대상 분할 - 기준 요소 왼쪽에는 기준 요소보다 작은 요소의 그룹, 오른쪽에는 큰 요소의 그룹이 생김 여기에서 왼쪽 그룹과 오른쪽 그룹을 분할하여 각 그룹에 대해 1)의 과정 수행 3) 반복 - 그룹의 크기가 1 이하여서 더 이상 분할할 수 없을 때까지 1), 2)의 과정을 반복하면 정렬이 완료 ex) - 5를 기준으로 5보다 작은 요소를 왼쪽에, 큰 요소들은 오른쪽에 모음 - 5보다 작은 1,4,3,2는..
[알고리즘] ch 8. 정렬(1) - 버블 정렬, 삽입 정렬 8.1 정렬 알고리즘의 개요 정렬(Sorting) - 정해진 기준에 따라 데이터를 순서대로, 그리고 체계적으로 정리하는 알고리즘 - 정렬의 목적은 '탐색' 8.2 버블 정렬 - 자료 구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬 수행 - 버블 정렬은 이웃 요소끼리 데이터를 교환하므로 교환 전에 먼저 이웃끼리 비교하여 바른 순서로 위치해 있는지 확인해야 함 - 왼쪽에 있는 요소가 오른쪽에 있는 요소보다 작아야 함 ex) - 제일 왼쪽에 있는 요소부터 오른쪽에 이웃한 요소와 데이터를 비교해나감 - 왼쪽이 5, 오른쪽이 1이므로 두 이웃 요소 간 데이터를 교환 - 5, 6은 정렬되어 있으니까 넘어감 - 왼쪽이 4, 오른쪽이 6이므로 교환 - 제일 큰 수인 6을 제외한 나머지 요소들은 여전히 정려되..
[알고리즘] ch 7. 그래프(4) - 최소 신장 트리( 크루스칼 알고리즘) 7.5.2 크루스칼 알고리즘 크루스칼 알고리즘(Kruskal's Algorithm) - 그래프 내 모든 간선의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축 - 과정 1) 그래프 내의 모든 간선을 가중치의 오름차순으로 정렬하여 목록을 만듬 2) 단계 1에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가. 단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안됨 - 사이클 탐지 방법으로 분리 집합 이용 - 각 정점별로 각각의 분리 집합을 만들고, 간선으로 연결된 정점들에 대해서는 합집합을 수행 - 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 됨 ex) - 정점 사이에 있는 모든 간선을 가중치 오름차순..
[알고리즘] ch 7. 그래프 (3) - 최소 신장 트리(프림 알고리즘) 7.5 최소 신장 트리  - 그래프는 정점의 집합과 간선의 집합으로 이루어진 자료구조 - 간선은 정점과 정점의 인접 관계를 설명하는 요소  신장 트리 (Spanning Tree) - 그래프의 모든 정점을 연결하는 트리  - 그래프의 하위 개념  최소 신장 트리 (Maximum Spanning Tree) - 최소 가중치 신장 트리 - 여러 간선 중 가중치의 합이 최소가 되는 간선만 남긴 신장 트리 - ex) 최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라  7.5.1 프림 알고리즘  프림 알고리즘 (Prim's Algorithm) 과정  1) 그래프와 최소 신장 트리를 준비 2) 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 ..
[알고리즘] ch 7. 그래프 (2) - 위상 정렬 7.4 위상 정렬 위상 정렬 (Topological Sort) - 위상 = 어떤 정점이 다른 정점과의 관계 속에서 가지는 위치 - 그래프 내 서로 인접한 정점 사이의 관계에 '위치'라는 속성이 존재한다는 뜻 - 위치는 간선 방향에 의해 결정 - 간선을 뻗어내는 정점이 앞이 되고, 간선을 받아들이는 정점이 뒤가 됨 - 이 앞/뒤 관계를 정렬하는 작업이 위상정렬 - '순서가 정해져 있는 작업'을 차례로 수행해야할때 그 순서를 결정해주기 위해 사용하는 알고리즘 - 위상을 정렬하려면 1) 그래프에 방향성이 있어야 하며 2) 그래프 내에 사이클이 없어야 함 -> DAG(Directed Acyclic Graph) 7.4.1 위상 정렬의 동작 방식 - 간선은 정점과 정점 사이의 관계를 설명하는 역할 수행 - 두 정점..
[알고리즘] ch 7. 그래프 (1) 7.1 그래프의 개요 - 그래프는 '정점의 모음'과 이 정점을 잇는 '간선의 모음'이 결합한 것 - 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G=(V,E)이다. - 간선으로 연결된 두 정점을 가리켜 서로 '인접(Adjacent)'또는 '이웃 관계'에 있다고 말함 - 간선을 통해 서로 이웃이 된 각 정점은 그래프 안에서 길을 만듬 ex) 정점 A에서 정점 C까지는 A,B,C가 하나의 경로(path)를 이루고, A,D,C가 또 하나의 경로를 형성함 - 경로는 길이를 가지는데, '길이'는 정점과 정점 사이에 있는 간선의 수로 정의 ex) 경로 A,B,C 사이에는 간선이 (A,B)와 (B,C) 2개가 있으니 길이가 2 - 사이클(Cycle) = 어느 경로가 정점 하나를 두번이상 거치도록 ..
[알고리즘] ch 6 우선순위 큐와 힙 6.1 우선순위 큐 우선순위 큐(Priority Queue) - 우선순위 속성을 갖는 데이터의 삽입(Enqueue)과 제거(Dequeue)연산을 지원하는 ADT - 큐는 먼저 들어온 요소가 무조건 먼저 나오게 하지만, 우선순위 큐는 새로운 요소에 우선순위를 부여해서 큐에 삽입하고 가장 높은 우선순위를 가진 요소부터 빠져나오게 함 6.1.1 우선순위 큐의 삽입/제거 연산 - 우선순위 큐의 각 요소는 '우선순위'를 가짐 1) 노드 삽입 연산 ex) 우선순위가 20인 요소 삽입 - 우선순위 큐의 첫 요소부터 순차적으로 우선순위를 비교 - 20은 2와 17보다 크고 22보다 작으므로 17과 22사이에 삽입 2) 노드 제거 연산 - 전단만 제거해서 반환 6.2 힙 힙(Heap) - 힙 순서 속성(Heap Orde..
[알고리즘] ch 5. 탐색(3) - 레드 블랙 트리 5.5 레드 블랙 트리 레드 블랙 트리 (Red Black Tree) - 레드 블랙 트리에서 노드의 색은 트리 전체의 균형을 유지할 수 있게 함 레드 블랙 트리의 노드 구조체 typedef int ElementType; typedef struct tagRBTNode { struct tagRBTNode* Parent; struct tagRBTNode* Left; struct tagRBTNode* Right; //노드의 색을 나타내는 Color 필드로, RED 아니면 BLACK 값을 저장 가능 enum { RED, BLACK }Color; ElementType Data; }RBTNode; 6.5.1 레드 블랙 트리의 구현 규칙 1) 모든 노드는 빨간색이거나 검은색이다 2) 뿌리 노드는 검은색이다 3) 잎 노..

티스토리툴바