자료구조

1. 데이터 구조란 무엇입니까?

데이터 구조는 컴퓨터에서 사용되는 데이터의 조직화 방법입니다. 데이터 구조는 데이터를 효율적으로 저장하고 검색할 수 있는 방법을 제공하며, 알고리즘의 성능을 개선하는 데 도움을 줍니다. 예를 들어, 배열, 링크드 리스트, 트리, 그래프 등이 데이터 구조의 일부입니다. 이러한 데이터 구조들은 데이터를 저장하고 연산을 수행하는 데 사용됩니다. 데이터 구조는 컴퓨터 프로그래밍에서 중요한 개념 중 하나이며, 프로그래밍 언어에서 제공하는 여러 기본 데이터 타입을 조합하여 구현됩니다.

1. 배열(array)과 연결된 목록(linked list)의 차이점은 무엇입니까?연결된 목록은 노드라는 개별적인 객체를 연결하여 데이터를 저장하는 구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하고 있습니다. 이러한 특성 때문에 연결된 목록은 동적으로 크기를 조정할 수 있으며, 데이터를 삽입하거나 삭제하는 작업이 비교적 쉽습니다. 그러나 인덱스를 사용하여 데이터에 직접 접근하는 것은 배열보다 느리며, 각 노드가 포인터를 저장해야 하므로 공간 낭비가 발생할 수 있습니다.
2. 따라서, 배열은 데이터를 빠르게 접근할 수 있지만 크기를 동적으로 변경할 수 없으며, 연결된 목록은 크기를 동적으로 변경할 수 있지만 데이터에 느리게 접근할 수 있고 공간을 더 많이 사용합니다. 사용하는 상황에 따라 배열과 연결된 목록 중 적합한 것을 선택해야 합니다.
3. 배열은 일정한 크기의 메모리 블록에 연속적으로 데이터를 저장하는 구조입니다. 이러한 특성 때문에 배열은 인덱스를 사용하여 빠르게 데이터에 접근할 수 있습니다. 그러나 배열은 크기를 동적으로 변경할 수 없으며, 데이터를 삽입하거나 삭제하는 작업이 비효율적입니다.
4. 배열(array)의 요소에 액세스할 때의 시간 복잡도는 얼마입니까?

배열의 요소에 액세스할 때의 시간 복잡도는 O(1)입니다. 이는 배열이 인덱스를 사용하여 메모리 상의 특정 위치에 직접적으로 액세스하기 때문입니다. 따라서, 인덱스가 주어졌을 때 배열에서 특정 요소를 찾는 작업은 상수 시간에 이루어집니다. 이러한 특성 때문에 배열은 데이터를 빠르게 검색하거나 정렬하는 데 효과적이며, 대부분의 경우 배열에서 데이터를 읽어오는 것은 매우 빠르고 효율적입니다. 그러나 배열의 크기를 변경하거나 요소를 삽입, 삭제하는 작업은 비용이 높기 때문에 이러한 작업을 자주 수행해야 하는 경우에는 다른 데이터 구조를 사용하는 것이 더 적합할 수 있습니다.

1. 배열 또는 연결 목록을 사용하여 스택을 어떻게 구현합니까?
   1. 배열을 사용한 스택 구현: 배열을 사용한 스택 구현은 가장 간단한 방법 중 하나입니다. 배열의 맨 끝에 새로운 데이터를 추가하거나 삭제할 때는 배열의 인덱스를 조작하여 구현합니다. 구현 방법은 다음과 같습니다.
   • 스택의 크기를 미리 지정한 후, 배열을 생성합니다.
   • 스택에 새로운 데이터를 추가할 때는 배열의 맨 끝에 데이터를 추가합니다. 이때 배열의 인덱스를 조작하여 맨 끝 위치를 가리키도록 합니다.
   • 스택에서 데이터를 삭제할 때는 배열의 맨 끝 데이터를 삭제합니다. 이때도 인덱스를 조작하여 맨 끝 위치를 가리키도록 합니다.
   배열을 사용한 스택 구현은 구현이 간단하고 메모리 접근 속도가 빠르지만, 스택의 크기를 미리 지정해야 하고, 스택이 가득 찬 경우 데이터를 추가할 수 없습니다.
   1. 연결 목록을 사용한 스택 구현: 연결 목록을 사용한 스택 구현은 스택의 크기를 미리 지정하지 않아도 되며, 동적으로 메모리를 할당할 수 있어 스택의 크기가 유동적으로 변할 수 있습니다. 구현 방법은 다음과 같습니다.
   • 스택의 맨 위에 새로운 데이터를 추가할 때는 연결 목록의 맨 앞에 새로운 노드를 추가합니다. 이때 새로운 노드의 다음 노드는 이전 노드를 가리키도록 합니다.
   • 스택에서 데이터를 삭제할 때는 연결 목록의 맨 앞 데이터를 삭제합니다. 이때 삭제할 노드의 다음 노드를 새로운 맨 위 노드로 지정합니다.
   연결 목록을 사용한 스택 구현은 스택의 크기가 유동적으로 변할 수 있으며, 구현이 복잡하지만, 메모리 할당과 해제에 대한 오버헤드가 있을 수 있습니다.
