문제오늘도 서준이는 퀵 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 퀵 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 교환되는 수를 구해서 우리 서준이를 도와주자.크기가 N인 배열에 대한 퀵 정렬 의사 코드는 다음과 같다.quick_sort(A[p..r]) {# A[p..r]을 오름차순 정렬한다.if (p A[j];# i값 증가 후 A[i] A[j] 교환 if (i + 1 != r) then A[i + 1] A[r];# i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환 return i + 1;}입력첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000..

문제수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)출력A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.문제 해석정렬이 이뤄진 후의 특정 값의 위치를 찾아내는 문제이다.문제에서 요구 사항은 N 부터 5백만 사이의 값을 찾는 것이다.입력 크기가 엄청 크다 그런데 이런 문제에서 모두 정렬해서 위치의 값을 찾으면 상당히 비효율적이기 떄문에 퀵 정렬을 처음에 고려했지만 모든 데이터를 정렬할 필요가 없다는 생각이 들었다.다른 사람들은 QuickSele..

문제버블 소트 알고리즘을 다음과 같이 C++로 작성했다.bool changed = false;for (int i=1; i A[j+1]) { changed = true; swap(A[j], A[j+1]); } } if (changed == false) { cout 위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.입력첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0..

문제크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,00..

문제N개의 수 A1, A2, ..., AN과 L이 주어진다.Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.입력첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)출력첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.문제해석특정 범위 안에서의 최소값을 찾아야 하므로, 이 문제는 슬라이딩 윈도우 문제라고 볼 수 있다.윈도우 크기만큼 범위를 잘라내어 그 안에서 최소값을 구하면 되며,매번 정렬을 통해 구하는 방식은 비효율적이므로, 덱(Deque)을 활용하여 정렬된 것처럼 유지하면서 문제를 해결해보겠다...