게으른 개발자

이분 탐색(Binary search) 이분 탐색을 사용할 때는 반드시 오름차순으로 정렬이 되어있어야 합니다! 이분 탐색은 이름처럼 주어진 범위를 반으로 나눠가면서 탐색하는 방법이다. 1~n까지 수 또는 리스트에서 특정 수 a를 찾는다고 하면 우리는 1~n까지 모두 탐색하여 x가 있는지 찾는 방법이 있다. 이 방법은 시간 복잡도 O(n)으로 n이 커질수록 x값을 찾는데 시간이 오래 걸린다. 이때 시간 복잡도를 O(logn)으로 줄여 탐색할 수 있는 방법이 바로 이분 탐색이다. 알고리즘 1. 탐색하고자 하는 값의 범위 또는 리스트에 중복되는 값이 없는 경우 index 0 1 2 3 4 5 6 7 8 value 0 1 2 3 4 5 6 7 8 이분 탐색은 left, right로 mid값을 구하고, mid값을 ..

문제 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 문제 요약 기차는 한대의 기관차와 여러 대의 객차로 구성되어있다. 만약 운행 중 기관차가 고장 난 다면 다른 기관차가 와서 객차를 끌고 목적지까지 운행해야 한다. 철도청에서는 기관차가 고장 날것을 대비해 k개의 객차만 끌 수 있는 소형 기관차 3대를 배치했다. 총 n개의 객차가 있을 때 3대의 소형 기관차가 가장 많은 인원을 데리고 목적지까지 도착할 수 있는 방법을 찾아야 한다. k개의..

문제 https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 문제 설명 강의실 문제는 N개의 강의 인덱스(idx), 강의 시작시간(s), 강의 종료시간(e)이 차례로 주어진다. 이때 주어진 강의를 모두 열고자 할 때 필요한 최소 강의실 수를 구한다. 풀이 두개의 heapq를 사용하여 풀이했다. 먼저 강의 정보를 입력받으면서 heapq를 사용하여 강의 시작시간을 기준으로 오름차순 정렬한다. 그리고 강의 시작시간이 빠른 순서대로 강의실을 배..

문제 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 설명 Two dots게임은 같은 색을 가진 노드를 이어서 사이클을 만드는 게임이다. 게임판의 크기는 최대 50 x 50이며 각 노드는 알파벳으로 주어진다. 즉 알파벳이 같다면 같은 색으로 간주한다. 주어진 게임판에서 사이클이 존재하면 Yes를, 존재하지 않으면 No를 출력한다. 문제 풀이 dfs로 풀이할 수 있다. 먼저 (0, 0)부터 (n-1, n-1)까지 dfs로 탐색하면서..

문제 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 요약 순회강연 문제는 여러 대학에서 강연 제의를 받은 학자가 가장 많은 돈을 받을 수 있는 일정으로 강연을 하고자 한다. 강연 데드라인과 강연료가 주어지며 강연 데드라인 안에만 강연을 해주면 강연료를 받을 수 있다. 이때 학자가 가장 많이 받을 수 있는 강연료를 출력하는 문제이다. 기간 내에 가능한 강연을 선택할 수 있다는 것은 기간이 20일이라면, ..

문제 https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 문제 요약 군사 이동 문제는 그래프가 주어지고 특정노드 A에서 노드 B로 이동이 가능한 최대 경로 중에서 최소 비용이 드는 경로(엣지)를 찾는 문제이다.(문제에서는 "경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택한다" 라고 되어있어서 이해가 잘 되지 않았다.) 예를 들어 위와 같은 그래프가 있을 때 노드 1에서 ..

문제 https://www.acmicpc.net/problem/13397 13397번: 구간 나누기 2 첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N) 둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수 www.acmicpc.net 문제 설명 구간 나누기 나눌 구간 k와 숫자로 구성된 배열이 주어진다. 주어진 배열에서 k개의 구간으로 나누어 각 구간의 최댓값과 최솟값의 차이를 구해 각 구간의 값 중 최댓값이 최솟값이 되는 경우를 찾는 문제이다. 문제에서 주어진 예제 1번은 아래 그림과 같이 구간을 나누었다고 가정해 보자. 위 그림에서 2번째 줄은 주어진 배열이며, 3번째 줄은 나누어..

문제 https://www.acmicpc.net/problem/5624 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net 문제 요약 좋은 수 문제는 주어진 숫자들 중에서 i번째 수 보다 앞에 있는 수 3개를 더해 i번째 수를 만들 수 있다면 i번째 수를 좋은 수라고 한다. 즉, a + b + c = d를 만족하는 d가 몇 개인지를 구하는 문제이다. d보다 앞에 있는 수 중 3개를 뽑는 조합을 모두 구하려면 O(N^3)으로 주어진 문제의 N의 개수가 5000으로 시간 초과가 발생한다. 따라서 수식을 a ..