2. 스택(Stack)은 후입선출(LIFO: Last In First Out)의 원리를 따르는 자료구조로, 새로운 데이터는 스택의 맨 위(top)에 추가되며, 삭제할 때는 맨 위의 데이터가 먼저 삭제됩니다. 배열(Array) 또는 연결 목록(Linked List)을 사용하여 스택을 구현할 수 있습니다.
3. 배열 또는 연결 목록을 사용하여 대기열을 어떻게 구현합니까?배열을 사용한 대기열 구현 방법은 다음과 같습니다:
   • 크기가 고정되어 있으므로 배열의 크기를 미리 정해야 합니다.
   • 큐의 시작과 끝을 나타내는 인덱스를 유지합니다.
   • 큐에 새로운 요소를 추가할 때는 끝 인덱스를 하나 증가시키고, 요소를 해당 인덱스에 추가합니다.
   • 큐에서 요소를 제거할 때는 시작 인덱스를 하나 증가시키고, 해당 인덱스의 요소를 반환합니다.
   • 큐가 가득 차 있는 경우 새로운 요소를 추가할 수 없습니다.
   • 큐가 비어 있는 경우 요소를 제거할 수 없습니다.
   연결 목록을 사용한 대기열 구현 방법은 다음과 같습니다:
   • 각 노드는 값과 다음 노드를 가리키는 포인터를 가지고 있습니다.
   • 큐의 시작과 끝을 나타내는 두 개의 포인터를 유지합니다.
   • 큐에 새로운 요소를 추가할 때는 새로운 노드를 생성하고, 끝 포인터가 가리키는 노드의 다음 노드로 추가합니다.
   • 큐에서 요소를 제거할 때는 시작 포인터가 가리키는 노드의 값을 반환하고, 시작 포인터를 다음 노드로 이동시킵니다.
   • 큐가 비어 있는 경우 시작 및 끝 포인터는 모두 NULL을 가리킵니다.
   배열과 연결 목록을 사용한 대기열 구현은 각각 장단점이 있으며, 구현 상황에 따라 적절한 방법을 선택해야 합니다.
