자료구조 면접 질문 리스트, 기출 모음(신입 면접, 대학원)

질문만 모음

트리와 그래프의 차이에 대해서 설명하시오
그래프 탐색 방법에 대해서 설명하시오
Heap이 무엇인지 설명하시오
Heap 자료구조에서 데이터 추출시에 시간복잡도가 어떻게 되는지 설명하시오
본인이 생각하는 가장 효율적인 정렬과 그것의 시간복잡도가 어떻게 되는지 설명하시오
탐욕 알고리즘과 동적 계획법을 각각 설명하시오
Stack과 Queue에 대해서 설명하시오
Stack과 Queue의 실사용 예시
List, Set, Map에 대해서 각각 설명하시오
Array, ArrayList, LinkedList에 대해서 각각 설명하시오
Array를 적용시키면 좋은 데이터는?
HashMap과 HashTable에 대해 설명하시오
우선순위 큐에 대해서 설명하시오
BST(Binary Search Tree)와 Binary Tree에 대해 설명하시오
RBT(Red-Black Tree)에 대해 설명하시오

 

---

# first

자료구조에 대해서 아는 것을 모두 말해보시오

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 구조입니다. 대표적으로 배열과 리스트, 스택과 큐 등이 있습니다.

 

그 외에 자료구조

배열(Array): 고정 크기, 연속된 메모리

리스트(List): 동적 크기, arrayList, LinkedList 등 존재

스택(Stack): LIFO(Last In First Out) 구조

큐(Queue): FIFO(First In First Out) 구조

해시 테이블(Hash Table): 키-값 기반 데이터 매핑

트리(Tree): 계층적 구조, 루트와 자식 노드로 구성

 

트리와 그래프의 차이에 대해서 설명하시오

트리: 비순환 그래프, 하나의 루트에서 모든 노드가 연결되는 형태

그래프: 정점과 간선으로 이루어진 형태 경우에 따라 방향/무방향 그래프, 가중치를 부여한 그래프, 순환 되거나 미순환 되는 형태의 그래프 등이 있습니다.

 

그래프 탐색 방법에 대해서 설명하시오

DFS(깊이 우선 탐색): 스택 또는 재귀를 사용해 한 경로를 끝까지 탐색한 후 같은 방식으로 다른 경로를 탐색해나가는 탐색 방법, 경로 찾기 등에 유리

BFS(너비 우선 탐색): 큐를 사용해 레벨 단위로 탐색해나가는 방법, 최단 거리 탐색에 유리

 

인접 리스트 사용 시 두 탐색 모두 O(V+E)의 시간복잡도, 인접행렬 사용 시 O(v2)의 시간복잡도를 갖습니다.

 

Heap이 무엇인지 설명하시오

최댓값 혹은 최솟값을 빠르게 찾기 위해 사용되는 완전 이진트리 기반의 자료구조입니다

삽입/삭제 시 높이에 비례해 작업이 수행되며 높이는 log₂(n)이며, O(log n)의 시간복잡도를 갖습니다.

 

최대 힙: 부모 노드가 자식보다 크거나 같음(트리의 맨 위 값이 가장 크고 내려갈수록 작아짐)

최소 힙: 부모 노드가 자식보다 작거나 같음(트리의 맨 위 값이 가장 작고 내려갈수록 커짐)

 

Heap 자료구조에서 데이터 추출시에 시간복잡도가 어떻게 되는지 설명하시오

O(log n)

루트 노드 추출 후 마지막 노드를 이동시키고 재정렬 수행

* 어떻게 동작하길래 log n일까?

 

본인이 생각하는 가장 효율적인 정렬과 그것의 시간복잡도가 어떻게 되는지 설명하시오

병합정렬(Merge Sort)와 퀵정렬(Quick Sort) 평균 시간 복잡도가 O(n log n)으로 효율적입니다.

병합정렬은 안정적이고 퀵정렬은 메모리 사용량이 적다는 장점이 있습니다.

* 안정적이라는게 어떤 의미일까? -> 정렬 전 동일한 값의 상대적 순서가 정렬 후에도 유지되는 성질

 

탐욕 알고리즘과 동적 계획법을 각각 설명하시오

탐욕 알고리즘은 현재 단계에서 최적의 선택을 하여 문제를 해결하는 것입니다.

동적 계획법은 문제를 작은 하위 문제로 나누고 결과를 저장하여 중복 계산을 방지하는 것입니다.

 

Stack과 Queue에 대해서 설명하시오

Stack: LIFO 구조, 재귀 호출 스택, 괄호 검증에 사용

Queue: FIFO 구조, 작업대기열, BFS 등에 사용

 

Stack과 Queue의 실사용 예시

Stack: 함수호출, 브라우저 웹 페이지 뒤로가기

Queue: 은행 대기 시스템, BFS 탐색, 작업스케줄링

 

 

# second

List, Set, Map에 대해서 각각 설명하시오

List: 중복 허용, 순서 보장

Set: 중복 불허용, 순서 미보장

Map: 중복 불허용, 순서 미보장, 키-값 형태로 저장

 

Array, ArrayList, LinkedList에 대해서 각각 설명하시오

Array: 고정 크기, 메모리 연속성, 인덱스 접근 가능 O(1), 삽입, 삭제 시 느림 O(n), 불변 크기, 기본 자료형만 저장 가능

ArrayList: 동적 크기, 유연성 제공, 객체만 저장 가능, 

LinkedList: 동적 크기, 검색시 인덱싱 접근 불가 모두 타고 가야함 O(n), 노드 위치를 알고 있는 경우 삽입 삭제 빠름 O(1), 메모리 불연속성(메모리 오버헤드 존재)

 

Array를 적용시키면 좋은 데이터는?

고정된 크기의 데이터를 저장하여 사용하는 경우 (ex: 날짜 데이터)

만약 Array를 사용하지 않는다면 메모리 효율성이 저하될 수 있음

 

HashMap과 HashTable에 대해 설명하시오

HashMap: 키-값 매핑 구조, 동기화되지 않음, 데이터 검색/삽입 빠름 O(1), 충돌 발생시 체이닝 또는 오픈 어드레싱으로 해결, key와 value에 null 허용

HashTable: 키-값 매핑구조, 동기화됨, null 허용x

* 동기화가 뭔데 -> 멀티스레드 환경에서 동일한 객체를 여러 스레드가 동시 접근할 때 충돌을 방지하기 위한 메커니즘

 

우선순위 큐에 대해서 설명하시오

요소를 우선순위에 따라 제공할 수 있는 큐(힙 기반, 이진 탐색 트리로 우선순위 큐 구현 가능)

작업 스케줄링, 다익스트라 최단 경로 탐색 등에 사용

삽입 삭제 O(log n)

 

 

# third (심화)

BST(Binary Search Tree)와 Binary Tree에 대해 설명

RBT(Red-Black Tree)에 대해 설명

 

 

 

 

 

질문참고

• https://hip-studyrecord.tistory.com/45
• https://mangkyu.tistory.com/89
• https://dev-coco.tistory.com/159