boj, 백준) 2336. 굉장한 학생( C++)
1. 문제 링크 https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 2. 문제 개요 어떤 학생 x보다 시험 3개의 성적이 높은 학생 y가 있다면, 학생 y는 x보다 대단하다고 한다. 어떤 학생 y보다 대단한 학생이 없으면 학생 y는 굉장하다고 한다. 굉장한 학생의 수를 구하는 프로그램을 작성하시오. 3. 문제 풀이 문제 힌트 없이 바로 풀이로 넘어가겠다. 이 부분은 다른 블로그에도 풀이가 많다. 하지만 모두 똑같이 생각하듯이, 글로 설명되어있어서 이해가 잘..
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만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자..