4. 배열 또는 연결 목록을 사용하여 대기열을 구현할 수 있습니다.
5. 연결된 목록(linked list)의 요소에 액세스할 때의 시간 복잡도는 얼마입니까?그러나 연결된 목록은 배열과 달리 삽입, 삭제 작업에 대한 시간 복잡도가 O(1)로 매우 효율적입니다. 이는 삽입 또는 삭제할 요소를 찾는 작업이 필요하지 않고, 해당 요소의 포인터를 수정하는 것만으로도 작업이 수행될 수 있기 때문입니다. 따라서, 삽입, 삭제 작업이 자주 발생하는 경우에는 연결된 목록이 더 적합한 데이터 구조일 수 있습니다.
6. 연결된 목록에서 특정 요소에 액세스할 때의 시간 복잡도는 일반적으로 O(n)입니다. 이는 연결된 목록이 각 노드에 포인터를 사용하여 연결되어 있기 때문입니다. 따라서, 특정 요소를 찾기 위해서는 첫 번째 노드부터 시작하여 해당 요소가 있는 노드까지 포인터를 따라 이동해야 합니다. 이러한 작업은 일반적으로 요소의 인덱스가 어디에 있는지에 따라 더 많은 시간이 소요될 수 있습니다.
7. 스택과 큐의 차이점은 무엇입니까?스택은 후입선출(LIFO, Last-In-First-Out) 구조입니다. 즉, 마지막으로 추가된 요소가 가장 먼저 삭제됩니다. 스택은 가장 위에 있는 요소에만 액세스할 수 있으며, 새로운 요소를 추가하거나 삭제할 때는 항상 가장 위에 있는 요소에 대해서만 수행됩니다. 이러한 특성 때문에 스택은 재귀 알고리즘, 브라우저의 방문 기록 등에 유용하게 사용됩니다.따라서, 스택과 큐는 구조와 작동 방식에서 큰 차이가 있습니다. 스택은 후입선출 구조이며, 가장 위에 있는 요소에만 액세스할 수 있으며, 큐는 선입선출 구조이며, 가장 앞쪽의 요소와 가장 뒤쪽의 요소에 모두 액세스할 수 있습니다.
8. 반면 큐는 선입선출(FIFO, First-In-First-Out) 구조입니다. 즉, 가장 먼저 추가된 요소가 가장 먼저 삭제됩니다. 큐는 가장 앞쪽의 요소와 가장 뒤쪽의 요소에 모두 액세스할 수 있으며, 요소를 추가하거나 삭제할 때는 항상 큐의 뒤쪽에 요소를 추가하고 앞쪽에서 요소를 삭제합니다. 이러한 특성 때문에 큐는 대기열 처리, 탐색 알고리즘 등에 유용하게 사용됩니다.
9. 스택과 큐는 모두 데이터를 저장하고 조작하는 데 사용되는 추상적인 데이터 구조입니다. 하지만 스택과 큐는 그 구조와 작동 방식에서 차이가 있습니다.
10. 이진 트리와 이진 검색 트리의 차이점은 무엇입니까?따라서 이진 검색 트리는 루트 노드보다 작은 값은 왼쪽 자식 노드에, 큰 값은 오른쪽 자식 노드에 위치하므로, 트리 내에서 값을 검색하거나 삽입할 때 효율적인 탐색이 가능합니다. 이진 검색 트리에서는 특정 값을 찾을 때 루트 노드부터 시작하여 값을 찾을 때까지 왼쪽 자식 노드 또는 오른쪽 자식 노드로 이동합니다. 이러한 이진 검색 트리의 특성 때문에 데이터를 효율적으로 탐색하고 삽입, 삭제할 수 있으며, 이를 활용한 알고리즘도 많이 존재합니다.
11. 반면에 이진 트리는 제약 조건이 없기 때문에 노드의 자식 노드 위치에 대한 제약이 없습니다. 이진 트리에서는 특정 값을 찾을 때 모든 노드를 방문해야 할 수도 있으며, 탐색 및 삽입, 삭제 작업에 대한 효율성이 낮을 수 있습니다. 따라서 이진 트리는 이진 검색 트리에 비해 성능이 떨어지는 경우가 많습니다.
12. 이진 트리와 이진 검색 트리는 모두 이진 트리의 일종입니다. 이진 트리는 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리입니다. 이에 비해 이진 검색 트리는 이진 트리 중에서도 루트 노드보다 작은 값을 가지는 노드는 왼쪽 자식 노드에, 큰 값을 가지는 노드는 오른쪽 자식 노드에 위치시키는 제약 조건을 추가한 트리입니다.
13. 해시 테이블과 이진 검색 트리의 차이점은 무엇입니까?해시 테이블은 해시 함수를 사용하여 데이터를 저장하고 검색합니다. 해시 함수는 데이터의 키를 입력으로 받아 해시값을 생성하고, 해당 해시값을 인덱스로 사용하여 데이터를 배열에 저장합니다. 해시 테이블은 데이터를 저장할 때 해시 충돌이 발생할 가능성이 있으며, 이 때는 충돌이 발생한 데이터를 연결 리스트에 추가하여 저장합니다. 해시 테이블은 해시 함수의 성능에 크게 영향을 받으며, 해시 함수의 성능이 좋을수록 검색 속도가 빨라집니다.두 자료 구조는 모두 데이터를 검색하는 데 사용되며, 해시 테이블은 해시 함수의 성능과 충돌 처리 방식에 따라 검색 속도가 달라질 수 있으며, 이진 검색 트리는 트리의 형태에 따라 검색 속도가 달라집니다.
14. 반면에 이진 검색 트리는 이진 검색 트리의 특성을 이용하여 데이터를 저장하고 검색합니다. 이진 검색 트리에서는 루트 노드부터 시작하여 찾고자 하는 데이터와 값을 비교하며, 작은 값을 가진 데이터는 왼쪽 자식 노드, 큰 값을 가진 데이터는 오른쪽 자식 노드에 저장합니다. 이진 검색 트리는 높이 균형을 유지하는 AVL 트리나 레드-블랙 트리와 같은 특별한 형태의 이진 검색 트리를 사용하면 검색 속도를 향상시킬 수 있습니다.
15. 해시 테이블과 이진 검색 트리는 데이터를 저장하고 검색하는 데 사용되는 자료 구조입니다. 그러나 두 자료 구조는 서로 다른 방식으로 데이터를 저장하고 검색합니다.
16. 너비 우선 검색과 깊이 우선 검색의 차이점은 무엇입니까?BFS는 시작 노드로부터 거리가 가까운 노드부터 방문하며, 너비를 우선으로 탐색하는 방법입니다. 즉, 인접한 노드를 모두 방문한 후에 그 다음 노드를 방문합니다. BFS는 최단 경로를 찾을 때 유용하게 사용됩니다. 시간 복잡도는 노드의 수를 V, 간선의 수를 E라고 할 때 O(V+E)입니다.따라서, BFS는 최단 경로를 찾는 문제에 유리하며, DFS는 모든 경로를 탐색하고자 할 때 유용합니다.
17. 반면, DFS는 시작 노드에서 한 방향으로 탐색을 진행하다가 더 이상 갈 곳이 없으면 다시 돌아와 다른 방향으로 탐색을 진행하는 방식입니다. 즉, 깊이를 우선으로 탐색하는 방법입니다. DFS는 재귀 함수를 이용하여 구현할 수 있습니다. DFS는 답이 될 가능성이 높은 경로를 먼저 탐색하기 때문에, 최적의 해를 찾는 문제에 적용하기 어렵습니다. 시간 복잡도는 BFS와 같이 O(V+E)입니다.
18. 너비 우선 검색(BFS)과 깊이 우선 검색(DFS)은 그래프에서 노드를 탐색하는 방법 중 가장 대표적인 두 가지 방법입니다.
19. 힙이란 무엇이며 어떤 작업을 수행할 수 있습니까?힙은 주로 최소값 또는 최대값을 빠르게 찾기 위한 우선순위 큐(priority queue)를 구현할 때 사용됩니다. 이 때, 최소값을 찾기 위해서는 '최소 힙(min heap)'을 사용하고, 최대값을 찾기 위해서는 '최대 힙(max heap)'을 사용합니다.
    1. 삽입(insert): 새로운 값을 삽입하고, 힙 속성을 유지합니다.
    2. 삭제(delete): 최소값 또는 최대값을 삭제하고, 힙 속성을 유지합니다.
    3. 힙 정렬(heap sort): 주어진 배열을 힙으로 만든 후, 힙에서 값을 하나씩 꺼내 정렬합니다.
    4. 최소/최대값 찾기(find min/max): 최소 힙에서는 최소값, 최대 힙에서는 최대값을 빠르게 찾을 수 있습니다.
    5. 우선순위 큐(priority queue): 우선순위 큐는 값이 들어오면 우선순위에 따라 삽입되고, 우선순위가 가장 높은 값이 먼저 삭제되는 자료구조입니다. 이를 힙을 이용하여 구현할 수 있습니다.
    힙은 이진탐색트리와 달리 균형잡힌 트리가 아니기 때문에 검색(search)이나 수정(update)에는 적합하지 않습니다. 하지만, 힙은 삽입과 삭제가 빈번하게 일어나는 우선순위 큐에서 가장 효율적인 자료구조 중 하나입니다.
