Coding Story

이분 탐색이란? 이분 탐색은 이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법으로 실제로 이분 탐색의 시간복잡도가 순차적 탐색보다 낮다. 순차 탐색: 리스트 안에 있는 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이분 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이분 탐색 방법 처음 범위는 인덱스 0부터 끝까지이다. 이 때 중간 인덱스를 mid로 한다. mid의 값와 찾는 원소를 비교한다. 2-1) 찾는 원소와 mid의 값이 같다면 탐색 종료한다. 2-2) mid의 값 < 찾는 원소 일 때 left는 mid + 1로 하여 2)를 다시 반복한다. ..

선택 정렬 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다. 1. 입력 배열에서 최솟값을 발견한 다음, 이 최솟값을 배열의 첫번째 요소와 교환한다. 2. 첫번째 요소를 제외한 나머지 요소들 중에 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 3. 이 절차를 숫자 개수-1 만큼 되풀이 한다. #define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t)) void selection_sort(int list[], int n) { int i, j, least, tmp; for (i = 0; i < n - 1; i++) { least = i; // 최솟값 인덱스 for (j = i + 1; j < n; j++) { // 인덱스 i+..

Dijkstra 최단 경로 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 n개의 정점이 있다면 O(n^2)의 시간복잡도를 가진다. #include #include #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 100 #define INF 1000L typedef struct GraphType { int n; // 정점의 개수 int weight[MAX_VERTICES][MAX_VERTICES]; }GraphType; int distance[MAX_VERTICES]; // 시작 정점으로부터의 최단경로 거리 int found[MAX_VERTICES]; // 방문한 정점 표시 // 선택되지 않은 정점 중 distance 값이 가..

신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 모든 정점들이 연결되어 있고 사이클을 포함하면 안된다. 그래프의 최소(간선의 수가 가장 작은) 연결 부분 그래프 n개의 가지는 그래프는 최소한 (n-1)개의 간선을 가진다. 간선에 비용을 붙여 링크의 구축 비용까지를 고려해 최소 비용의 신장 트리를 선택해야함 통신 네트워크 구축에 많이 사용 최소 비용 신장 트리(MST) 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결 신장 트리 중에서 사용된 간선들이 가중치 합이 최소인 신장 트리 Kruskal, Prim 알고리즘이 대표적 반드시 n-1 개의 간선만 사용하고, 사이클이 포함되어서는 안된다. Kruskal 의 MST 알고리즘 탐욕적인 방법(greedy metho..

그래프 탐색 알고리즘 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다. 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다. 그래프의 탐색 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 두가지가 있다. 깊이 우선 탐색(DFS: depth first search) 그래프의 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행한다. 알고리즘 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 띈다. 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택하여 깊이 우선 탐색을 다시 시작한다..