신입 개발자 기술면접 : 자료구조 01 이론

🗣️ 신입 인터뷰/자료구조

신입 개발자 기술면접 : 자료구조 01 이론

쫀냠 2023. 12. 18. 16:17

[자료구조 02 코드] 포스트에서는 C++ 언어로 자료구조 관련 문제를 풀이해 봅니다.

🗣️ 배열과 연결 리스트의 차이점이 뭔지 아는대로 설명해주실래요?

배열과 연결 리스트는 데이터를 저장하기 위한 자료구조로, 데이터 저장 방식에 큰 차이가 있습니다.

배열은 연속된 메모리 공간에 데이터를 순차적으로 미리 할당된 크기만큼 저장합니다. 그래서 특정 인덱스의 데이터에 즉시 접근 (random access `O(1)`) 할 수 있어서 읽는 속도가 빠릅니다. 하지만 데이터 삭제 또는 삽입 시 요소들의 인덱스를 수정해야 해서 비교적 시간이 오래 걸립니다.

반면에 연결리스트는 노드를 이용해 메모리 공간에 데이터를 불연속적으로 저장하여 논리적 연속성을 보장합니다. 각 노드는 데이터와 다음 노드의 주소 값을 저장하고 있어서 임의 접근을 하지 못하고 순차적으로 접근할 수 있습니다. 배열과 달리 인덱스가 없으므로 한 번에 특정 데이터에 접근할 수 없고 해당 인덱스에 도달하기까지 `O(n)`의 시간이 걸립니다. 그러나 데이터의 삽입과 삭제 시 노드가 가리키는 주소 값만 변경하면 되어서 `O(1)`의 시간복잡도를 가진다는 장점이 있습니다. 그러나 이것도 주소를 기억하고 있을 때에나 `O(1)`이고, 실질적으로 추가/삭제하려는 인덱스까지 도달하는 데 `O(n)`의 시간이 걸립니다.

배열의 주된 장점은 데이터 접근과 append 가 빠르다는 것이지만, 메모리 낭비라는 단점이 있습니다. 배열은 선언시에 fixed size를 설정하여 메모리 할당을 합니다. 즉, 데이터가 저장되어 있지 않더라도 메모리를 차지하고 있으므로 메모리 낭비가 발생합니다.

이와 반면 연결리스트는 Runtime 중에서도 size 를 늘리고 줄일 수 있습니다. 데이터가 추가되는 시점에서 메모리를 할당하기 때문에 모미를 좀 더 효율적으로 사용할 수 있습니다. 그래서 initial size 를 고민할 필요가 없고, 필요한 만큼 memory allocation을 하여 메모리 낭비가 없습니다.

🗣️ 스택과 큐는 어떤 경우에 주로 사용하나요?

스택은, 선입후출의 특성을 가진 자료구조입니다. 스택을 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주로 배열을 통해 구현합니다. 스택이 실제로 사용되는 부분은 브라우저의 '뒤로가기' 기능이나, 메모리 영역의 스택 영역 에 사용됩니다. 즉 프로그램을 실행할 때 함수를 수행한 후 돌아가야 하는 주소 값을 저장하는 용도로 사용하기도 합니다.

큐는, 선입선출의 특성을 가진 자료구조입니다. 큐를 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주로 연결리스트를 통해 구현합니다. 큐가 실제로 사용되는 부분은 프린터 큐, CPU 스케줄링의 Ready Queue 등에 사용됩니다.

🗣️ 우선순위 큐는 무엇인가요?

선입선출의 구조를 가진 큐와 다르게, 우선순위가 높은 원소부터 우선적으로 빠져나오게 되는 자료구조입니다. 각 요소가 우선순위를 가집니다. 우선순위 큐를 활용해 정렬하거나 다익스트라 알고리즘을 구현할 때 사용합니다. 우선순위 큐는 배열, 연결리스트, 힙으로 구현할 수 있으먀, 일반적인 경우에는 주로 삽입과 삭제 연산이 모두 `O(logN)` 이 보장된 힙 자료구조를 이용해 구현합니다.

🗣️ 힙이란 무엇인가요?

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

🗣️ 힙의 삽입,삭제를 설명해주세요!

두 연산 모두 모두 트리의 높이만큼 즉 `O(logN)` 의 시간복잡도를 가집니다. 최악의 경우에도 `O(logN)` 이 보장됩니다.

힙에 데이터를 삽입할 때는, 힙의 맨 끝에서 이루어집니다. 부모 노드와 우선순위(최댓값 또는 최솟값)를 비교해 부모 노드보다 우선순위가 높으면 위치를 바꾸면서 루트 노드까지 비교합니다.

