[자료구조] 자료구조 면접 대비

Q) 배열이 무엇인가요?
A) 배열은 값의 집합으로 구성되었고 인덱스로 식별됩니다.
데이터 조회에 O(1)시간이 소요됩니다.
동적 배열인 리스트의 경우 조회에는 마찬가지로 O(1)이 소요되나, 데이터의 삭제나 삽입은 O(n)이 소요됩니다. (shift 연산때문)


Q) 연결리스트는 무엇인가요?
A) 연결리스트는 데이터의 선형 집합이지만, 데이터의 순서가 메모리에 순차적으로 저장되지는 않습니다. 연결리스트의 삽입, 삭제는 배열보다 간단합니다. 처음이나 끝 지점에 노드를 추가하는 것은 O(1)에 가능합니다. 단, 특정 인덱스에 접근할 때는 순차 탐색을 해야하므로 O(n)시간이 소요됩니다.


Q) 스택의 특징은 무엇인가요?
A) 스택은 후입선출 구조의 자료구조입니다. 접시를 쌓는 것에 비유할 수 있습니다. push()와 pop()이 주요 연산입니다.


Q) 큐의 특징은 무엇인가요?
A) 큐는 선입선출 구조의 자료구조입니다. 줄을 서는 것에 비유할 수 있습니다.
+) 데크는 더블 엔디드 큐의 줄임말로, 양방향 모두 O(1)에 삭제와 삽입을 처리할 수 있습니다. 단순연결리스트로도 구현이 가능하지만 이중연결리스트로 구현하는 것이 가장 잘 어울립니다.


생각하기!!
+) 큐 두개로 힙 구현하기
+) 스택 두개로 큐 구현하기


Q) 우선순위 큐는 무엇인가요?
A) 우선순위큐는 큐, 스택과 같은 추상자료형과 유사하지만 각 요소의 우선순위와 연관되어있는 자료구조입니다.


Q) 해시 테이블은 무엇인가요?
A) 해시 테이블이나 해시맵은 키를 값에 매핑할 수 있는 구조입니다. 이때 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 의미합니다. 해시함수를 사용하는 것을 해싱이라고 합니다.


Q) 해시 충돌 해결방법엔 어떤 것이 있나요?
A) 오픈 어드레싱 방법과 체이닝 방식으로 나뉩니다. 오픈 어드레싱 방법 중 선형 조사법은 충돌 발생시 옆자리를 순차적으로 탐색하며 빈 자리를 찾는 방법입니다. 이차 조사법은 옆이 아닌 조금 멀리서 빈 공간을 탐색하는 것입니다. 이중 해쉬는 공간 탐색을 좀 더 불규칙하게 만들기 위해 두개의 해쉬함수를 사용하는 것입니다. 체이닝 방식은 충돌이 발생하면 연결리스트 방식으로 데이터를 연결해나가는 방법입니다.


Q) BFS와 DFS를 설명해주세요.
A) bfs는 너비 우선 탐색으로, 인접한 노드를 우선적으로 탐색하는 방법입니다. bfs는 큐를 활용한 반복구조로 구현할 수 있습니다. dfs는 깊이 우선 탐색으로, 다음 분기로 넘어가기전에 해당 분기를 완벽히 탐색하는 방법입니다. dfs는 재귀구조 또는 스택을 활용한 반복구조로 구현합니다.
+) 백트래킹은 dfs처럼 탐색을 하다 답의 가능성이 없다고 판단되면 즉시 포기하면서 정답을 찾아나가는 방식입니다.


Q) 트리 자료구조란 무엇인가요?
A) 계층형 트리구조를 시뮬레이션하는 추상자료형으로, 루트 값과 부모자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합입니다.


Q) 그래프와 트리의 차이점은 무엇인가요?
A) 트리는 사이클을 갖지 않습니다. 또한 그래프가 단방향 또는 양방향이 될 수 있는 것에 반해 트리는 단방향 그래프이고, 트리는 오직 하나의 부모를 갖습니다.


Q) 그래프를 구현하는 두가지 방법은 무엇인가요?
A) 정방 행렬을 사용하여 인접 행렬을 구현하는 방법과 인접리스트를 사용하는 방법이 존재합니다.


Q) 이진 트리 종류에 대해 말해주세요.
A) 정이진트리(full binary tree)는 모든 노드가 0또는 2개의 자식 노드를 갖는 형태입니다. 완전이진트리(complete binary tree)는 마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있으며, 마지막 레벨의 왼쪽 노드부터 채워져 있는 형태입니다. 포화이진트리(perfect binary tree)는 모든 노드가 2개의 자식노드를 가지며 모든 리프 노드가 동일한 레벨을 갖는 형태입니다.


Q) 이진 탐색 트리는 무엇인가요?
A) 노드의 왼쪽 서브트리에는 노드 값보다 작은 값을 가진 노드들로 이루어져 있고, 오른쪽 서브트리에는 노드 값보다 큰 값을 가지는 노드들로 이루어져 있는 트리입니다.