20. 힙에는 다음과 같은 주요 작업들이 가능합니다.
21. 힙(Heap)은 완전 이진트리를 기반으로 한 자료구조로, 부모 노드와 자식 노드 간의 크기 관계를 유지하는 이진트리입니다. 즉, 부모 노드는 자식 노드보다 항상 크거나 작은 값을 가지며, 이를 '힙 속성(heap property)'이라고 합니다.
22. 힙메모리는 무엇인지?힙 메모리는 프로그램 실행 중에 운영체제로부터 할당받아 사용하는 영역으로, 사용자가 직접 할당하고 해제할 수 있습니다. 이를 위해서는 malloc, calloc, realloc과 같은 함수를 사용하여 동적으로 메모리를 할당하고, free 함수를 사용하여 메모리를 해제해야 합니다.
23. 힙 메모리는 스택 메모리와 달리 데이터 크기를 미리 정하지 않아도 되기 때문에, 유연한 메모리 할당이 가능합니다. 하지만, 힙 메모리는 사용 후 반드시 해제해야 하며, 메모리 누수(memory leak)를 방지하기 위해 주의가 필요합니다. 또한, 잘못된 사용으로 인해 힙 오버플로우(heap overflow)와 같은 보안 취약점이 발생할 수 있습니다.
24. 힙 메모리(Heap Memory)는 동적 메모리 할당을 위한 메모리 영역 중 하나입니다. 프로그램 실행 중에 필요한 데이터를 동적으로 할당하고 해제할 수 있는 영역으로, C, C++, Java 등의 프로그래밍 언어에서 사용됩니다.
25. AVL 트리와 레드-블랙 트리의 차이점은 무엇입니까?AVL 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 최대 1로 유지하는 것을 목표로합니다. 따라서 AVL 트리는 균형을 맞추기 위해 노드의 삽입 및 삭제 시 회전 작업을 수행해야합니다. AVL 트리의 높이는 항상 O(log n)입니다. 이로 인해 AVL 트리는 탐색과 삽입/삭제 모두에 O(log n)의 시간 복잡도를 가집니다.
26. 반면에 레드-블랙 트리는 삽입 및 삭제시에도 트리의 균형을 맞추기 위해 색상을 사용합니다. 각 노드는 빨간색 또는 검은색 중 하나로 색칠됩니다. 레드-블랙 트리의 높이는 AVL 트리보다 더 높을 수 있지만, 최악의 경우에도 O(log n)을 유지합니다. 레드-블랙 트리의 삽입 및 삭제는 AVL 트리보다 덜 복잡하며, 대신 검색 시에는 AVL 트리보다 약간 느릴 수 있습니다. 따라서 레드-블랙 트리는 데이터가 자주 변경되는 경우에 적합합니다.
27. AVL 트리와 레드-블랙 트리 모두 자기 균형 이진 탐색 트리의 일종입니다. 하지만 두 트리 사이에는 몇 가지 차이점이 있습니다.
28. 연결된 목록의 중간 요소는 어떻게 찾습니까? https://velog.io/@lacomaco/토끼와-거북이-알고리즘-LeetCode-142구체적으로, 연결된 목록의 head를 가리키는 포인터를 두 개 만듭니다. 첫 번째 포인터는 한 번에 한 노드씩 전진하고, 두 번째 포인터는 한 번에 두 노드씩 전진합니다. 두 번째 포인터가 끝에 도달할 때 첫 번째 포인터는 중간 노드를 가리키게 됩니다. 이 알고리즘은 두 번째 포인터가 끝에 도달할 때까지 반복됩니다.
29. 연결된 목록에서 중간 요소를 찾으려면 "토끼와 거북이" 알고리즘을 사용할 수 있습니다. 이 알고리즘은 두 개의 포인터를 사용하여 목록을 탐색합니다. 한 포인터는 한 번에 한 노드씩 움직이고, 다른 포인터는 한 번에 두 노드씩 움직입니다. 두 번째 포인터가 목록의 끝에 도달하면 첫 번째 포인터는 중간 노드를 가리키게 됩니다.
30. 배열에서 k번째로 작은 요소를 어떻게 찾습니까? https://www.daleseo.com/quick-select/Quickselect 알고리즘은 퀵 정렬과 유사한 방법을 사용하여 배열에서 k번째로 작은 요소를 찾습니다. 퀵 정렬에서와 같이 피벗을 선택하고 배열을 두 개의 하위 배열로 분할합니다. 피벗이 k번째로 작은 요소보다 작은 경우, 피벗의 오른쪽에 있는 요소만을 대상으로 다시 분할합니다. 반대로, 피벗이 k번째로 작은 요소보다 큰 경우, 피벗의 왼쪽에 있는 요소만을 대상으로 다시 분할합니다. 이 과정을 반복하여 k번째로 작은 요소를 찾습니다.
31. Quickselect 알고리즘은 최악의 경우에도 O(n^2)의 시간 복잡도를 가지지 않으며, 일반적으로 O(n)의 시간 복잡도를 가집니다.
32. 배열에서 k번째로 작은 요소를 찾으려면 여러 가지 방법이 있지만 일반적으로 Quickselect 알고리즘이 사용됩니다.
33. 퀵 정렬, 병합 정렬 및 힙 정렬과 같은 정렬 알고리즘의 시간 복잡성은 무엇입니까?
    • 퀵 정렬: 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우 O(n^2)의 시간 복잡도를 가집니다. 최악의 경우는 대개 이미 정렬된 배열이나 역순으로 정렬된 배열 등에서 발생합니다.
    • 병합 정렬: 항상 O(n log n)의 시간 복잡도를 가집니다. 하지만, 병합 정렬은 임시 배열이 필요하므로 추가적인 메모리 공간이 필요합니다.
    • 힙 정렬: 항상 O(n log n)의 시간 복잡도를 가지며, 병합 정렬보다 메모리를 덜 사용합니다. 힙 정렬은 힙이라는 자료구조를 사용하기 때문에, 힙을 구성하는 과정이 추가로 필요합니다.
    이러한 정렬 알고리즘들 중에서 힙 정렬은 안정적인 정렬 알고리즘이 아니므로, 원래 데이터의 순서를 유지하려면 추가적인 작업이 필요할 수 있습니다.