힙에서 데이터 삭제는 우선순위가 가장 높은 노드를 삭제하는 연산입니다. 즉, 루트 노드를 삭제하게 됩니다. 삭제한 후에는 루트 노드 자리에 힙의 마지막 노드(마지막 레벨의 가장 오른쪽 노드)를 옮긴 후 힙을 재정렬합니다.

삽입 및 삭제를 하면 힙의 구조가 무너지게 되는데, 다시 Heap 으로 만드는 과정을 Heapify 라고 합니다.

🗣️ 힙이 할 수 있는 것을 균형이진트리가 할 수 있지 않나요?

공통점: 힙과 균형 이진 트리 모두 이진 트리 기반의 구조이며, 삽입과 삭제 연산이 로그 시간 복잡도를 가집니다.

차이점: 힙은 트리의 최상단(루트)에 있는 요소에 대한 빠른 접근(최대값 또는 최소값)에 중점을 둔 반면, 균형 이진 트리는 트리 내의 모든 요소에 대한 빠른 검색에 중점을 둡니다.

특정 상황에서, 예를 들어 우선순위 큐 구현 시, 힙과 균형 이진 트리는 상호 대체 가능할 수 있습니다. 그러나 각각의 자료 구조가 가진 특성에 따라 성능 차이가 발생할 수 있습니다.

힙과 균형 이진 트리는 둘 다 이진 트리 기반의 자료 구조이지만, 각각의 특성과 최적화된 용도가 다릅니다. 힙은 최대값 또는 최소값에 빠르게 접근하는 데 최적화되어 있고, 균형 이진 트리는 트리 내의 모든 요소에 대한 빠른 검색, 삽입, 삭제 연산에 적합합니다. 따라서 특정 애플리케이션의 요구 사항에 따라 적절한 자료 구조를 선택하는 것이 중요합니다.

🗣️ 이진탐색트리 삽입, 삭제 과정은 어떻게 이뤄지나요?

삽입: 루트 노드부터 차례대로 값을 비교해 나가면서 삽입할 자리를 찾는 방식입니다. 추가하려는 데이터가 비교하는 노드보다 값이 큰 경우는 오른쪽 자식 노드와 비교를 수행하고, 작은 경우는 왼쪽 자식 노드와 비교를 수행합니다.

삭제: 자식노드의 개수에 따라 3가지로 나눌 수 있습니다.

자식 노드가 없다: 해당 노드만 삭제하면 된다.
자식 노드가 1개: 자식 노드를 삭제한 노드의 위치로 옮기면 된다.
자식 노드가 2개: 오른쪽 서브 트리에서 가장 작은 값을, 삭제한 노드 위치로 옮기면 된다. 또는 왼쪽 서브 트리에서 가장 큰 값을 삭제한 노드 위치로 옮겨도 된다.

🗣️ 이진 탐색 트리, 포화 이진 트리, 완전 이진 트리의 차이점은 무엇인가요?

이진 트리는 자식 노드를 최대 2개까지 가질 수 있는 트리를 의미합니다. 3가지 모두 이진 트리이지만, 서로 다른 특징이 있습니다.

먼저 이진 탐색 트리는 모든 노드에 대해 왼쪽 서브 트리는 해당 노드보다 작은 값을 가지고, 오른쪽 서브 트리는 해당 노드보다 큰 값을 갖습니다. 데이터의 빠른 검색을 위해 만들어진 트리 자료구조입니다.
포화 이진 트리는 트리의 마지막 레벨까지 모든 노드가 채워져 있습니다.
마지막으로 완전 이진 트리는 트리의 마지막 레벨을 제외한 나머지 레벨에 모든 노드가 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 노드가 채워져 있습니다.

🗣️ 이진 탐색 트리에서 발생할 수 있는 문제는 무엇이고, 이를 보완할 수 있는 방법이 있다면 무엇인가요?

평균적으로 `O(logN)`의 시간복잡도를 가지지만, 이진 탐색 트리에서 불균형이 발생하면 시간 복잡도 면에서 효율적이지 못하다는 문제점이 있습니다. 예를 들어, 트리가 한쪽으로 편향되어 있는 최악의 경우에 `O(n)`의 시간 복잡도가 소요될 수 있습니다.

이를 보완하기 위해 등장한 방법이 균형 이진 트리 탐색 트리입니다. 대표적인 예로, 레드-블랙 트리와 AVL 트리가 있습니다.

