탐색이란 여러 개의 자료 중에서 원하는 자료를 찾는 작업 탐색키와 데이터로 이루어진 여러개의 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 방법 정렬되지 않은 배열에서의 탐색 1. 순차 탐색 (Sequential Search) 데이터의 첫 부분부터 순차적으로 데이터를 비교하여 원하는 데이터의 위치를 찾는 알고리즘 탐색 방법중에서 가장 간단하고 직접적인 탐색 방법 평균 비교 횟수 탐색 성공 : (n + 1)/2번 비교 탐색 실패 : n번 비교 시간 복잡도 : O(n) 코드 int seqSearch(int key,int low, int high){ int i; for(i = low;i

프림 알고리즘 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 - 정점선택을 기반으로 하는 알고리즘 - 이전 단계에서 만들어진 신장 트리를 확장하는 방법 동작과정 1. 시작 단계에서는 시작 정점만이 MST집합에 포함 2. 앞 단계에서 만들어진 MST집합에 인접한정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장 (가장 낮은 가중치를 선택) 3. 위의 과정을 트리가 N-1개의 간선을 가질때까지 반복 시간복잡도 주 반복문이 정점의 수 N만큼 반복하고 내부 반복문이 N번 반복 - 프림 알고리즘의 시간복잡도 O(n^2) - 그래프에 간선이 많이 존재하는 밀집 그래프에 프림 알고리즘이 적합

크루스칼 알고리즘(Kruskal MST) 탐욕적인(Greedy) 방법을 이용하여 그래프의 모든 정점을 최소비용으로 연결하는 최적 해답을 구하는 것 동작과정 1. 간선데이터를 비용에따라 오름차순으로 정렬 2. 간선을 하나씩 확인하며 현재의 간선이 싸이클을 발생 시키는지 확인 2-1.사이클이 발생하지 않은 경우 최소 신장 트리에 포함 2-2.사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음 3. 모든 간선에 대하여 2번을 반복 시간복잡도 간선의 갯수가 E개일때 : O(ElogE) 시간이 가장 오래걸리는 부분이 간선을 정렬하는 작업 정렬의 시간복잡도 = O(ElogE)

신장트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프에 사이클이 형성이 되면 안됨 - 그래프의 최소 연결부분 그래프 - 최소연결 = 간선 수가 제일 적다 - n개의 정점을 가지는 그래프에서 n-1 개의 간선으로 연결되어 있는 형태 - 일부 간선을 선택해서 만든 트리 최소 신장트리(Minimum Spanning Tree) 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 - 각 간선의 가중치가 동일하지 않을 때 가장 적은 간선을 사용한다고 해서 최소비용이 얻어지지 않음 - MST는 간선에 가중치를 고려하여 최소 비용의 신장트리를 선택하는 것을 의미 - 간선의 가중치의 합이 최소(n개의 정점엔 n-1개의 간선) - 사이클이 형성 되면 안됨

깊이 우선 탐색(Depth- First Search) 특정 노드에서 시작해 다음 분기(branch)로 넘어 가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘 - 자기 자신을 호출하는 순환 알고리즘 또는 스택의 형태를 지님 - 마지막에 들어온것이 먼저나가는 방식. LIFO(Last In First Out) - 알고리즘을 구현할때 노드의 방문여부 확인 필요 장점 - 현 경로상의 노드만 기억하면 되므로 저장공간의 수요가 비교적 적음 - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음 단점 - 해가 없는 경로에 깊이 빠질 가능성 존재 - 얻어진 해가 최단경로가 된다는 보장이 없음 동작과정 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2-1..

위상 정렬이란 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음 큐와 스택을 통해 구현 가능 위상 정렬 과정 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거 3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복 4-1. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재 4-2. 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과 시간 복잡도 O(V + E)

플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복 시간 복잡도 (최선 = 최악 = 평균) O(V^3) 점화식 distance[i,j] = min(distance[i,j], distance[i,k] + distance[k,j]) 코드 for(int k = 0; k < 4; k++) // k 는 거쳐가는 정점 for(int i = 0; i < 4; i++) // i 는 행 (출발 정점) for(int j = 0; j < 4; j++) // j 는 열 (도착 정점) if (a[i][k] + a[k][j] < a[i][j]) a[i][j] = a[i][k] a[k][j];

다익스트라 알고리즘이란 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 다익스트라 알고리즘 과정 1. 출발점으로부터의 최단거리를 저장할 배열 d[v] 생성. 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채움 2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장 3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교 4. 만약 d[A] + P[A][B]의 값이 더 작다면, d[B]의 값을 이 값으로 갱신 5. A의 모든 이웃 노드 B에 대해 이 작업을 수행 6. A의 상태를 "방문 완료"로 바꾼다. 더 이상 A는 사용하지 않음 7. "미방문" 상태인 모든 노드들 중, 출발점으로부터..