본문 바로가기

자료구조

 (3)
[자료구조] 트라이 트라이문자열을 효율적으로 탐색하는 자료구조로 O(n) 시간복잡도로 해당 문자열이 존재하는지 확인 할 수 있는 자료구조 이다.삽입, 검색, 삭제, 업데이트 : O(n) 시간이 걸린다.Node 트리구조 기반의 자료구조를 활용한다.만약 “abc123” 과 “abc12” 라는 문자열이 존재한다면 “abc12”는 같은 노드를 공유한다.삽입 :루트노드에서 자식 노드로 방문해가면서 자식노드가 존재하지 않으면 자식노드를 만들어준다.마지막 노드에 도착하면 노드에 값을 넣어준다. ( 마지막 노드인것을 판별하기위한 플래그 )삭제 :삽입과 다르게 for문이 아닌 재귀 방식으로 구현하였다.재귀방식으로 구현할경우 자식노드를 지워가면서 자식노드의 길이가 0이면 부모노드도 삭제 할 수 있다.검색 :삽입과 마찬가지로 자식노드를 방문하..
[Java] 자료구조 배열고정 크기 이상의 객체를 관리 할 수 없다.배열의 중간에 객체가 삭제되면 응용 프로그램에서 자리를 옮겨야한다.컬랙션가변 크기로 객체의 개수를 염려할 필요 없다.컬랙션 내의 한 객체가 삭제되면 컬랙션이 자동으로 자리를 옮겨준다.컬랙션을 구현한 클래스들Java.util 패키지는 컬랙션의 개념을 구현한 핵심적인 다양한 클래스를 제공한다.VectorArrayListHashTableHashMapLinkedList 등[참고] 컬랙션을 구현한 모든 클래스들은 Object를 상속받는 객체들만 요소로 받아들인다. 즉, byte, char short, int, long, float, boudle boolean 등 8 종류의 기본 타입은 원칙적으로 사용할 수 없다. Vector vs ArrayList공통점List 인터페..
느리게 갱신되는 세그먼트 트리 (Segment Tree Lazy Propagation) 개념 최대한 늦게 세그먼트 트리를 갱신시키는 방법으로, Lazy Value 값을 노드에 저장시켜놓은뒤, 노드의 방문을 필요때마다, 업데이트를 시켜준다. 쿼리나, 다른 업데이트가 필요할때, 그때 노드를 방문함으로서, 업데이트를 최대한 미루는 방식이다. Lazy Value 대상은 자식노드들이 모두 업데이트가 필요할 경우이다. 모든 자식노드가 업데이트가 필요할경우 해당 부모노드에서 자식노드까지의 방문을 멈추고, 해당 부모노드에 Lazy Value 값을 갱신시킨다. 추후 나중에 필요할때 Lazy Value 값을 적용 자식들에게 가중치를 전파한다. 가령, 원소는 (0, 9)가 존재한다고 하고, (3, 7)구간을 업데이트 한다고 가정한다. 빨간색과, 흰색을 제외한 부분은 다 업데이트를 해야하는 부분이며, 하늘색 부..

티스토리툴바