선택 정렬 이란 간단히 말해서 수열에서 가장 작은 값을 맨 앞으로 보내는 과정을 반복하는 것이다. 시간 복잡도 : O(N^2) 상당히 비효율적이라 잘 쓰진않지만 코드가 간단하다. 알고리즘 1. 배열 전체를 탐색하며 최소값과 인덱스를 저장. 2. 맨 앞인덱스와 최소값의 인덱스의 값을 교환. 3. 비교인덱스 +1 4. 1-3 과정 반복. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include using namespace std; int main() { int arr[10] = { 1,10,5,8,7,6,2,4,3,9 }; int min, idx, temp; cout

플루이드 - 와샬 알고리즘은 그래프 탐색 알고리즘중 가장 간단하지만 모든 정점사이의 최단거리를 구할 수있다. 하지만 시간 복잡도가 O(N^3) 이므로 정점의 갯수가 많으면 쓰는데 제약이있다. 설명보다는 문제를 보면서 이해하는게 쉽다. 문제 링크 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 ..

깊이 우선 탐색 (depth-first search: DFS) 정의 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사 알고리즘 1. 시작지점을 기준으로 이동가능한 경우 자기자신을 호출(재귀 함수) 를 통하여 방문가능한 곳까지 방문. 2. 이미 방문하였거나 더이상 방문할 수 없을경우 return. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31..

BFS(너비 우선 탐색) 정의 너비 우선 탐색(Breadth-first search, BFS)은 그래프 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 자료구조 큐를 이용하여 구현. 그림에서 보면 회색은 현재 큐에 들어가있는 정점이고 검은색은 방문완료한 정점이다. 알고리즘 (2차원 배열기준) 1. 큐를 이용하여 시작점을 먼저 push . 2. 큐가 비워 질때까지 반복 3. 시작점을 중심으로 상,하,좌,우 중 탐색가능한지점을 큐에 넣어주고 탐색이 끝 날때 까지반복. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..