트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 문자열 집합 S={"BE", "BET", "BUS", "TEA", "TEN" }를 저장하는 트리의 예는 아래와 같습니다. 여기서 진한 노드들은 종료 노드들로 해당 위치에 대응되는 문자열이 트라이가 집합에 표현되어 있다는 것을 의미합니다. BE, BET 등을 나타내는 노드들은 종료 노드지만 TE의 경우에는 그렇지 않습니다. 트라이에서 중요한 점은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있습니다. 즉 각 노드별로 대응되는 문자열을 저장할 필요가 없습니다. 트라이의 한 노드는 자손 노드들을 가리키는 포인터 목록과 이 노드..

KMP 알고리즘을 배우기전 엄청 큰 문자열 더미에서 특정 문자열을 찾기 위해서는 아래와 같이 O(N*H)의 시간복잡도를 사용하여 찾았을 것이다. N은 찾을려는 문자열 H는 문자열 더미이다. for(int begin = 0; begin + N.size()

PostgreSQL 고급 쿼리와 실행 코드 및 룰 이전 글에서 CRUD, Join, 인덱싱에 대해 공부해봤다. 이번 글에서는 데이터를 쿼리할 수 있는 여러 가지 방법에 대해 더 깊게 알아볼 것이다. 집계 함수 집계 쿼리는 주이진 기준에 맞추어 여러 행들은 그룹으로 분류한다. 그 결과는 행들의 개수, 숫자 타입 열들의 평균등이 된다. 공부하기에 앞서 events 테이블에 데이터 하나를 추가한다. 서브쿼리 insert를 진행할 때 서브쿼리를 사용하면 venue_id를 일일이 찾지 않아도 된다. INSERT INTO events (title, starts, ends, venue_id) VALUES('Moby', '2012-02-06 21:00', '2012-02-06 23:00', (SELECT venue_i..

세븐 데이터 베이스를 읽고(3) Postgres 설치 및 CRUD, Join mac 설치 # 설치 brew install postgresql # 서비스 시작 pg_ctl -D /usr/local/var/postgres start export PGDATA='/usr/local/var/postgres' # 실행 확인 pg_ctl status # 버전확인 postgres -V 기능 확장 #스키마 생성 createdb book # postgres에 접속 psql book # 접속 후 기능확장하기 CREATE EXTENSION tablefunc; CREATE EXTENSION dict_xsyn; CREATE EXTENSION fuzzystrmatch; CREATE EXTENSION pg_trgm; CREATE E..

[데이터베이스/세븐 데이터 베이스를 읽고] - (1)세븐 데이터 베이스를 읽고 - 이 책을 통해 배울 내용. (1)세븐 데이터 베이스를 읽고 - 이 책을 통해 배울 내용. (1)세븐 데이터 베이스를 읽고 - 이 책을 통해 배울 내용 http://www.yes24.com/Product/Goods/8595403 세븐 데이터베이스 7개 데이터베이스의 매력적인 기능과 완벽한 쓰임새를 소개한다! 이 책에서는 PostgreSQ hoony-gunputer.tistory.com 이전 글에서 배울 데이터 베이스 종류에 관계형, 문서형, 키-value형, 칼럼형 등을 언급했다. 각 트징을 알아보고 어떤 상황에서 사용하면 좋을지 정리해보겠습니다. 관계형(RDBMS) 일반적으로 많이 사용하는 모델이다. 관계형 데이터베이스 관..

(1)세븐 데이터 베이스를 읽고 - 이 책을 통해 배울 내용 http://www.yes24.com/Product/Goods/8595403 세븐 데이터베이스 7개 데이터베이스의 매력적인 기능과 완벽한 쓰임새를 소개한다! 이 책에서는 PostgreSQL, Riak, HBase, MongoDB, CouchDB, Neo4J, Redis의 7개 데이터베이스들의 핵심 개념과 기능을 구체적으로 소개한다. 또한 www.yes24.com 개발자라면 데이터 베이스를 정말 많이 사용하게 될 것입니다. 예를 들어 mysql, mongodb, mariadb, postgres 등등이 있습니다. 하지만 필자의 경우 어떤 상황에서 어떤 데이터베이스를 선택할지 별다른 고민없이 이번에는 저걸써볼까 아니면 이번에는 저걸 써볼까 생각하여 ..