리프노드 썸네일형 리스트형 BOJ(백준) 3653 - 영화 수집 ★ 아이디어처음에 query를 이용해서 간단히 구간합을 뽑을 수는 있는데, 그 이후가 쉽지 않다. DVD를 뽑아서 맨 위로 올리는 것을 어떤 식으로 표현할 것인가?? 처음에는 또 인덱스 및 구간에다가 합을 부여하고 싶다. lazy propergation 같은 아이디어가 떠올랐는데, 그때마다 항상 0과 1, 리프노드를 잘 활용하는 아이디어가 필요했다. 세그먼트트리의 리프를 N + M만큼으로 구성하는 아이디어가 필요하다. N = 8, M = 3이면 0 0 0 1 2 3 4 5 6 7 8 더보기 BOJ(백준) 3006 - 터보소트 ★ 아이디어index자체를 바꾸려면 시간이 엄청 걸린다. 구간에다가 합을 부여하고 싶은 생각이 든다. lazy propergation이 떠오르긴 하는데, 그것말고 또 다른 아이디어가 있을까 찾다가, 바꾸는 횟수를 카운트 = 리프노드가 1인 세그먼트트리로 구간합을 구하는 아이디어 이것을 떠올리면 간단해진다. https://github.com/jongwuner/Algorithm/blob/master/BOJ/3006.cpp 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include#include#includeusing namespace std;typedef pair Pair;int N, segSize .. 더보기 BOJ(백준) 1068 - 트리 https://www.acmicpc.net/problem/1068 자료구조(트리), 리프노드, 차수, 트리 방향성루트 있는 트리가 주어지고, 각 노드들의 부모노드가 주어진다. 어떤 한 노드를 제거 했을 때, 남는 리프노드(단말노드)의 개수를 구하는 프로그램을 작성하라. 시간복잡도 : O(N) N은 트리 노드의 개수 점검해봐야 할 부분-루트가 있는 트리의 방향성-리프 노드의 성질 https://github.com/jongwuner/Algorithm/blob/master/BOJ/1068.cpp 1234567891011121314151617181920212223#includeint p[50], a, c[50];int main(){ int n, d; scanf("%d", &n); for (int i = 0; i.. 더보기 이전 1 다음
