[자료구조] 6월 3주차 기술면접 질문 정리

---

기술면접 스터디에서 받은 질문을 복습하기 위한 용도로 정리한 내용입니다.

 

스택으로 큐를 구현하고, 큐로 스택을 구현하는 방법은 무엇인가요?

스택으로 큐를 구현하기 위해서는 2개의 스택이 필요합니다. 첫 번째 스택에 데이터를 넣고,  데이터를 뺄 때는 첫 번째 스택의 모든 데이터를 두 번째 스택으로 옮깁니다. 그렇게 하면 첫 번째 스택의 역순으로 두 번째 스택에 데이터가 저장될 것이고, 두 번째 스택에 있는 데이터를 하나씩 빼면 큐의 pop() 연산을 하는 것과 같은 결과가 나올 것입니다. 반대로 큐로 스택을 구현하기 위해서는 큐에 데이터를 넣고, 맨 위의 데이터가 나오기 전까지 데이터를 빼서 다시 큐에 넣습니다. 이 과정을 반복하면 스택을 구현할 수 있습니다.

힙이란 무엇인가요?

힙이란 완전 이진 트리의 한 종류로, 최대 힙과 최소 힙이 있습니다. 최대 힙은 부모 노드의 값이 자식 노드의 값보다 큰 것을 말하고 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 것을 말합니다.최대 힙과 최소 힙을 이용해 최댓값과 최솟값을 빠르게 찾을 수 있어서 우선순위 큐를 구현하거나 힙 정렬을 하는 데 주로 사용됩니다.

그래프를 구현하는 방법은 무엇인가요?

그래프를 구현하는 방법에는 인접 행렬을 이용하는 방법과 인접 리스트를 이용하는 방법이 있습니다. 인접 행렬은 2차원 배열을 이용하여 그래프를 구현하는 방법으로, 간선의 수가 많은 밀집 그래프에서 주로 사용됩니다. 새로운 간선을 추가하고 제거하는 것이 O(1)의 시간 복잡도로 빠르다는 장점이 있지만 정점이 많은 그래프에서는 비효율적일 수 있습니다. 인접 리스트는 연결 리스트를 이용하여 그래프를 구현하는 방법으로, 간선의 수가 적은 희소 그래프에서 주로 사용됩니다. 특정 노드에 인접한 노드를 찾을 때 인접 배열보다 더 빠르게 찾을 수 있지만 두 노드 간의 간선 존재 여부를 확인하는 데 O(N)의 시간 복잡도가 걸릴 수 있습니다.

Array의 특징과 Array에 적합한 데이터는 무엇인가요?

배열은 연속된 메모리 공간에 데이터를 저장하고, 인덱스로 특정 원소에 O(1)의 시간 복잡도로 접근할 수 있습니다. 삭제나 삽입 과정에서는 그 위치의 원소를 삽입 혹은 삭제한 뒤 전체적으로 Shift 해줘야하기 때문에 O(n)의 시간 복잡도를 갖습니다. 따라서 데이터의 접근이 빈번하게 일어난다면 Array를 사용하는 것이 더 적합합니다.

List와 Set의 차이점은 무엇인가요?

List는 순서가 있고 중복을 허용하는 자료구조입니다. 인덱스로 원소에 접근이 가능하고 크기가 가변적입니다. 반면 Set은 순서가 없고 중복을 허용하지 않는 자료구조입니다. 빠른 검색 속도를 가지며 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다.

HashMap과 Hashtable의 차이점은 무엇인가요?

HashMap은 Map 클래스를 구현하기 위해 HashTable을 사용한 클래스로 key와 value에 null이 허용되며 동기화를 지원하지 않습니다. 반면 HashTable은 null이 허용되지 않으며 동기화를 지원합니다. 또한 HashMap보다 속도가 빠릅니다.