백준/세그먼트 트리 (27) 썸네일형 리스트형 [ICPC] 백준 7469 - K번째 수 https://www.acmicpc.net/problem/7469 수열의 부분 구간에서 연산을 하는 것은 머지 소트 트리로 처리할 수 있다. 머지 소트 트리를 구현한 후 이진 탐색을 이용하여 구간의 k번째 원소를 찾아주면 된다. 전체 코드 - query 함수에서 lower_bound를 사용했으므로 kth - 1을 pivot으로 삼은 것에 유의하라. 더보기 #include using namespace std; int n, m; vector mst[400000]; int ar[100001]; inline int mid(int s, int e) { return s + (e - s) / 2; } void set_mst(int node, int start, int end) { vector &cur = mst[no.. [ICPC] 백준 9463 - 순열 그래프 https://www.acmicpc.net/problem/9463 각 편에서 번호가 같은 정점끼리 연결했을 때 생기는 교차점으로 순열 그래프를 구성한다고 한다. 우리는 교차점의 개수를 구해야 되므로 문제에서 첫번째 그림을 보고 3770번 문제와 같은 흐름으로 inversion counting을 생각할 수 있다. 다만 이 문제는 주어진 입력에서 번호가 같은 정점끼리 연결하는 것이므로 이를 적절히 변환해줄 필요가 있다. 주어지는 첫번째 노드 집합을 index에 매칭하여 각 숫자가 어느 index에 대응하는지 배열로 저장한다.(mp[val] = idx) 두번째 노드집합에서는 index와 첫번재 mp배열에서 해당 노드 숫자의 index를 가져와 pair로 짝지어서 배열이나 선형 자료구조에 저장한다. 그렇게 되면.. [ICPC] 백준 3770 - 대한민국 https://www.acmicpc.net/problem/3770 문제 분석 두 고속도로가 하나의 교차점을 만들수 있을 때(세 개 이상의 고속도로가 만나면 안된다.) 교차점의 개수를 구하는 문제이다. 서쪽의 정점들을 pivot으로 하여 오름차순 정렬하면 다음과 같이 그릴 수 있다. 여기서 동쪽의 정점을 index, 서쪽으로 연결된 정점을 value라고 하자. 그렇다면 어떤 index의 value가 1 ~ index - 1 범위의 value와 비교했을 때 index의 value가 더 작다면 교차한다는 사실을 관찰할 수 있다. 이는 어떤 index의 value가 index + 1 ~ end 범위의 value와 비교했을 때 index의 value가 더 크다면 교차한다는 것과 동치가 된다. 하나의 교차점은 오직.. 백준 9426 - 중앙값 측정 https://www.acmicpc.net/problem/9426 지문의 힌트에서 (K + 1) / 2번째로 작은 숫자를 찾으면 된다고 알려주고 있다. 세그먼트 트리를 통해 (K + 1) / 2번째로 작은 숫자를 찾는 연산을 구현하면 간단히 해결할 수 있다. 중앙값을 구하는 구간의 길이는 K라고 명시하고 있으므로 슬라이딩 윈도우를 통해 구간을 벗어나는 원소나 구간에 속한 원소만을 update 연산으로 세그먼트 트리에 반영해주면 된다. 전체 코드 더보기 #include using namespace std; int n, k; inline int mid(int s, int e) { return s + (e - s) / 2; } void update(vector &tree, int node, int start,.. 백준 1777 - 순열 복원 https://www.acmicpc.net/problem/1777 ICPC 문제 Permutation Recovery와 거의 비슷한 문제이며 하이퍼링크에서 풀이를 확인할 수 있다. 다만 이 문제는 위와는 다르게 i 이전의 index에서 자기보다 큰 숫자를 세는 것이 아니라 i 이후의 index에서 자기보다 큰 숫자를 세는 것이다. 입력으로 들어온 수열을 거꾸로 하여 위와 같은 풀이를 적용하면 해결할 수 있다. 전체 코드 더보기 #include using namespace std; int n; int seq[100001]; int ar[100001]; inline int mid(int stt, int end) { return stt + (end - stt) / 2; } int init(vector &tre.. 이전 1 2 3 4 5 6 다음
