지금껏 거의 2주간 배운것들을 정리해보려합니다. 장황한 설명들은 다른 좋은 학교, 교수님, 블로그글에 있으니, 단어장 정리수준으로 언제/왜 써야 되는지에 집중해서 적어보려합니다.
- Segment Tree
간략 설명: 특정한 범위를 표현하고 이를 Tree의 인덱스에 지정하고 이른 트리구조로 관리함, 각각의 인덱스에 매핑되는 값 혹은 특정한 데이터를 꺼내는 형태로 자료를 관리함. 트리는 인덱스를 기준으로 양쪽이 균등한 형태를 갖도록 구성함. 실제 노드는 배열로 구성시 배열의 인덱스와는 다름. 특정 구조체의 배열로 구현하여 사용하거나, 링크형태로 연결관계만 유지하고, 실제 데이터는 따로 담는 방법이 있겠음.
언제: 트리구조를 이용하므로, 검색시간이 O(N)->O(LogN)정도로 줄어드는 장점이 있고, 각각의 Range별 특정한 사전 연산등을 통하여, 값을 빠르게 얻을 수 있음. 대표적인 사용예를 특정구간의 합 또는 최대값을 구하는 용도로 사용. 메모리에 비교적 여유가 있다면, 각 노드에 직접 데이터를 담아서 사용하는 것이 노드 탐색시 처리할 수 있도록 하여 좋음. LIS구할때 자주 사용함. 전봇대 전선 교차 제거 문제 – 한쪽을 기준으로 소팅하고 반대쪽 연결 수열의 LIS를 찾는것이 교차되지 않는 전선들을 찾을 수 있음. 그외는 제거 대상
- TRIE
- 아이디어 또는 트릭 목록
Binary Search/Tree -> O(N) -> O(LogN)으로 전환하는 개념. 나누고 합하는 개념이 들어가고 공간상으로 넓게 퍼뜨려 시간을 절약하는 방법. MergeSort, BinarySearch, BinaryTree,
Memoization : 여러번 반복하여 상태가 변화하고 해당 상태에 따라서 다음번 결과가 바뀌는 경우, 각각의 상태의 결과를 따로 저장해두었다가 다시 사용하는 방법, 단일한 Path가닌 여러 path로 상태가 영향을 줄 경우에 유용함.
Early Determination/ Lazy Propagation: 트리등의 값 변경, 작업의 스케쥴이 여러건 들어오고, 데이터의 포맷이 같고. 당장 상태 변경이 필요치 않으며, 입력에 대한 출력만 요구하고, 출력을 100% 정확하게 사전에 예상할 수 있는 방법이 있을 경우, 그리고 차후에 상태 변경을 하여도 무방한경우 사용