-

# 주소 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net htt..

배열이 정열되어 있다는 것은 수학적으로 단조증가 수열이라는 것과 동치입니다. 즉, x0 < x1 < ... < xn이 있을 때 어떤 값 xk를 뽑고 그 값이 내가 찾는 값보다 크다면 xk, xk+1, ... , xn-1역시 원하는 값보다 클 것입니다. 그렇다면 굳이 이 값들은 탐색할 필요가 없으므로 과감하게 제거합니다. 반대로 내가 찾는 값보다 작을 경우 x0, x1, .... , xk는 탐색할 필요가 없습니다. public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자 Arrays.sort(arr); // 정렬 int start = 0; // 시작 int end = arr[arr.length-1]; // 끝 while(start mid) sum+..

이번 시간에는 스택과 큐에 대해 정리해보았습니다. 1. 스택(STACK) 여러 의미로 사용되는 스택은 자료구조에서는 무언가를 쌓는다라는 의미를 갖는 자료구조입니다. 후입선출(後入先出, Last In First Out; LIFO)의 자료구조라고도 불리우며 QUEUE와 달리 먼저 들어온 것이 먼저 나가는 용도로 쓰입니다. 스택은 입력은 push, 제거는 pop을 이용합니다. peek는 Top의 위치에 있는 데이터를 확인하는 것이므로 스택으로 데이터를 쌓아 올렸을 때 peek를 사용하면 가장 마지막에 삽입한 데이터가 출력되게 됩니다. 즉 쉽게 말해 스택은 일종의 바닥이 막힌 상자라고 볼 수 있습니다. 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수밖에 없다고 생각하시면 되겠습니다. 스택은 힙 영역 메모리에서 ..

이번 시간에는 삽입 정렬에 대해 알아보겠습니다. 알고리즘에는 많은 유형이 있지만 주로 탐색과 정렬하는 것들이 많습니다. 탐색을 하기 전에는 미리 정렬을 해야 합니다. 정렬된 자료를 탐색하는 강력한 알고리즘이 있거든요. 정렬하는 방법도 여러가지가 있습니다. 그 중에 오늘은 삽입 정렬 차례입니다. 삽입 정렬이란 여러 개의 섞인 숫자가 있을 때, 그 숫자를 작은 순서부터 큰 순서로 정렬하는 겁니다. 삽입 정렬은 첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣습니다. 세 번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣습니다. 이렇게 끝까지 계속하면 정렬됩니다. 쉽게 설명하자면 오른손에 쥔 정렬되지 않은 카드를 왼손에 ..

이번 시간에는 시간의 복잡도를 설명하겠습니다. 시간의 복잡도는 알고리즘을 수행하는 데 평균적으로, 또는 최악의 경우 얼마만큼의 시간이 걸리는 지 보여줍니다. 반대의 개념으로 공간의 복잡도도 있는데, 알고리즘이 얼마만큼의 메모리를 잡아먹는 지 보여줍니다. 공간의 복잡도는 알고리즘을 짜는데 있어 크게 고려하는 부분이 아닌데다가 보통은 시간의 복잡도를 더 중요하게 여기기 때문에 시간의 복잡도를 주로 다루겠습니다. 그리고 그냥 복잡도라고 해도 시간의 복잡도라고 생각하시면 편할 것 같습니다. 복잡도를 계산하는 과정은 정말 어려우니 여기서는 생략하겠습니다. 대학교에서 배우는데 학원에서는 가르쳐주지 않습니다. 우리는 간단히 복잡도를 표시하는 방법과 그것이 시사하는 바를 알아보려고 합니다. 복잡도는 주로 빅오 표기법을..