boj,백준) 9345. 디지털 비디오 디스크(DVDs) ( C++)
1. 문제 링크 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 2. 문제 개요 N개의 DVD가 0번부터 N-1번까지 정리되어 있다. 그런데 나쁜 손님이 와서 A번 DVD과 B번 DVD의 위치를 바꾼다. 착한 손님이 L번부터 R번까지의 DVD를 빌리려고 할 때, DVD를 자세히 보지 않고 L번째부터 R번째까지 그냥 통째로 가져간다. 이때, [L, R] 범위에 진짜 L~R번의 DVD가 모두 포함되어 있..
boj, 백준) 13537. 수열과 쿼리1 (C++)
1. 문제 링크 https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 2. 문제 개요 길이가 N인 수열 A1, A2,..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 i j k : Ai , Ai+1,..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. 3. 문제 풀이 시간복잡도를 분석해보자 그냥 단순하게 매 번 탐색을 한다고 가정하면, 구간 최대O(N), 횟수 O(..
boj, 백준) 2517. 달리기 (C++)
1. 문제 링크 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 �� www.acmicpc.net 2. 문제 개요 요약하자면, 평소 실력이 정수로 주어진다. 반환점을 돌고 일렬로 선 상태에서, 실력이 앞서 있는 사람보다 높다면 앞질러 도착할 수 있다. 이때 최선의 등수를 계산하는 프로그램을 작성하시오. 3. 문제 힌트 N이 최대 50만이기 때문에, O(n^2)을 사용하면 안 됨. O(nlogn)으로 구할 수 있는 경우를 찾아보자. 즉, 모든 숫자에 대해서 탐색을 해야..
boj, 백준) 10254. 고속도로 (C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/10254 10254번: 고속도로 문제 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 �� www.acmicpc.net 2. 문제 개요 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 도시의 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾는 프로그램을 작성하시오. 3. 문제 힌트 그냥 Brute Force로 푼다면 이문제는 O(n^2) 시간 내에 풀 수 있다. 하지만 N이 20만이다. 그래서 O(nlo..
boj, 백준) 13263. 나무자르기 , Convex hull trick ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족�� www.acmicpc.net 2. 문제 개요 높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다. i번 나무에 전기톱을 사용할 때마다, 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자..
boj, 백준) 2699. 격자점 컨벡스헐 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/2699 2699번: 격자점 컨벡스헐 문제 정수좌표를 갖는 점을 격자점이라고 한다. 격자 다각형은 모든 꼭짓점이 격자점으로 이루어진 다각형이다. 만약, 다각형의 두 꼭짓점을 잇는 모든 선분이 다각형 내부(또는 경계)에 있다면 www.acmicpc.net 2. 문제 개요 좌표가 주어지고 컨벡스 헐을 이루는 점의 개수, 좌표(x, y) 순서를 조건에 맞는 순서대로 출력할 것. 조건은 1. 첫 번째 곡짓점은 y좌표가 가장 큰 점이다. 만약, 그러한 점이 2개라면, x가 작은 점이 첫 번째 점이다. 2. 그 다음 점부터는 시계방향 순서이다. 3. 문제 힌트 평소에 알고 있는 컨벡스 헐 알고리즘인 그라함 스캔 알고리즘은 y좌표가 가장 작고 ..