34. 퀵 정렬, 병합 정렬 및 힙 정렬과 같은 정렬 알고리즘의 시간 복잡도는 다음과 같습니다.

 

 

 

---

 

자료구조 예상 질문

1. Array(배열), LinkedList, ArrayList의 차이는 무엇인가요?

배열

• int arr[10];
• 선언 시 크기와 데이터타입을 지정
• 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조
• 데이터 삭입 및 삭제 시 해당 index를 중심으로 뒤에 있는 모든 요소들을 이동 → 비효율적
• 검색 시 index를 사용하여 O(1)

List(ArrayList)

• 크기를 정해주지 않아도 된다.
• 순서가 중요!
• 데이터 삭입 및 삭제 시 해당 index를 중심으로 뒤의 있는 모든 요소들을 이동 → 비효율적
• 검색 시 index를 사용하여 O(1)

LinkedList

• 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식
• 데이터 삽입 및 삭제 시 이전과 다음 노드가 가리켰던 주소값만 수정하면 효율적으로 가능
• 검색 시 순차적으로 살펴봐야 하므로 비효율적

1. 스택과 큐의 차이는 무엇인가요?

스택

• LIFO(Last In First Out, 후입선출)
• 가장 나중에 들어온 것이 가장 먼저 나온다.
• 예시) 함수의 스택, 문자열 역순 출력 등
• push( ), pop( ), isEmpty( ), isFull( )
• [참고] 최대 크기가 없는 스택을 만드려면 → 연결리스트(LinkedList) 이용

