본문 바로가기

수열과 쿼리2

머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 머지 소트 트리를 이용한 백준 문제 풀이 수열과 쿼리 1 , 수열과 쿼리 3 , 트리와 색깔 , K번째 수 는 맨 아래를 참고해주세요. 코드 스포일러를 방지하기 위해 접은 글로 풀이를 남겼습니다. 알고리즘에서 c++의 algorithm 헤더에 있는 내장 sort함수는 코드의 간결성과 실수를 줄여줍니다. 그러나, 내장함수가 있다고해서 정렬 알고리즘을 구현할줄 몰라도 되는 것은 아닙니다. 아래의 버블 소트는 알고리즘 입문자들이 대부분 알고있는 정렬 알고리즘으로 O(N^2)의 비효율적인 복잡도로 작업을 수행합니다. 모든 수를 비교하면서 큰 수를 뒤로 보내는 단순한 방식으로 동작합니다. // 버블 소트 for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) {.. 2020. 8. 17.
[BOJ] 백준 13537번: 수열과 쿼리 1 머지 소트 트리 + 이분탐색 아래글 참고. 2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m, k; int arr[100001]; int mst[17][100002] = { 0, }; void make_tree(int s, int e,int depth) { if (s == e) { mst[depth][s] = arr[s]; } else { int mid = (s + e) / 2; make_tree(s, mid, depth + 1); make_tree(mid + 1, e, de.. 2020. 6. 22.

티스토리툴바