공부 하면서 계속 업데이트 예정입니다.
큰 틀의 질문에 대한 답변을 공부하며, 해당 질문에 대한 꼬리질문을 공부해나갈 예정입니다.
배열과 링크드 리스트의 차이점
배열은 메모리에 할당될 때 연속적인 데이터 공간에 할당이 됩니다.
데이터에 접근 할 때 random access가 가능하므로 빠르지만, 삽입 삭제 시에나 배열의 크기를 유동적으로 변하기 어렵습니다.
링크드 리스트는 메모리에 할당될 때 흩어져서 저장됩니다.
처음에는 크기를 지정해주지 않아도 되며 삽입 삭제가 빠르지만 검색 시 순차접근을 통해서 접근해야하므로 느립니다.
스택과 큐에 대해서 설명해주세요.
스택은 후입선출 구조로, 한쪽 끝에서만 삽입과 삭제가 이루어지며 함수 호출 스택이나 실행 취소 기능에 사용됩니다.
큐는 선입선출 구조로, 먼저 들어온 데이터가 먼저 처리되며 대기열 처리나 BFS와 같은 알고리즘에 활용됩니다.
우선순위 큐에 대해서 설명해주세요.
해시 테이블에 대해서 설명해주세요.
해시테이블은 키를 해시 함수로 변환해 인덱스로 사용하는 자료구조로 평균적으로 O(1)의 빠른 조회 성능을 제공하지만
충돌관리가 필요합니다.
충돌이 발생할 경우에는 체이닝이나 개발 주소법으로 해결합니다.
그래프와 트리의 차이점에 대해서 설명해주세요.
최소 신장 트리에 대해서 설명해주세요.
최소 신장 트리는 가중치 그래프에서 모든 노드를 연결하면서 사이클이 없고, 간선 가중치 합이 최소가 되도록 구성한 트리입니다.
크루스칼은 간선을 기준으로 선택하고, 프림은 정점을 기준으로 확장해 나가는 알고리즘입니다.
힙 자료구조에 대해서 설명해주세요.
힙은 완전 이진 트리 형태를 가지는 자료구조로,
최대 힙과 최소 힙으로 나뉘고 루트 노드에서 항상 최댓값 또는 최솟값을 O(1)에 접근할 수 있습니다.
삽입과 삭제는 힙 속성을 유지하기 위해 O(logN)이 걸리며,
이러한 특성으로 우선순위 큐 구현에 주로 사용됩니다.
힙의 삽입과 삭제는 어떻게 이루어지나요?
힙에 새로운 원소를 삽입할 때는 완전 이진 트리 구조를 유지하기 위해 가장 마지막 위치에 노드를 추가한 뒤,
부모 노드와 비교하며 힙 속성을 만족할 때까지 위로 올리는 과정을 반복합니다.
힙에서 삭제는 보통 루트노드를 제거하며, 마지막 노드를 루트로 옮긴 뒤 자식노드와 비교하며 힙 속성을 만족할 때까지 아래로 내리는 과정을 반복합니다.
이진 탐색 트리에 대해 설명해 주세요.
이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지는 이진 트리로, 왼쪽 서브트리에는 부모보다 작은 값,
오른쪽 서브트리에는 부모보다 큰 값이 위치하도록 구성됩니다.
이러한 구조로 중위 순회 시 정렬된 결과를 얻을 수 있으며,
균형이 잡힌 경우 탐색,삽입, 삭제는 O(logN),
편향된 경우에는 O(N)의 시간 복잡도를 가집니다.
균형이 깨질 경우를 보완하기 위해 AVL 트리나 Red-Black 트리를 사용합니다.
포화 이진 트리, 완전 이진 트리, 전 이진 트리의 차이점에 대해 각각 설명해주세요.
포화 이진 트리는 모든 레벨이 완전히 채워진 이지트리로, 모든 내부 노드는 두 개의 자식을 가지며 모든 리프노드는 같은 깊이에 위치합니다.
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 채워져 있고 마지막 레벨의 노드들이 왼쪽부터 차례대로 채워진 이진트리입니다.
전 이진 트리는 모든 노드가 자식을 0개 또는 2개만 가지는 이진 트리입니다. (1개 불가)
레드 블랙 트리에 대해 설명해주세요.
레드-블랙 트리는 이진 탐색 트리의 한 종류로, 노드에 색상을 부여해 트리의 균형을 유지하는 자료구조입니다.
완벽한 균형은 아니지만, 트리의 높이를 O(logN)으로 제한하여 탐색,삽입,삭제의 시간 복잡도를 O(logN)으로 보장합니다.
레드 블랙 트리의 삽입과 삭제 과정에 대해서 말해주세요.
삽입은 일반 이진 탐색 트리와 동일하게 수행한 뒤, 새로 삽입된 노드를 RED로 설정합니다.
이후 부모와 삼촌 노드의 색상에 따라 색상 변경과 회전을 통해 레드-블랙 트리의 규칙을 만족하도록 조정합니다.
삭제 또한 이진 탐색 트리 방식으로 노드를 제거한 뒤, BLACK 노드가 삭제되어 규칙이 깨진 경우 형제 노드의 색상과 자식 상태에 따라 색상 변경과 회전을 통해 균형을 복구합니다.
삭제가 삽입보다 복잡합니다.
AVL에 대해 설명해주세요.
AVL 트리는 이진 탐색 트리의 한 종류로, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1을 유지하는 엄격한 균형 트리입니다.
삽입과 삭제 시 회전을 통해 균형을 유지하며 항상 O(logN)의 시간 복잡도를 보장합니다.
균형 조건은 왼쪽높이에서 오른쪽 높이를 뺀 절댓값이 1보다 같거나 작아야합니다.
B-Tree와 B+Tree에 대해 설명해주세요.
B-Tree는 하나의 노드에 여러개의 키와 자식을 가질 수 있는 다진 탐색트리로, 주로 디스크 기반 시스템에서 사용됩니다.
모든 리프 노드는 같은 레벨에 위치하며, 삽입, 삭제, 탐색은 O(logN)입니다.
B+Tree는 B-Tree의 변형으로, 모든 데이터는 리프 노드에만 저장되고 리프 노드들이 연결 리스트로 연결되어 있습니다.
이로 인해 범위 검색에 매우 효율적입니다. 이는 DB인덱스에서 가장 많이 사용됩니다.
꼬리질문 공부 리스트
Day 1
- 배열 vs 링크드 리스트
- 메모리 구조
- 캐시 지역성
- 삽입/삭제 실제 비용
- 해시 테이블
- 충돌
- 평균 vs 최악
- 언제 느려지나
- 힙 vs BST
- 왜 힙은 정렬 안 되나?
- 왜 PQ는 힙?
Day 2
- AVL vs Red-Black
- 회전 횟수
- 삽입/삭제 성능 차이
- 실사용 선택 기준
- B+Tree
- 디스크 I/O
- 범위 검색
- 왜 Hash 안 씀?
Day 3
- 그래프
- 트리 판별 조건
- MST 알고리즘 선택 기준
- 사이클 판별