자료구조
문제 1
유형: OX형
문제: 연결 리스트는 연속된 메모리 공간을 차지해야 한다.
정답 확인하기
정답: X
해설: 연결 리스트는 동적 메모리 할당을 사용하여 연속되지 않은 메모리 공간을 차지할 수 있음. 따라서 배열과 달리 크기를 미리 정할 필요가 없음.
문제 2
유형: OX형
문제: 해시 테이블의 충돌 해결 방법으로 체이닝과 개방 주소법이 있다.
정답 확인하기
정답: O
해설: 해시 테이블에서 같은 해시 값을 가지는 키가 여러 개 나올 수 있음. 이를 해결하기 위해 체이닝(연결 리스트 사용)과 개방 주소법(빈 슬롯 탐색)이 있음.
문제 3
유형: OX형
문제: 배열에서 요소를 삭제할 때 O(1) 시간 복잡도를 가진다.
정답 확인하기
정답: X
해설: 배열에서 중간의 요소를 삭제할 경우, 삭제된 요소 뒤에 있는 모든 요소들이 한 칸씩 왼쪽으로 이동해야 하므로 시간 복잡도가 O(n)이 됨
문제 4
유형: 객관식
문제: 문제: 다음 중 큐(Queue)의 특징으로 옳은 것을 모두 고르시오.
보기:
- 후입선출(LIFO) 방식으로 동작한다.
- 선입선출(FIFO) 방식으로 동작한다.
- 삽입(Enqueue)과 삭제(Dequeue) 연산이 있다.
- 큐는 배열 또는 연결 리스트로 구현될 수 있으며, 상황에 따라 원형 큐 방식이 사용되기도 한다.
- 우선순위 큐는 일반적인 큐와 동일한 방식으로 요소를 제거한다.
정답 확인하기
정답: 2, 3, 4
해설:
- 큐는 선입선출(FIFO) 구조
- 삽입(O(1)),삭제(O(1))가 가능하다.
- 큐는 배열 또는 연결 리스트로 구현되며 상황에 따라 원형 큐 방식도 사용
- 우선순위 큐는 FIFO가 아니라, 우선순위에 따라 요소를 제거하는 방식
문제 5
유형: 객관식
문제: 다음 중 이진 탐색 트리(BST)의 특징으로 옳은 것은?
보기:
- 부모 노드의 왼쪽 자식은 부모보다 크고, 오른쪽 자식은 부모보다 작다.
- 모든 서브트리도 이진 탐색 트리의 성질을 만족해야 한다.
- 중위 순회를 하면 항상 오름차순으로 정렬된 값을 얻을 수 있다.
- 이진 탐색 트리는 항상 균형 잡힌 구조를 가진다.
- 모든 이진 탐색 트리는 최소 힙의 성질을 만족한다.
정답 확인하기
정답: 2, 3
해설:
- 이진 탐색 트리의 기본 성질을 왼쪽 자식 < 부모 < 오른쪽 자식
- 모든 서브트리도 이진 탐색 트리의 성질을 가져야함
- 이진 탐색 트리를 중위 순회 하면 항상 오름차순 정렬된 값이 나옴
- 이진 탐색 트리는 균형 잡혀 있을 수도 있지만, 불균형할 수도 있음
- 힙구조와 이진 탐색 트리는 별개
문제 6
유형: 객관식
문제: 다음 중 해시 테이블(Hash Table)의 특징으로 옳은 것을 모두 고르시오.
보기:
- 키(Key)와 값(Value) 쌍을 저장하는 자료구조이다.
- 평균적으로 O(n)의 탐색 속도를 가진다.
- 해시 충돌은 방지할 수 있다.
- 체이닝 기법은 충돌 해결 방법 중 하나이다.
- 해시 테이블은 항상 오름차순으로 정렬된 데이터를 반환한다.
정답 확인하기
정답: 1,4
해설:
- 해시 테이블은 (Key, Value) 쌍을 저장
- 평균적으로 O(1)의 탐색 속도를 가지며, 최악의 경우 O(n)
- 해시 충돌은 완전히 방지할 수 없으며 체이닝 기법이나 개방 주소법을 사용해 확률을 낮춤
- 해시 테이블은 정렬되지 않은 상태에서 저장됨, 항상 정렬된 데이터를 반환하지 않음
문제 7
유형: 객관식
문제: 다음 중 그래프(Graph)의 특징으로 옳은 것을 모두 고르시오.
보기:
- 그래프는 정점(Vertex)과 간선(Edge)으로 구성된다.
- 그래프는 항상 방향성이 존재한다.
- 인접 리스트와 인접 행렬 방식으로 구현할 수 있다.
- DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘이 사용된다.
- 무방향 그래프에서는 모든 간선이 양방향이다.
정답 확인하기
정답: 1,3,4,5
해설:
- 그래프는 방향 그래프와 무방향 그래프로 나뉨, 항상 방향성을 갖는다는 것은 틀림
- 그래프의 구성 요소는 정점(Vertex)과 간선(Edge)
- 그래프는 인접 리스트 또는 인접 행렬로 구현할 수 있음
- 그래프 탐색을 위해 DFS와 BFS 알고리즘이 활용됨
- 무방향 그래프에서는 모든 간선이 양방향으로 연결됨
문제 8
유형: 서술형
문제: 연결 리스트에서 단일 연결 리스트와 이중 연결 리스트의 차이점을 설명하시오.
정답 확인하기
정답: 키워드 : 방향, 메모리 단일 연결 리스트와 이중 연결 리스트는 모두 노드를 연결하여 데이터를 저장하는 선형 자료구조이지만, 각 노드의 링크 구조에서 차이가 있습니다.
단일 연결 리스트
- 단일 연결 리스트에서는 각 노드가 데이터와 하나의 포인터(또는 링크)를 가지고 있습니다. 이 포인터는 다음 노드를 가리키며, 리스트를 한 방향으로만 순차적으로 탐색할 수 있습니다. 즉, 한 번 리스트를 탐색하면 다시 처음으로 돌아가는 것이 불가능합니다. 이 구조는 추가적인 메모리 공간을 절약할 수 있지만, 양방향 탐색이 불가능하다는 단점이 있습니다.
이중 연결 리스트
- 이중 연결 리스트에서는 각 노드가 데이터와 두 개의 포인터를 가지고 있습니다. 하나는 다음 노드를 가리키고, 다른 하나는 이전 노드를 가리킵니다. 이를 통해 리스트를 양방향으로 탐색할 수 있는 장점이 있습니다. 즉, 앞에서부터 뒤로, 뒤에서부터 앞으로 모두 탐색할 수 있습니다. 이 구조는 단일 연결 리스트보다 메모리를 더 많이 사용하지만, 양방향 탐색이 가능해 더 유연한 데이터 처리와 더 빠른 삽입/삭제가 가능해집니다.
해설:
문제 9
유형: 서술형
문제: 트리 구조에서 이진 탐색 트리와 균형 이진 탐색 트리의 차이점을 설명하시오.
정답 확인하기
정답: 키워드 : 성능, 동작 이진 탐색 트리와 균형 이진 탐색 트리는 모두 이진 트리의 일종으로, 트리 구조에서 효율적인 탐색을 목적으로 사용됩니다. 그러나 두 가지는 성능과 동작에서 중요한 차이점을 가집니다.
이진 탐색 트리
- 이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 트리의 왼쪽 자식은 항상 부모보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 가집니다. 이 규칙을 따르면 트리에서 원하는 값을 효율적으로 찾을 수 있습니다. 하지만, 이진 탐색 트리는 데이터를 삽입할 때 정렬된 순서대로 삽입하면 트리가 편향될 수 있습니다. 예를 들어, 이미 정렬된 데이터를 순차적으로 삽입하면 트리가 한쪽으로 치우친 편향 트리가 되며, 이 경우 트리의 높이가 O(n)으로 증가하고, 탐색, 삽입, 삭제의 시간 복잡도가 최악의 경우 O(n)에 이를 수 있습니다. 이런 상황에서는 트리의 효율성이 크게 떨어집니다.
균형 이진 탐색 트리
- 균형 이진 탐색 트리는 트리의 높이를 자동으로 조절하여 항상 트리의 높이가 O(log n) 수준을 유지하도록 하는 트리입니다. 트리의 균형을 유지하는 알고리즘을 통해 삽입과 삭제가 이루어지며, 예를 들어 AVL 트리나 레드-블랙 트리 등이 이에 해당합니다. 이러한 균형을 유지함으로써 트리의 깊이가 항상 최소화되고, 트리의 탐색, 삽입, 삭제 시간이 모두 O(log n)으로 일정하게 유지됩니다. 균형 이진 탐색 트리는 트리의 성능을 보장할 수 있기 때문에 이진 탐색 트리보다 안정적인 탐색 성능을 제공합니다.
해설:
문제 10
유형: 서술형
문제: 해시 테이블의 충돌 처리 방법 중 체이닝 방법에 대해 설명하고, 이 방법이 어떤 상황에서 유리한지 서술하시오.
정답 확인하기
정답: 키워드 : 어떤 방식으로 저장하는 방식인지, 어떤 상황에서 쓰이는지
체이닝 기법은 해시 테이블에서 충돌을 처리하는 방법 중 하나로, 해시 값이 동일한 요소들을 하나의 링크드 리스트로 묶어서 저장하는 방식입니다. 각 버킷은 여러 요소를 저장할 수 있는 연결 리스트를 가집니다. 새로운 값이 동일한 해시 값을 가지면 해당 버킷에 연결 리스트의 형태로 추가됩니다. 체이닝 방식은 버킷 크기가 충분히 크고, 충돌이 많은 경우에 유리합니다. 예를 들어, 해시 함수가 잘 작동하지 않거나 데이터 분포가 고르게 이루어지지 않은 경우, 충돌이 많이 발생할 수 있는데, 이때 체이닝은 여러 값을 한 버킷에 저장할 수 있어 유용하게 작동합니다. 반면, 버킷 수가 너무 적거나 연결 리스트가 커지면 검색 시간이 길어질 수 있습니다.
문제 11
유형: 객관식
문제: 스택(Stack)에 관한 설명으로 옳은 것을 모두 고르시오.
보기:
- 스택은 선입선출(FIFO) 구조를 가진다.
- 스택의 기본 연산에는 push, pop, peek(top) 등이 있다.
- 스택에서 데이터 삽입 및 삭제는 모두 O(1)의 시간 복잡도를 가진다.
- 스택의 중간에 있는 요소에 직접 접근하는 것이 가능하다.
- 스택은 함수 호출 관리, 괄호 검사, 웹 브라우저의 뒤로가기 기능에 활용된다.
정답 확인하기
정답: 2, 3, 5
해설:
1: 스택은 후입선출(LIFO) 구조로, 가장 최근에 들어온 데이터가 가장 먼저 나가는 특성을 갖는다. 4: 스택은 맨 위의 요소에만 접근 가능하다.
문제 12
유형: 서술형
문제: 트리와 그래프의 공통점과 차이점에 대해 설명해주세요.
정답 확인하기
정답: 공통점으로는 둘 다 정점과 간선으로 이루어진 비선형 자료구조인 점이고, 차이점으로는 트리는 그래프의 일부로 사이클이 허용되지 않는 그래프이고, 그래프는 사이클이 허용됩니다.
참고자료: 책 면접을 위한 CS 전공지식 노트
문제 13
유형: 서술형
문제: Array를 적용시키면 좋을 데이터의 예를 구체적으로 들어주세요. 구체적 예시와 함께 Array를 적용하면 좋은 이유, 그리고 Array를 사용하지 않으면 어떻게 되는지 함께 설명해주세요.
정답 확인하기
정답:
순서가 중요하다는 것과 그에 상응하는 예시를 들 수 있음이 중요
- Array를 적용시키면 좋은 예로 주식 차트가 있습니다.
- 주식 차트에 대한 데이터는 요소가 중간에 새롭게 추가되거나 삭제되는 정보가 아니며, 날짜별로 주식 가격이 차례대로 저장되어야 하는 데이터입니다.
- 즉, 순서가 굉장히 중요한 데이터이므로 Array 같이 순서를 보장해주는 자료구조를 사용하는 것이 좋습니다. Array를 사용하지 않고 순서가 없는 자료 구조를 사용하는 경우에는 날짜별 주식 가격을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야 하는 번거로움이 발생합니다.
참고 자료: 신입 개발자 기술면접 질문 정리 - 자료구조
문제 14
유형: 서술형
문제: 이진 탐색 트리에서 최악의 경우 트리의 구조와 이때 시간 복잡도를 설명해주세요. 그리고 이 문제를 해결하기 위한 트리 구조를 설명해주세요.
정답 확인하기
정답: 루트 노드부터 시작해서, 노드가 한쪽으로만 계속 추가되어 선형 트리가 생성된다면 O(n)의 시간복잡도를 가지게 됩니다. 예를 들어 계속 더 작은 값만 추가하거나, 더 큰 값만 추가하는 경우 입니다. 이를 방지하기 위해 트리의 균형을 유지하여 시간 복잡도를 O(log N)으로 보장하는 AVL 트리와 레드-블랙 트리가 있습니다.
참고자료: 책 면접을 위한 CS 전공지식 노트
문제 15
유형: 서술형
문제: 다음 트리를 중위순회(Inorder Traversal)의 결과를 쓰시오.
정답 확인하기
정답: DBAECFG
해설: 중위순회는 왼쪽 자식 노드, 루트 노드, 오른쪽 자식 노드 순으로 순회하는 방식이다.
참고 : 전위순회(Preorder)는 루트노드, 왼쪽 자식 노드, 오른쪽 자식 노드순으로 순회한다.
후위순회(Postorder) 는 왼쪽 자식 노드, 오른쪽 자식 노드, 루트 노드 순으로 순회한다.
문제 16
유형: OX문제
문제: 힙(Heap) 자료구조는 최솟값 또는 최댓값을 O(log n) 시간 복잡도로 찾을 수 있다. (O/X)
정답 확인하기
정답: X
해설: 힙(Heap)에서는 최솟값 또는 최댓값을 O(1) 시간에 찾을 수 있다.(루트 노드에 위치). 삽입과 삭제는 O(log n) 시간이 걸린다.