큐

• FIFO(First in First Out, 선입선출)
• 가장 먼저 들어온 것이 가장 먼저 나온다.
• 예시) 버퍼, BFS
• 큐는 들어올 때 rear로 들어오지만, 나올때는 front 부터 빠지는 특성

1. 힙 자료구조에 대해서 말해보세요.

힙

• 우선순위 큐를 위해 만들어진 자료구조
• 우선순위큐 : 우선순위가 높은 데이터가 먼저 나가는 구조
• 예시) 작업 스케줄링
• 삽입과 삭제 시 시간복잡도 : O(logn)
• 완전 이진트리의 일종 (여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만든 자료구조)

최대 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리

최소 힙

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

1. 트리의 특징에 대해서 말해보세요.

트리

• 값을 가진 노드와 이 노드들을 연결해주는 간선으로 이루어짐
• 사이클이 존재할 수 없음 (사이클이 있다면 그것은 그래프!)
• 모든 노드는 자료형으로 표현 가능
• 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
• 노드의 개수가 N개면, 간선은 N-1개를 가진다.

*이진탐색트리 공부할 것

1. 해시에 대해서 말해보세요.

해시

• 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
• 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑

→ 데이터가 많아지면, 다른 데이터가 같은 해시값으로 충돌나는 현상 발생 (Collision 현상)

