반응형 전체 글162 Tree Structure 노트10 - Suffix Tree Search Tree 구성의 종류 - key 전체를 비교하는 방법 / key의 일부를 비교하는 방법 / 각 node마다 동일한 기준으로 비교하는 방법 / 각 node마다 비교하는 기준이 다른 경우 Trie 구조가 필요한 Text Application의 전형적인 예) - Dictionary : memory를 작게 만드는 것이 중요한 작업 - 자동차 네비게이션에서 주소 찾기 or 우편번호 주소 찾기 Digital Search Tree - key 값을 binary로 바꿔서 각 level마다 비교대상을 다르게 함. - level i node에서 볼때 왼쪽 subtree의 모든 값은 i번쨰 bit = 0, 오른쪽 subtree의 i번째 bit = 1 Trie는 기본적으로 multi-way branch tree. .. 2022. 4. 14. 디자인 패턴 - Template Method pattern Template Method pattern : 객체가 실행해야 하는 알고리즘 기본 골격을 추상(부모)클래스에 구현해 놓은 후 서브클래스에서 메소드를 override하여 객체가 수행해야 할 행위의 다양성을 표현하는 방법. ==> 객체지향 프로그래밍 시에 생활화해야 되는 코딩 스타일 / 어떤 작업을 처리하는 일부분을 서브 클래스로 캡슐화하여 전체 일을 수행하는 구조는 바꾸지 않으면서 특정 단계에서 수행하는 내역을 바꾸는 패턴. / 상속을 통해 슈퍼클래스의 기능을 확장할 때 사용하는 가장 대표적인 방법. 변하지 않는 기능은 슈퍼클래스에 만들어두고 자주 변경되며 확장할 기능은 서브클래스에서 만들도록 함. - 전체적으로는 동일하면서 부분적으로는 다른 구문으로 구성된 메서드의 코드 중복을 최소화할때 유용함. - 동.. 2022. 4. 12. 디자인 패턴 - Iterator pattern Iterator pattern은 collection 객체의 element들을 traverse하기 위한 기능을 collection 객체와 독립적으로 구현하는 방법. (=객체 지향 프로그래밍에서 iterator를 사용하여 container를 가로지르며 요소들에 접근하는 패턴.) 컬렉션 객체 - 배열, ArrayList, Stack, LinkedList, HashMap등 라이브러리에 있는 Iterator 객체를 구현하는 예제 특징 : Iterator 패턴은 container로부터 알고리즘을 분리시키며, 일부의 경우 알고리즘들은 필수적으로 container에 특화되어 있기 때문에 분리가 불가능하다함. / 유연하고 재사용 가능한 객체지향 소프트웨어를 설계하기 위해 반복되는 디자인 문제를 해결하는 방법. Itera.. 2022. 4. 12. 디자인 패턴 - Facade pattern Facade pattern : facade(건물의 정면) / 특정 서브 시스템에 소속된 여러개의 객체를 액세스하기 위한 통합된 접근 경로를 제공하는 방법. adapter pattern과 facade 이 두개의 패턴은 이질적인 시스템을 연결하는 효과를 제공함. Facade pattern은 클래스 라이브러리 같은 어떤 소프트웨어의 다른 커다란 코드 부분에 대한 간략화된 인터페이스를 제공하는 객체. / facade는 소프트웨어 라이브러리를 쉽게 사용할 수 있게 해줌(공통적인 작업에 대해 간편한 메소드들을 제공해줌). / facade는 라이브러리 바깥쪽의 코드가 라이브러리의 안쪽 코드에 의존하는 일을 감소시켜줌. 대부분의 바깥쪽의 코드가 facade를 이용하기 때문에 시스템을 개발하는데 있어 유연성이 향상됨. .. 2022. 4. 12. Tree Structure 노트9 - Trie 탐색 트리 트라이 문자열 탐색을 위한 Trie(Prefix tree) 내용이 있다는 것과 그것이 '인식될 수 있는 형식'으로 표현된 것은 다르다. 주소 시스템 같이 내용이 많은걸 할때 씀. 휴대 전화에서 쓰이는 것 같은 예측 문자나 자동 완성에 필요한 사전을 저장하는 것들도 일반적인 응용중 하나/ 주로 문자열이 key인 경우가 많음./ 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. Trie의 장단점 : ㆍ트라이는 문자열 검색이 빠름. ㆍ문자열 탐색시, 하나하나 모두 비교하면서 탐색을 하는 것 보다 시간 복잡도 측면에서 훨씬 효율적임. ㆍ각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음. 구현.. 2022. 4. 11. Tree Structure 노트8 - Red-Black Tree Dynamic Operation을 위한 다양한 트리 자료구조가 있을 때, 사람들(coder)가 이해하기 좋은 구조와 사람에게는 어렵지만 컴퓨터에서 효율적으로 동작하는 구조 중 어느것이 좋은가? Dynamic Tree Structure를 선택하는 기준 - Tree기반의 자료구조(Splay Tree, Min-max Tree, Split Tree, Leftist Tree..)/ 얼마나 많은 데이터를 처리해야 하는가?/ inserting이 자주 일어나는가 그리고 이 작업이 연속적인가?/ on-memory에서 효율적으로 동작하는가? 아니면 disk를 사용하는가? Red-Black Tree는 복잡한 자료구조지만, 실사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행시간을 보임(worst-case guarant.. 2022. 4. 11. 이전 1 ··· 22 23 24 25 26 27 다음 반응형