문제 링크: https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제 설명 1.가중치가 있는 양방향 그래프가 주어짐. 2. 가중치는 다리가 버틸수있는 최대 무게이고 시작 점과 도착점이 주어졌을때, 한번에 가장많이 옮길수있는데 물품의 중량 출력 알고리즘 1.처음에는 다익스트라 알고리즘을 이용하여 이동시 드는 최소 가중치를 구하였는데 문제 의도와 는 달라서 fail. 2. 다음 블로그를 찾아보며 문제를 ..

문제 링크 : https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다� www.acmicpc.net 문제 설명 1. 처음에 해킹당하기 전에 연결된 네트워크가 주어짐. 2. 네트워크는 가중치가 있는 양방향 그래프 형식. 3. 최소의 가중치로 모든 네트워크를 연결 하기위한 간선의 갯수와 연결할 간선을 출력. 알고리즘 1. 다익스트라 알고리즘을 이용하여 통신 최소 시간 을 계속 갱신. 2. 최소 시간을 갱신하면서 따로 배열을 만들어 네트워크를 이어주는 간선 ..

퀵 정렬은 피벗이라는 기준 숫자를 정하여 기준숫자보다 작으면 왼쪽인덱스로 크면 오른쪽은덱스로 옮기는 방식으로 약간 분할정복 개념 으로 정렬을 한다. c++의 sort STL 은 퀵정렬을 사용하며 시간복잡도 O(NlogN)을 보장한다. 퀵정렬의 시간복잡도는 최악의 경우 O(N^2) 이지만 평균적으로 O(NlogN)을 보인다. 정렬 과정 밑줄친 숫자는 피벗 숫자이고 빨간색 숫자는 정렬이 완료된 숫자이다 알고리즘 1. 배열의 가장 왼쪽 에 있는 수를 피벗 으로 정함 2. 피벗기준으로 피벗보다 작은수는 왼쪽으로 큰수는 오른쪽으로 옮김 3. 피벗을 계속 갱신해주고 피벗을 이용하여 정렬한 숫자를 다시 1-2번과정을 통하여 정렬. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..

삽입 정렬은 정렬이 필요한 경우에만 알맞은 위치에 삽입하며 정렬한다. 시간복잡도는 O(N^2) 으로 버블 정렬,선택정렬과 동일하지만 일반적으로 두개의 정렬보다 더 빠르다. 진행 과정을 살펴보며 이해하자. 정렬 과정 알고리즘 1. 앞의 회색은 정렬된 배열이고 빨간색 수는 정렬 할 수이다. 2. 빨간색수를 정렬된 배열 맨뒤부터 값을 비교하며 대상 인덱스의 숫자보다 크면 앞으로 이동 3. 2번 과정을 반복하다가 더이상 이동이 없을시 정렬이 완료된것. 코드 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..

버블 정렬은 인접한 두 수를 비교하여 작은수를 앞으로 큰수를 뒤로 보내는 방법이다.(오름차순 기준) 정렬이 앞이아니라 뒤에서 부터 된다는 특징을 가진다. 시간 복잡도 : 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