해시테이블을 쓰는 이유?

• 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
• 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리 가능
• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색 가능
• 해시테이블의 시간복잡도 : O(1)

Collision 문제 해결 방법

• 체이닝: 연결리스트로 노드를 계속 추가해나가는 방식 (제한X, 메모리문제)
• Open Addressing: 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어 있으면 다음 주소에 저장)
• 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
• 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

1. B Tree가 무엇인가요?

[참고] 이진트리

• 하나의 부모가 두개의 자식만 가질 수 있음
• 균형이 맞지 않으면 검색 효율이 선형검색급으로 떨어짐
• 간결함과 균형만 맞다면, 검색 삽입 삭제 모두 O(logN)

B Tree

• 데이터 베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종
• 이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree
• 자식 수에 대한 일반화를 진행하면서, 트리의 균형을 자동으로 맞춰주는 로직을 갖춤
• 단순하고 효율적, 레벨로만 따지면 완전히 균형을 맞춘 트리
• 각 노드의 자료는 정렬된 상태, 노드의 자료수가 N이면 자식수는 N+1

B+ Tree

• 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드가 추가로 있음
• B-Tree의 변형구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어짐
• 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용
• leaf 노드끼리 연결리스트로 연결되어 있어서 범위 탐색에 매우 유리
• B-tree의 경우 최상 케이스에서는 루트에서 끝낼 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함

 

 

 

 

---

 

• ❓스택과 큐의 차이
• 스택은 후입선출, 큐는 선입선출
• ❓스택과 큐는 각각 ArrayList, LinkedList중에 뭐가 더 좋은지
• Stack은 ArrayList Queue는 LinkedList [<https://staticclass.tistory.com/100>](<https://staticclass.tistory.com/100>) ArrayList와 LinkedList의 성능이 같다면 ArrayList를 쓰는 게 좋음(공간복잡도에서 유리) -> LinkedList는 앞 뒤 주소를 모두 가지고 있기 때문 stack은 맨 뒤 추가, 맨 뒤 삭제만 가능하기 때문에 ArrayList가 유리 queue는 맨 뒤 추가, 맨 앞 삭제이기 때문에 LinkedList가 유리 -> ArrayList는 맨 앞을 제거하면 한 칸씩 당겨야 함
• ✅우선순위 큐→ 힙 구현이 가장 효율적

• ❓Priority Queue의 동작원리우선순위 큐는 힙이라는 자료구조를 가지고 구현한다. top이 최대면 최대힙, top이 최소면 최소힙으로 표현한다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.
• 우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용합니다. 힙은 완전이진트리를 통해서 구현되었기 때문에 우선순위 큐의 시간복잡도는 O(logn)입니다.
• ❓BST와 Binary Tree설명이진탐색의 빠른 탐색과 연결리스트의 삽입/삭제의 장점을 가짐
• 이진트리와 다르게 이진탐색트리는 왼쪽 트리값은 부모 노드보다 작아야 하며, 오른쪽 트리값은 부모 노드보다 커야 함
• BST는 이진탐색과 연결리스트를 결합한 자료구조
• ❓Hash Map과 Hash Table의 차이해시테이블은 병렬 처리를 할 때(동기화를 고려해야 할 때)Thread-safe하고 null값을 허용하지 않음
• 해시맵은 병렬 처리를 하지 않을 때 Thread-safe하지 않고, null값을 허용함
• 동기화 지원 여부과 null값 허용 여부의 차이