자료구조

알고리즘

[백준] 22233번 가희와 키워드

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 시간 1.5초 -> 대충 (n) 2억?으로 생각했다 먼저 문제를 읽으면 최대 10개의 키워드에서 Hash_map, map, set 을 써야 하지 않을까 생각했다. 여기서는 자료구조를 생각하는게 중요한 것 같다. 글을 쓴 이후 지워진다. -> erase, remove 글에 쓴 키워들를 지우고 메모장에 얼만큼에 키워드를 출력 -> 자료구조의 size 출력하면 되겠다라..

CS/데이터베이스

[DB] 인덱스에서 B-Tree를 쓰는 이유

데이터베이스의 탐색 성능을 좌우하는 인덱스. 인덱스를 사용하는 이유? 대부분의 속도 저하는 바로 Select문 특히 조건 검색 Where절에서 발생하는데 가장 먼저 생각해 볼 수 있는 대안으로 Index가 존재 그렇다면 왜 B-Tree자료구조를 사용할까? 먼저 자료구조에서 트리란 무엇인가에 대하여 알아보자. Tree는 평균적으로 시간 복잡도 O(logN)을 가진다. 하지만 최악의 경우 한 쪽으로 쏠려버린 트리다 최악의 탐색 시간 O(N)을 가지게 되어버린다. 이걸 방지하기 위해 밸런스 트리(Balanced Tree)를 이용하기도 한다. 밸런스 트리(Balanced Tree)란? 트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸..

Sleeg
'자료구조' 태그의 글 목록