제이슨의 개발이야기

AVL 트리 란 무엇인가? AVL 트리( Adelson-Velsky and Landis tree) 는 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진트리 입니다 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있습니다 AVL 트리는 탐색,삽입,삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡습니다 레드 블랙 트리란 무엇인가? 레드 블랙 트리는 균형 이진 탐색 트리로 탐색 , 삽입 , 삭제 모두 시간 복잡도가 O(logn)입니다 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 , 삽입 및 삭제 중에 트리가 균형을 유지하도록 ..

안녕하세요 제가 요즘 면접 준비하고 있어서 자료구조 관련 면접 질문 대비를 해보려구 합니다! 1. 시간 복잡도 란? 시간복잡도는 이 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값 2. 공간 복잡도 란? 공간복잡도는 이 알고리즘이 결과를 도출하는데 얼마나의 공간이 필요한 지에 대한 값 3. 연결리스트에 대해서 설명하기 { 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조 입니다. 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸립니다 연결 리스트에는 3종류가 있는대 1. 싱글 연결 리스트 : 다음 노드의 주소만 가지고 있다 2. 이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있고 가장 첫번째 노드의 이전 주소값은 null 마..

Heap 자료 구조 란 무엇일까? 아마 첨 들어 본 사람도 있을 거고 공부 했지만 시간이 지나면서 "어? heap이 머였지?" 라는 사람들도 있을거라고 생각합니다 왜냐하면 stack 이나 queue , tree 등은 한번 배우면 까먹기 쉽지 않은 자료 구조 지만 heap 같은 경우 tree 의 구조를 응용한 자료 구조 이므로 까먹거나 햇갈릴 수 도 있는 자료구조라고 생각합니다 heap 이란 우선순위 큐를 구현하기 위한 자료구조 로써 완전 이진 트리 로 이루어 저 있는 자료구조입니다 힙의 종류로는 최대 힙(max heap) 와 최소 힙(min heap)이 있습니다 힙은 배열로 구현 하는 것이 가장 효과적이다 ! 먼저 최대 힙(max heap)은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 ..