sundori DevStory

목차 검색 말 그대로 무언가를 찾는 것인데 우리가 영어 사전에서 의미가 궁금한 단어를 검색하거나, 인터넷에서 맛집을 찾을 때 검색을 한다. 이러한 검색도 정렬처럼 자료구조를 활용하는데, 자료를 만들고 저장하고 정렬하는 이유는 자료를 사용하기 위해서이고, 사용하려면 자료 중에서도 원하는 항목을 찾아야 한다. 따라서 자료를 검색하는 것은 원하는 탐색 키를 가진 항목을 찾는 것이다. 저장한 자료는 그 자료를 구별하여 인식할 수 있는 키를 가지고 있는데, 이것을 탐색 키 Search Key라고 한다. 또한 자료 속에서 원하는 자료를 찾으면 성공 Hit이라고 하며, 실패한다면 검색 실패 Miss라고 한다. 이러한 검색 연산은 삽입 연산과 삭제 연산을 할 때도 필요하다. 원소를 삽입하거나 삭제하려면 먼저 그 위치를..

목차 정렬 히프 정렬 Heap Sort 히프 정렬은 히프 자료구조를 이용하여 정렬하는 방법이다. 히프에서는 항상 가 장 큰 원소가 루트 노드가 되고. 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하는 특징이 있다. 그러므로 최대 히프에 대해서 원소 개수만큼 삭제 연산을 수행하면 내림차순으로 정렬된 원소를 얻을 수 있고, 최소 히프에 대해서 원소 개수만큼 삭제 연산을 수행하면 오름차순으로 정렬된 원소를 얻을 수 있다. 히프 정렬은 정렬할 원소들을 하나씩 히프에 삽입하여 정렬할 n개의 원소를 가진 최대 히프를 구성한다. 히프에 삭제 연산을 수행하여 얻은 루트 원소를 저장하고, 히프를 다시 최대 히프가 되도록 재구성하는 작업을 원소의 개수만큼 반복하면 정렬을 완성할 수 있다. 2023.11.20..

목차 정렬 기수 정렬 Radix Sort 기수 정렬은 분배 방식의 정렬 방법으로 정렬할 우너소의 키값에 해당하는 버켓에 원소를 분배하였다가 버켓(큐)의 순서대로 원소를 꺼내는 방법 반복한다. 기수 정렬은 원소의 키를 표현하는 값의 기수 Radix만큼 버켓이 필요하고, 키값의 자릿수만큼 정렬을 반복한다. 첫 번째 단계 (가장 낮은 자리의 숫자에 대한 정렬): 배열을 가장 낮은 자리의 숫자(1의 자리)에 따라 0부터 9까지의 버켓으로 나눈다. 버켓 0: {10, 30} 버켓 1: {31} 버켓 2: {2, 22} 버켓 3: {} 버켓 4: {} 버켓 5: {} 버켓 6: {16} 버켓 7: {} 버켓 8: {8} 버켓 9: {69} 버켓의 순서대로 배열을 업데이트한다: {10, 30, 31, 2, 22, 1..

목차 정렬 병합 정렬 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과 다르게 정점과 간선을 삽입하면서 최소 비용 신장 트리를 만들어가는..