Q) 자가균형 이진탐색트리는 무엇인가요?
A) 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진탐색트리입니다. 레드-블랙 트리, AVL 트리 등이 있습니다.



Q) 레드-블랙 트리
A) 레드 블랙 트리는 이진탐색트리의 일종으로 트리의 높이를 최대한 작게 유지시켜줍니다. 레드 블랙 트리의 조건은 4가지가 있습니다.
1. 루트 노드의 색깔은 검정입니다.
2. 모든 리프 노드의 색깔은 검정입니다.
3. 빨강 노드의 자식은 검정입니다.(=빨간 노드가 연속으로 나올 수 없습니다.)
4. 모든 리프노드에서 black depth가 동일합니다.

<삽입>
BST와 같은 방법으로 값 삽입을 진행하다가 빨강 노드가 연속으로 나오는 더블 레드 현상이 발생하면 다음에 의해서 해결하게됩니다.
1. 엉클 노드의 색깔이 검정이면 restructing을 합니다.
2. 엉클 노드의 색깔이 빨강이면 recoloring을 합니다.
restructing은 자신, 부모, 조부모를 오름차순으로 정렬한뒤 가운데값을 부모로 만들고 나머지 둘을 자식으로 만듭니다. 그리고 가운데 노드를 검정, 두 자식들을 빨강으로 만듭니다. restructing 작업은 무조건 1번 시행되며 O(1) 소요됩니다.
recoloring은 부모와 엉클을 검정, 조부모를 빨강으로 바꿉니다. 조부모가 루트일 경우 검정으로 바시 바꿔줍니다. 한편 빨강으로 바뀐 조부모의 색에 의해 다시 더블레드 현상이 발생할 수 있기 때문에 recoloring은 최대 logN번 시행됩니다. recoloring은 O(1)이므로 결국 최대 O(logN) 소요됩니다.

+)https://zeddios.tistory.com/237
+)https://www.youtube.com/watch?v=vDHFF4wjWYU

<삭제>
삭제의 경우 삭제 노드의 child 개수에 따라 rotation 방법이 달라지게 됩니다. 삭제 노드가 레드라면 violation이 발생하지 않으므로 그냥 삭제 해주면 되지만, 블랙이라면..
https://leeyongjeon.tistory.com/entry/C%EC%96%B8%EC%96%B4-%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%AC-%EC%82%AD%EC%A0%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98RedBlack-Trees-in-C-deleting-or-removing-algorithm




Q) AVL 트리
A) 하.. 귀찮다..


Q) 트리 순회에는 무엇이 있나요?
A) 트리 순회는 트리 구조에서 각 노드를 한번씩 방문하는 과정입니다. 이진트리에서는 방문 순서에 따라 전위순회, 중위순회, 후위순회가 있습니다. 전위순회는 현재 노드를 순외하고 왼쪽 서브트리를 순회하고 오른쪽 서브트리를 순회합니다. 중위순회는 왼쪽 서브트리-현재노드-오른쪽 서브트리, 후위순회는 왼쪽 서브트리-오른쪽 서브트리-현재 노드 순으로 탐색합니다.
재귀구조로 간결하게 구현할 수 있습니다.


Q) 힙 자료구조는 무엇인가요?
A) 힙은 트리 기반의 자료구조로, 힙의 특성을 만족하는 거의 완전한 트리입니다. 우선순위 큐를 힙으로 구현하게 됩니다. 삽입 연산은 요소를 하위 레벨의 최대한 안쪽으로 삽입한뒤 부모 노드와 비교하며 자리를 찾아가는 방식(업힙)으로 O(logn)이 소요됩니다. 추출 연산은 루트를 추출하고 마지막 요소가 루트 자리로 올라간 후 다시 자식 노드와 비교하며 자리를 찾아가는 방식(다운힙)으로 이루어집니다. 이 역시 O(logn)이 소요됩니다.
+) 임의의 배열 전체를 heapify하는 데에는 O(n)이 소요됩니다.
**제대로 알기 https://hezma.tistory.com/8


Q) 트라이 자료구조는 무엇인가요?
A) 트라이는 검색트리의 일종으로, 키가 문자열인 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조입니다.
트라이의 주요 메서드는 insert, search, startswith입니다.
insert는 입력받은 문자열을 한글자씩 체크하여 해당 노드의 children 딕셔너리에 키값으로 존재하지 않으면 키값으로 할당하고 새로운 노드를 만들어나가는 방식입니다. 이때 문자가 끝나는 지점의 노드는 bool word 값을 True로 설정해줍니다.
search는 문자 한글자씩 탐색하다 중간에 키 값이 존재하지 않을시 False를 리턴하고, 문자가 끝났을 시에 노드의 word값이 False로 설정되어 있으면 False를 반환합니다.