[면접 준비-CS기초] 1. 자료구조와 알고리즘(1)

IT 기업 신입사원 면접에서 많이 질문하는 면접 질문 목록입니다. 자료구조와 알고리즘 관련 질문 중 스택, 큐, 데크 등 주요 자료구조에 대한 설명과 해시 테이블에 대한 설명입니다. 또한 순차 자료구조와 연결 자료구조의 차이점도 설명되어 있습니다.

 

자료구조와 알고리즘 면접 질문과 답변 정리

자료구조란?

자료구조란 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조입니다.

알고리즘이란?

알고리즘은 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다.

 

각 자료구조에 대한 설명

스택(Stack)

스택은 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조입니다. top위치의 원소에만 접근이 가능하기 때문에, 마지막에 삽입한 원소가 가장 먼저 삭제되는 Last-In-First-Out 구조입니다. 용어: top, push, pop

큐(Queue)

큐는 뒤에서는 삽입만 가능하고 앞에서는 삭제만 가능한 자료구조입니다. 따라서 가장 먼저 삽입된 원소가 가장 먼저 삭제되는 First-In-First-Out 구조입니다. 용어: front, rear, enqueue, dequeue

데크(Deque)

데크는 큐 두개를 좌우로 뒤집어서 붙인 구조로, 큐의 양쪽 끝에서 삽입과 삭제 모두를 수행할 수 있도록 확장한 자료구조입니다.

트리(Tree)

트리는 정점과 간선을 이용해 사이클을 이루지 않도록 구성한, 그래프의 특수한 형태입니다. 계층 관계를 갖는 데이터를 표현하기에 적합한 구조입니다.

힙(Heap)

힙은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 완전이진트리입니다. 각 노드의 키값이 자식의 키값보다 크거나 같은 경우는 최대 힙, 작거나 같은 경우는 최소 힙이 됩니다.

우선순위 큐(Priority Queue)

우선순위 큐는 가장 우선 순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로는 힙을 사용합니다.

 

최소비용 신장트리(MST: Minimum Spanning Tree)

신장 트리는 N개의 정점으로 이루어진 무방향 그래프에서, N개의 모든 정점과 N-1개의 간선으로 만들어진 트리입니다.

최소비용 신장 트리는 신장 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 최소비용 신장 트리를 만드는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

크루스칼 알고리즘

크루스칼 알고리즘은 매 차례마다 가중치가 낮은 간선을 삽입하거나 가중치가 높은 간선을 삭제하는 방식으로 MST를 만드는 알고리즘입니다. 간선을 오름차순 또는 내림차순으로 정렬하여 선택하는데, 사이클이 생성되지 않게 하기 위해 매번 사이클 생성 여부를 판단해야 합니다.

프림 알고리즘

• 프림 알고리즘은 하나의 시작 정점을 기준으로 트리를 점점 확장해가는 알고리즘입니다. 선택된 정점들과 선택되지 않은 정점들을 연결하는 간선들 중 가중치가 최소인 간선으로 연결된 정점을 새로 선택하며, 모든 정점이 선택될 때까지 반복합니다.
• 프림 알고리즘은 이미 선택된 정점을 다시 선택하지 않기 때문에, 사이클 생성 여부를 판단하지 않아도 됩니다.

크루스칼 알고리즘은 가중치를 기준으로 간선을 정렬해야 하기 때문에 간선의 개수가 많지 않은 경우에 적합하며, 간선의 개수가 많을 때는 프림 알고리즘을 사용하는 것이 적합합니다.

 

해시 테이블(Hash Table)

• 해시 테이블은 <key, value>로 데이터를 저장하는 자료구조 중 하나로, 빠른 데이터 검색이 필요할 때 유용합니다. key값에 대해서 해시 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 위치로 바로 이동하여 값을 꺼내오는 구조입니다.
• 고유한 인덱스로 값을 조회하기 때문에 평균적으로 O(1)의 시간 복잡도를 갖습니다.
• 그러나 해시함수를 통해 계산된 주소값이 충돌하는 경우 chaining 방식 또는 open addressing 방식 등으로 충돌을 해결할 수 있지만, 최악의 경우에는 모든 저장공간을 방문해야 하기 때문에 시간 복잡도가 O(n)까지 늘어날 수 있습니다.
• chaining 방식: 해시 테이블의 각 인덱스의 저장공간을 연결 리스트로 구현. 충돌이 발생해도 노드를 하나 추가하면 됨.
• open addressing 방식: 주소값이 충돌하면 비어있는 주소를 찾아서 그 공간에 저장.

 

순차 자료구조(ArrayList)와 연결 자료구조(LinkedList)의 차이점

• 순차 자료구조는 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장하는 방식으로, 데이터의 논리적인 순서와 물리적인 순서가 일치합니다.
• 연결 자료구조는 물리적 위치가 논리적인 순서와 상관없이 저장되며, 링크에 의해서 논리적인 순서를 표현하는 방식입니다.
• 순차 자료구조는 원하는 데이터에 무작위로 접근할 수 있지만, 연결 자료구조는 순차적인 접근만 가능합니다.
• 순차 자료구조는 리스트의 크기가 제한되어있으며, 리스트의 크기를 재조정하려면 많은 연산이 필요합니다. 반면 연결 자료구조는 링크 정보를 변경하여 추가/삭제 연산을 빠르게 수행할 수 있습니다.

 

여기까지 자료구조와 알고리즘에 대한 면접 질문 1편이었습니다. 다음 글에서는 이어서 자료구조와 알고리즘에 대한 질문들을 더 작성해보겠습니다. 취준생과 이준생들에게 많은 도움이 되기를!

 

다음 글

[면접 준비-CS기초] 1. 자료구조와 알고리즘(2)