https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net 노드에 해당 구간에 정렬된 값들이 저장되는 머지 소트 트리를 만들고 특정 구간에서 어떤 숫자 이하의 개수가 몇 개인지 구하는 쿼리를 만들어 이분 탐색을 통해 문제를 해결했다. 코드 #include #include #include using namespace std; int n, m; vector inputs(100001, 0); vector mgstt[400004]; //머지소트트리 vector::it..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이분 탐색으로 문제를 해결했다. 각 행마다 확인하는 수 보다 작은 수가 몇 개 있는지 개수를 구해서 이분 탐색을 진행했다. 코드 #include #include #include #include using namespace std; int n; int k; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); c..