230526 Today I Learned

스프링 면접 대비 질문을 이어서 정리했다.

13. 인덱스란 무엇이고 원리에 대해 설명해주세요

인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조입니다. 인덱스는 특정 칼럼에 대한 key-value 쌍으로 구성되며, 키는 검색 조건에 사용되는 값이고 value은 해당 키가 가리키는 데이터의 위치입니다. DBMS에서 인덱스를 생성하면, 인덱스 구조가 열의 값을 키로 사용하여 정렬된 형태로 생성됩니다. 데이터를 검색할 때, DBMS는 인덱스를 사용하여 검색 조건에 해당하는 키를 찾습니다. 이를 통해 실제 데이터를 순차적으로 검색하는 것보다 빠르게 원하는 데이터를 찾을 수 있습니다.

14. 이분탐색에 대해 설명하고 시간복잡도를 알려주세요

이분탐색은 정렬 되어 있는 자료에서 사용할 수 있는 알고리즘으로 시간복잡도는 O(log N) 입니다. 정렬된 자료구조에서 중간에 있는 요소와 찾을 요소의 값을 비교하고 크다면 그보다 오른쪽을 탐색하고 작다면 왼쪽을 탐색하는 방식입니다. 이분 탐색은 탐색 범위를 반으로 줄이는 특성 때문에 데이터의 크기가 두 배로 증가할 때마다 탐색 시도 횟수가 1회 증가합니다. 따라서 시간복잡도가 O(log N)입니다. 하지만 정렬되어 있는 자료에서만 사용할수 있다는 단점이 있습니다.

15. 트리와 그래프를 비교해서 설명해주세요

트리와 그래프는 노드와 노드를 연결하는 간선으로 구성되어 데이터간의 관계를 표현하는 자료구조입니다. 트리는 하나의 루트 노드에서 시작하여 다양한 자식 노드들로 확장되는 계층적인 구조입니다. 각 노드는 부모-자식 관계로 연결되어 있으며, 각 노드는 하나의 부모 노드를 가집니다. 부모에서 자식으로 방향성을 가지고 있고, 순환구조를 가지지 않습니다.
그래프는 여러 개의 노드들이 임의로 연결된 비선형 구조입니다. 방향성이 있을수도 있고, 없을수도 있으며, 순환구조를 가질 수 있습니다.