sundori Dev

목차 정렬 병합 정렬 Merge Sort 병합 정렬은 여러 개의 정렬된 자료 집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법이다. 이러한 방법은 전체 원소에 대해 수행하지 않고 부분집합으로 분할 Divide 하고 각 부분 집합에 대해서 정렬 작업을 정복 Conquer 즉, 완성한 후에 정렬된 부분집합들을 다시 결합 Combine 하는 분할 정복 Divide and Conquer 기법을 사용한다. n개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way라고 한다. 여기서 우리는 두 개의 집합을 하나의 집합으로 만들기에 2-way 병합이라 한다. 다음 3가지의 작업을 반복한다. 분할 : 자료들을 두 개의 부분집합으로 분할한다 정복 : 부분집합에 있는 원소를 정렬한다. 결합 ..

목차 정렬 삽입 정렬 Insert Sort 삽입 정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식으로 정렬을 수행한다. 삽입 정렬에서는 정렬할 자료가 두 개의 부분집합 S(Sorted Subset)와 U(Unsorted Subset)로 나뉘고 정렬된 앞부분의 원소는 부분집합 s가 되고, 아직 정렬하지 않은 나머지 원소는 부분집합 U가 된다. 정렬하지 않은 부분 집합 U의 원소를 앞에서부터 하나 하나 꺼내서 이미 정렬한 부분 집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하는 방식이다. 따라서 삽입 정렬을 수행할 때마다 부분집합 S의 원소는 하나씩 늘어나는 반면, 부분집합 U의 원소는 하나씩 줄어든다. 삽입 정렬 작동 과정의 예 주어진 배열: {69, 10, 30, 2..

목차 정렬 선택 정렬 Selection Sort 선택 정렬 Selection Sort은 전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식을 사용한다. 전체 원소 중에서 가장 작은 원소를 찾은 다음 첫째 원소와 자리를 교환하고 둘째로 작은 원소를 찾고 둘째 원소와 자리를 교환한다. 그다음 셋째로 작은 원소를 찾고 셋째 작은 원소와 자리를 교환한다. 위의 사진처럼 각 단계에서 배열의 인덱스를 1씩 증가하면서 배열에어 가장 작은 값을 가진 원소와 교환을 하는 것이다. #include void SelectionSort(int a[], int size) { int i, j, t, min, temp; for (i = 0; i < size - 1; i++) { min = i; for (j = i..

정렬 가지고 있는 자료를 사용하기 편하도록 정렬하려면 어떤 방법이 있을까? 이때 고민해 볼 수 있는 것이 정렬 알고리즘이다. 우선 정렬 Sort이란 순서 없이 배열된 자료를 작은 것부터 또는 큰 것부터 오름차순, 내림차순으로 재배열(재배치)하는 것이다. 여기서 재배열을 하는 기준을 어떻게 정하나인데, 가게를 예를 들면 유통기한 순으로 물건을 다시 진열하거나, 우리가 살면서 해야 할 일을 적을 때도 마찬가지이다. 이처럼 일상생활에서 자주 사용하는데.... 자료를 정렬하는데 사용하는 기준이 되는 특정 값(유통기한, 날짜 등)을 켜라고 한다. 따라서 우리는 그 키를 기준으로 정렬하면 크기가 키가 된다. 정렬 방식의 분류 기준 정렬 방식 설명 실행 방법 비교식 정렬 Comparative Sort 비교할 각 키값..

최단 경로 플로이드 Floyd 최단 경로 알고리즘은 모든 정점 사이의 최단 경로 All to Shortest Path를 구하고 최단 경로로 만드는 알고리즘이다. 1. 초기 2차원 배열에 각 정점에서의 거리를 2차원 배열로 초깃값으로 집어넣는다. 2. 여기서부터 adj [v][w]=MIN(adj [v][w], adj [v][k]+adj [k][w])라는 식을 사용한다. 정점 0부터 k까지의 정점만을 이용한 정점 v에서 정점 w까지의 최단 경로를 의미하는데 정점 0부터 정점 k -1까지의 정점을 고려한 최단 거리 adj을 구한 상태에서 다음 정점 k를 정할 때, adj [v][w]와 adj [v][k] + adj [k][w] 중에서 작은 값을 최단 경로로 정한다. #include #define INF 100..

최단 경로 최단 경로는 신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치의 합이 최소인 경로이다. 예를 들어 지하철 노선 어플을 보면 내가 원하는 출발지에서 목적지까지의 최단 경로를 구하는 어플, 그리고 내비게이션이 있다. 이러한 최단 경로를 구하는 가중치 그래프에서는 가중치 인접 행렬 Weight Adjacent Matrix를 사용하는데, 이 가중치 인접 행렬은 2차원 배열이며, 두 정점 사이에 간선이 없으면 0이 아니라 무한∽이라는 값이 저장되어 있다고 가정하고 사용한다. 그렇게 최단 경로를 찾는 방법에는 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구하는 다익스트라 Dijkstra 최단 경로 알고리즘과 모든 정점에서 다른 모든 정점까지의 최단 ..

목차 크루스칼 알고리즘 2 이 알고리즘은 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만들어가는 알고리즘이다. 크루스칼 알고리즘 2를 적용한 최소 비용 신장트리를 만들기 위해서는 밑에 4가지의 순서를 지키며 트리를 생성하면 되는데... 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 그래프에서 가중치가 가장 낮은 간선을 삽입한다. 단, 이때 정점을 그래프에서 사이클을 형성하는 간선은 삽입할 수 없으므로 그다음으로 가중치가 낮은 간선을 삽입한다. 그래프에 간선이 n-1개 삽입될 때까지 2번 과정을 반복한다. 그래프에 간선이 n-1개가 되면최소 비용 신장 트리가 완성된다. 그렇다 이 순서를 읽어보면 크루스칼 알고리즘 1과 다르게 정점과 간선을 삽입하면서 최소 비용 신장 트리를 만들어가는..

목차 신장트리 그래프의 관점에서 트리를 보면 사이클이 없는 연결 그래프이다. 사이클이란 순환 경로에서 시작 정점과 종료 정점이 동일한 경우를 말한다. 모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 트리의 형태의 부분 그래프를 신장 트리 Spanning Tree라고 한다. 깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리(Depth First Spanning Tree)라고하며, 너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장트리(Breadth First Spanning Tree)라고 한다. 위의 사진을 보면 알다시피 모든 정점이 무조건 한 번씩 연결이 되어있는데 이것이 바로 간선을 최소로 이용하여 모든 정점을 연결한 신장트리이다. 이렇게 간선을 최소..

목차 너비 우선 탐색(BFS) 큐를 활용: 너비 우선 탐색은 시작 노드에서 인접한 모든 노드를 먼저 방문한 후, 그 다음 레벨의 노드들을 방문하며, 이를 위해 큐를 사용한다. 노드 방문: 시작 노드에서 인접한 노드를 먼저 모두 방문한 후, 다음 레벨의 노드로 이동하며 방문한 노드는 표시하여 중복 방문을 방지한다. 너비 우선 탐색의 특징: 레벨 단위로 탐색하기 때문에 최단 경로를 찾는데 효과적이며, 큐를 사용하기 때문에 반복문으로 구현하기 용이하다. 즉, 시작 정점에 인접한 정점을 모두 차례로 방훈하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례대로 방문하는 방법이다. 가까운 정점을 먼저 방문하고 난 뒤 멀리 있는 정점을 나중에 방문한다. #pragma once #include #include ..

목차 그래프 순회의 개념 한 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 확인하는 것을 그래프 순회 Graph Traversal 또는 그래프 탐색 Graph Search라고 한다. 깊이 우선 탐색(DFS) 스택 또는 재귀 함수를 활용: 깊이 우선 탐색은 특정 경로를 따라 끝까지 탐색한 후 다른 경로를 탐색하고, 이를 위해 스택을 사용하거나 재귀 함수를 호출하여 구현한다. 노드 방문: 시작 노드에서 출발하여 한 경로를 끝까지 탐색한 후 되돌아와서 다른 경로를 탐색하며, 방문한 노드는 표시하여 중복 방문을 방지한다. 깊이 우선 탐색의 특징: 한 경로를 완전히 탐색하기 때문에 목표 노드가 발견되면 바로 종료할 수 있으며, 특히 트리 구조에서는 재귀를 통해 간단하게 구현이 가능하다. 즉, 시작..