📌 1. 스택과 큐에 대해서 설명해 주세요.
- 스택은 LIFO로 먼저 들어온 데이터가 나중에 나가는 자료구조 입니다.
- 즉, 출입구가 하나여서 한 곳에서만 삽입 삭제가 이루어집니다.
- 큐는 FIFO로 먼저 들어온 데이터가 먼저 나가는 자료구조입니다.
- 앞에서는 삭제가 이루어지고 뒤에서 삽입이 이루어집니다.
📌 2. 해시테이블에 대해서 설명해 주세요.
- 해시 테이블은 해시 함수를 통해 일정한 길이로 변환된 해시 값을 저장하는 자료구조입니다.
- key와 value로 저장되어 key값을 알고 있다면 빠르게 데이터를 탐색할 수 있다는 것이 특징입니다.
- 해시값 충돌에 대한 대안 중 선형 탐사가 있는데 선형 탐사는 저장하려는 곳에 이미 데이터가 저장되어 있다면 정해놓은 고정폭 단위로 옮겨가며 빈 곳을 찾아 데이터를 저장하는 방법입니다.
📌 3. 배열과 링크드 리스트의 차이점에 대해서 설명해 주세요.
- 배열은 한 번 크기를 정하면 변경할 수 없는 자료구조입니다.
- 그에 반해 연결 리스트는 동적으로 공간을 할당해 데이터를 저장할 수 있습니다.
- 또한, 배열은 데이터가 연속적으로 저장되어 있지만 연결 리스트는 주소값을 이용해 연결돼 불연속적인 단위로 저장되어있습니다.
📌 4. LinkedList vs ArrayList의 차이점에 대해 설명하시오 (+Array는 추가적인 메모리 확보가)
- ArrayList와 LinkedList는 모두 동적할당이 가능한 배열입니다.
- ArrayList는 Array와 같이 데이터가 연속적인 한 줄로 늘어진 형태입니다.
- LinkedList는 pointer를 이용해 주소로 연결되며 데이터가 불연속적인 단위로 저장됩니다.
📌 5. 그래프와 트리의 차이점에 대해서 설명해 주세요.
- 그래프와 트리는 모두 노드와 간선으로 이루어져 있습니다.
- 그러나, 그래프는 싸이클이 생길 수 있고 트리는 싸이클이 생기지 않습니다.
- 그래프는 부모와 자식이라는 관계가 없고 트리는 있습니다.
- 그래프는 루트 노드란 개념이 없고 트리에는 루트 노드가 존재합니다.
| 기준 | 그래프 | 트리 |
|---|---|---|
| 싸이클이 생길 수 있는가? | O | X |
| 부모-자식 관계가 있는가? | X | O |
| 루트 노드가 있는가? | X | O |
📌 6. 힙 자료구조에 대해 설명해 주세요.
- 힙은 완전 이진 트리의 일종입니다.
- 최댓값이나 최솟값을 O(1) 속도로 아주 빠르게 찾아내기 위한 자료구조입니다.
- 최대힙은 부모가 항상 자식보다 크고 최소힙은 부모가 항상 자식보다 작은 완전 이진 트리입니다.
📌 7. 힙의 삽입과 삭제는 어떻게 이루어지나요?
힙의 삽입
- 제일 마지막 노드에 삽입합니다.
- 최대힙인지 최소힙인지에 따라 부모 노드와 교환하며 힙을 재구성합니다.
힙의 삭제
- 항상 루트 노드에서 이루어집니다.
- 비어있는 루트 노드에 마지막 레벨의 마지막 노드를 넣습니다.
- 최대힙인지 최소힙인지에 따라 자식 노드와 교환하며 힙을 재구성합니다.
📌 8. 포화(Perfect) 이진트리, 완전(Complete) 이진트리, 정(Full) 이진트리의 차이점에 대해 각각 설명해주세요.
포화(Perfect) 이진트리
- 모든 레벨의 노드가 꽉 차 있는 트리입니다.
- 마지막 레벨의 노드가 완전하게 차있어야 합니다.
완전(Complete) 이진트리
- 마지막 레벨을 제외한 모든 노드들이 꽉 차 있는 트리입니다.
- 마지막 레벨은 왼쪽부터 채워져 있어야 합니다.
정(Full) 이진트리
- 부모의 자식이 0개 또는 2개인 트리입니다.
- 즉, 1개의 자식을 가지고 있는 부모 노드는 존재하지 않습니다.
📌 9. Binary Search Tree에 대해 설명해주세요.
- 이진 탐색 트리는 부모보다 작은 것은 왼쪽에 부모보다 큰 것은 오른쪽에 저장되는 트리입니다.
- 중위 순회를 거치면 오름차순으로 데이터를 가져 올 수 있습니다.
📌 10. 레드 블랙 트리에 대해 설명해주세요.
- 자가 균형 이진 탐색 트리
- 모든 노드는 빨간색 혹은 검은색
- 루트 노드는 검은색
- 빨간색 노드는 검은색 노드의 자식
- 모든 리프 노드는 검은색으로 트리의 끝을 나타내고 자료를 가지지 않은 null
- 모든 리프 노드에서 루트 노드로 가는 길에 만나는 검은색 노드의 수는 같음
📌 11. 레드 블랙 트리의 삽입과 삭제 과정에 대해서 말해보세요.
삽입
- 노드의 색을 정함
- 삽입할 노드의 색을 빨강이라고 가정했을 때, 부모 노드의 색이 검정일 경우 문제 없이 삽입 가능
- 삽입할 노드의 색을 빨강이라고 가정했을 때, 부모 노드의 색이 빨강일 경우 문제 발생
- 부모 노드가 레드인데, 부모님의 형제가 없거나 블랙일 때 - 회전
- 노드가 레드인데, 부모님의 형제가 레드일 때 - 색상 변환
삭제
- 삭제 노드가 빨강일 경우 그냥 삭제
- 삭제 노드가 검정일 경우, 빨강이 연속으로 오는 문제 발생
- 타겟 노드에 블랙 추가
- 타겟의 조카들이 모두 검정일 경우 부모의 색을 타겟과 타겟의 형제에게 나눠줌
- 타겟의 조카 중 일부가 빨강일 경우: 회전
- 타겟 노드에 블랙 추가
📌 12. B-Tree에 대해서 설명해 주세요.
- B-Tree란 2개 이상의 자식을 가질 수 있는 트리를 말합니다.
- 균일 트리라 같은 레벨의 값을 탐색할 때 같은 시간을 보장합니다.
- 그러나, 삽입 삭제 등의 연산이 반복될 수록 균일함이 깨질 수 있습니다.
- 데이터가 정렬된 상태로 존재합니다.
📌 13. B-Tree와 B+Tree의 차이점에 대해 설명해 주세요.
- B-Tree는 모든 노드에 데이터를 가지고 있는데 B+Tree는 리프에만 데이터를 가지고 있습니다.
- B+Tree는 데이터의 갱신이 리프에서만 일어납니다.
- B+Tree는 연결 리스트로 노드가 연결되어있습니다.
📌 14. 최소 신장 트리에 대해서 설명해 주세요.
- 우선 신장 트리란 모든 정점을 포함하는 트리입니다.
- 최소 신장 트리는 간선의 가중치가 다 다를 때 신장 트리의 가중치 합이 가장 작은 트리입니다.
Data가 좋은 Web 개발자