boj, 백준) 9426. 중앙값 찾기 ( C++ )
1. 문제 링크 www.acmicpc.net/problem/9426 9426번: 중앙값 측정 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N) 둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다. www.acmicpc.net 2. 문제 개요 주어진 데이터의 부분 수열의 중앙값을 찾아 모두 합을 구하는 프로그램을 만드시오. 3. 문제 힌트 세그먼트 트리를 사용해보자. 매번 정렬하여 중간값을 꺼내는 방식이나, merge sort처럼 각 세그먼트 트리에 정렬된 값을 갖고 올라가는 것은 O(NK)로 시간이 아슬아슬할 것 같다. 뭔가,, 공간 복잡도를 희생해서 시간 복잡도를 줄일 수 있는 방..
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, 백준) 2357. 최솟값과 최댓값 (C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 www.acmicpc.net 2. 문제 개요 1~100,000개의 정수들이 있을 때 [a, b] 구간의 최솟값과 최댓값을 1~100,000번 찾..