인덱스 썸네일형 리스트형 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(백준) 1280 - 나무심기 ★ 아이디어 일단 좌표의 범위가 (2 더보기 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(백준) 11003 - 최솟값 찾기 아이디어 처음엔 보자마자 세그먼트트리를 떠올렸었다. 근데 세그먼트트리의 연산은 갱신과 질의인데, 질의만 사용할 거면 굳이 쓸 필요가 없다고 생각했다. 그리고 세그먼트트리 시간복잡도를 고려했을 때, 세그먼트트리 생성과 연산의 시간때문에 시간초과가 날 우려가 있다고 생각해서, 다른 자료구조와 알고리즘을 고민했다. 스택, 큐, 우선순위 큐는 삽입이 되면 일단 삽입되어있는 내부에 대해서 순서를 알 수 없기 때문에, 자주 활용하는 pair에다가 인덱스(index)를 담아서 삽입하는 아이디어가 있다. 그것을 활용해서, 선형자료구조를 검색하면서 선형자료구조의 인덱스를 체크하는 동시에 우선순위큐의 삽입과 삭제를 활용하면 문제는 쉬워질 것 같았다. 점검해볼 사항- 자료구조에 저장하고 있는 자료. pair- 인덱스 활용-.. 더보기 이전 1 다음