🗣️ 트리와 그래프의 차이점은 무엇인가요?

그래프는 정점과 간선으로 구성된 자료구조입니다. 방향 그래프와 무방향 그래프 모두 존재하며, 사이클은 있을 수도, 없을 수도 있습니다. 또한, 계층 관계가 없습니다. 반면에 트리는 그래프의 한 종류로, 방향성이 있으면서 사이클이 존재하지 않습니다. 또한, 계층 관계가 있어서 부모 노드와 자식 노드라는 관계성과 루트 노드라는 개념이 존재합니다.

그래프는 트리보다 더 포괄적인 개념입니다. 즉, 트리는 그래프라고 부를 수 있으나 모든 그래프를 트리라고 부를 순 없습니다.

🗣️ BFS와 DFS의 차이점은 무엇인가요?

두 그래프 모두 탐색을 수행할 때 사용합니다.

BFS는 너비 우선 탐색으로, 하나의 노드에서 시작해 가까운 노드들을 먼저 탐색합니다. 큐로 구현할 수 있고, 비가중치 그래프에서 각 노드까지의 최단 거리를 알 수 있습니다. (예: 소문)

DFS는 깊이 우선 탐색으로, 하나의 노드에서 시작해 최대 깊이까지 탐색을 수행합니다. 스택 또는 재귀 함수로 구현할 수 있습니다. (예: 비밀)

🗣️ 해시 테이블이란 무엇인가요?

해시 테이블은 키와 값 쌍을 저장하는 자료구조입니다. 해시 함수로 키에 대한 해시를 얻을 수 있는데, 해시는 해시 테이블에서 값이 저장되어 있는 인덱스입니다. 해시 테이블은 `O(1)`이라는 빠른 시간 안에 해시 함수를 통해 원하는 값에 접근할 수 있는 특징이 있습니다. 하지만 서로 다른 키를 넣었을 때 동일한 값이 나오는 해시 충돌이 발생할 수 있다는 단점도 있습니다.

🗣️ 해시 테이블의 검색 시간 복잡도는 어떻게 `O(1)`을 유지할 수 있나요?

해시 테이블에 키로 접근하면, 해시 함수에 키 값을 집어 넣어서 나온 해시 값을 저장소의 인덱스로 활용합니다. 해당 인덱스에 값을 저장하므로, 해시 함수의 시간 복잡도를 제외하면 시간 복잡도 `O(1)`을 보장할 수 있습니다.

🗣️ 해시 테이블을 이용할 때 해시 충돌이 발생할 경우 어떻게 처리할 수 있나요? 🌟

해시 테이블에 접근하는 키 값은 무한하고, 해시 함수를 통해 나온 해시 값은 유한합니다. 값이 저장되는 메모리는 한계가 있기 때문인데요.

서로 다른 키에 대해 같은 해시값을 가지는 '해시 충돌' 을 해결하기 위한 방법으로 Chaining 방식과 Open Addressing 방법이 있습니다.

체이닝은 같은 해시가 나오는 키의 값을 연결 리스트로 저장하는 방식입니다. 인덱스의 버킷을 연결 리스트로 구현해, 이미 값이 존재하더라도 연결리스트에 해당 값을 삽입합니다. 해시 테이블의 저장 공간에 대한 제약을 적게 받지만, 하나의 해시에 노드가 너무 많아질 수 있다는 단점이 있습니다.
개방 주소법은 해시 충돌 발생 시 비어 있는 공간에 값을 저장하는 방식입니다. 특정한 간격만큼 이동 후 비어있는 주소 값에 저장하는 방식입니다. 세부적으로는 선형 조사법, 이차 조사법, 이중 해싱이 있습니다.

출처 https://www.nossi.dev/436b3b11-fa77-4dcc-9d24-f6b034d6770e

🗣️ 체이닝, 개방주소법의 장단점을 비교해주시겠어요?

체이닝 방식

장점

1) 한정된 저장소(Bucket) 을 효율적으로 사용할 수 있다.

2) 해시 함수(Hash Function) 을 선택하는 중요성이 상대적으로 적다.

3) 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.

단점

1) 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.

2) 외부 저장 공간을 사용한다.

3) 외부 저장 공간 작업을 추가로 해야 한다.

개방주소법 방식

장점

1) 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다

단점

1) 해시 함수의 성능에 해시테이블의 성능이 좌지우지됩니다.

2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야 합니다.

Reference

https://www.nossi.dev/fc5fc2ee-40f3-4d60-800a-5ef8fc57b4e5