버블 정렬은 인접한 두 수를 비교하여 작은수를 앞으로 큰수를 뒤로 보내는 방법이다.(오름차순 기준) 정렬이 앞이아니라 뒤에서 부터 된다는 특징을 가진다. 시간 복잡도 : O(N^2) 정렬 과정 알고리즘 1. 첫번째 인덱스와 두번째 인덱스를 비교하여 큰수가 뒤로가게 교환한다. 2. 1번과정을 마지막 인덱스 까지 진행 3. 2번과정이 1번진행되면 가장 큰수가 뒤로 가기때문에 그다음 에는 마지막 인덱스-1까지 1-2 번 과정을 진행. 4. 정렬이 완벽해질때까지 진행. 코드 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 #include using namespace std; int main() { int arr..

선택 정렬 이란 간단히 말해서 수열에서 가장 작은 값을 맨 앞으로 보내는 과정을 반복하는 것이다. 시간 복잡도 : 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

문제 링크 : https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 문제 설명 거의 최단경로 : 시작점에서 목적지 까지 가는 최단경로를 이용하지 않고 갈 수있는 최단 경로 . 1. 단..

문제 링크 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는(1) 상태와 꺼져 있는 (0) 상태 중 하나의 상태를 가진다. i(1> result; answer = INF; //0번째 스위치를 누르지 않은 상태에서 시작 copyS = s; simulation(1, 0); //0번째 스위치를 누른 상태에서 시작 copyS = s; push(0); simulation(1, 1); if (answer == INF) 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..