[ CS 기술면접 ] 자료구조 예상질문 모음 !

CS 기술면접 스터디 5주차에 접어들며 스터디장님께서 복습의 시간을 제안하셨다

포스팅보다는 내가 볼려고 .. 남기는 포스팅이라 두서 없을 수 있다 !

 

예상 질문과 답변만 정리해서 올릴 것이기 때문에
혹시 간단한 개념을 참고하고 싶다면 .. 아래 깃헙 repo 링크를 참고하면 좋을 것 같다 !

https://github.com/KangSuzy/CS-study.git

GitHub - KangSuzy/CS-study: 남은 상반기 기간 동안 CS 스터디를 진행합니다.

---

자료구조 질문 모음

# Array, LinkedList, Hash Table 예상질문

✅ 동적 할당 배열과 동적 배열의 차이가 무엇인가요? 

동적 할당 배열은 프로그램 중 언제든 마음대로 크기를 지정할 수 있지만 한 번 크기가 고정되면 바꿀 수 없습니다.
그에 반해 동적 배열은 크기가 고정되지 않은 배열을 의미합니다.

✅ 연결 리스트와 일반적인 배열 사이 차이점 중 하나는 크기가 고정되어 있는지 아닌지에 달렸습니다. 
그렇다면 크기를 동적으로 늘릴 수 있는 동적 배열과 연결 리스트는 어떻게 다를까요?

동적 배열과 연결 리스트 모두 크기가 정해져있지 않다는 공통점이 있습니다. 하지만 동적 배열은 저장할 때 원소들이 연속적으로 저장되고(메모리 주소가 연속되며) 인덱스 번호로 원소에 O(1)로 접근이 가능하지만, 연결 리스트는 노드의 포인터 영역이 다음 노드 주소를 가리키기 때문에, 메모리 주소가 반드시 연속적이지는 않다는 차이가 있습니다.

✅ 해시 함수를 돌리는 것을 제외하고 순수히 해시 함수의 삽입만 따지면 시간복잡도는 O(1)입니다. 왜 O(1)인가요?
해시 함수를 통과하는 key가 동일하다면 해시코드는 항상 동일하고, 해시코드와 값을 그냥 삽입하면 되기 때문에 O(1)입니다. 하지만 해시 충돌이 일어나면 모든 bucket들의 value를 검토해야 하기 때문에 최악의 경우 O(n)이 될 수도 있습니다.

 

# Graph, Tree, Trie 예상질문

✅ 그래프와 트리의 차이점에 대해 설명해주세요

그래프는 노드와 엣지로 이루어진 자료구조이며 네트워크 구조입니다. 루트 노드가 없고 부모-자식 관계라는 개념이 없습니다. 트리는 사이클이 없는 그래프로 계층적 구조입니다. 부모-자식 관계라는 개념이 있고 루트노드는 1개이며 모든 노드는 0개 이상의 자식 노드를 갖습니다.

 

✅ 이진탐색트리과 시간복잡도에 대해 설명해주세요

이진탐색트리는 이진 탐색과 연결리스트의 개념이 합쳐진 개념입니다. 따라서 효율적인 탐색 능력을 가지고 삽입, 삭제가 가능합니다. 부모 노드는 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작습니다.
시간복잡도는 균등 트리인 경우 O(logN), 편향 트리인 경우 O(N)입니다. N은 트리의 depth에 비례합니다.

 

✅ 트라이에 대해서 설명해주세요

트라이는 문자열에서 검색을 빠르게 도와주는 자료구조입니다. 문자열에서 이진 탐색트리를 이용하면 시간복잡도가 O(MlogN)인데 트라이를 이용하면 시간복잡도가 O(M)입니다.

 

# Stack, Queue, Heap 예상질문

✅ deque 에 대해 설명해주세요
양방향으로 삽입과 삭제가 가능하며 스택과 큐의 기능을 모두 가집니다 시간복잡도는 O(1) 입니다

 

✅ deque 의 시간복잡도가 O(1) 인 이유 ?
내부적으로 양방향 연결리스트이기 때문입니다

 

✅ 배열과 트리의 차이점을 설명해주세요
배열은 선형적으로 데이터를 담는 구조이고트리는 계층적으로 데이터를 표현하는 자료구조 입니다

 

✅ 배열로 이진트리를 구현하였을때 인덱스 ?
부모가 n인 경우 왼쪽 자식은 2n 오른쪽 자식은 2n+1 인덱스를 가집니다

 

✅ 스택과 큐의 활용에 대해 이야기해주세요

스택은 LIFO 특징을 갖고 있기 때문에 웹브라우저 방문기록이나 실행 취소 등에서 활용되고
큐는 FIFO 특징을 갖고 있기 때문에 프린트 출력과 같은 우선순위의 작업이나 주문 대기열 등에서 활용됩니다