자료구조 면접 질문

스택과 큐는 둘 다 데이터를 저장하는 자료구조이지만, 데이터 접근 방식에 차이가 있습니다. 스택은 LIFO(Last-In, First-Out) 즉, 가장 최근에 들어온 데이터가 가장 먼저 나가는 구조입니다. 반면 큐는 FIFO(First-In, First-Out) 즉, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조입니다.

스택의 대표적인 사용 사례는 함수 호출 스택입니다. 함수가 호출될 때마다 스택에 정보가 쌓이고, 함수 실행이 끝나면 스택에서 해당 정보가 제거됩니다. 또한, 웹 브라우저의 뒤로 가기 기능도 스택으로 구현될 수 있습니다.

큐의 대표적인 사용 사례는 너비 우선 탐색(BFS)입니다. BFS는 큐를 사용하여 탐색할 노드들을 저장하고, 순서대로 방문합니다. 또한, 프린터의 작업 대기열이나 메시지 큐와 같이 순차적인 처리가 필요한 경우에도 큐가 사용됩니다.

배열과 연결 리스트는 데이터를 저장하는 기본적인 자료구조이지만, 메모리 구조와 사용 방식에 차이가 있습니다.

배열은 메모리 상에 연속적으로 데이터를 저장합니다. 덕분에 인덱스를 통해 특정 위치의 데이터에 빠르게 접근(임의 접근)할 수 있다는 장점이 있습니다. 하지만, 배열의 크기를 미리 정해야 하고, 중간에 데이터를 삽입하거나 삭제할 때 다른 데이터들을 이동시켜야 하므로 비효율적일 수 있습니다.

반면, 연결 리스트는 각 데이터가 포인터를 통해 다음 데이터를 가리키는 방식으로 연결됩니다. 데이터들이 메모리 상에 흩어져 있어도 상관없고, 삽입/삭제 시 포인터만 변경하면 되므로 효율적입니다. 하지만, 특정 위치의 데이터에 접근하려면 처음부터 순차적으로 탐색해야 하므로 배열보다 접근 속도가 느립니다.

어떤 자료구조를 선택할지는 상황에 따라 다릅니다. 데이터 접근이 잦고 삽입/삭제가 거의 없다면 배열이 유리하고, 삽입/삭제가 빈번하게 일어난다면 연결 리스트가 더 나은 선택일 수 있습니다.

면접관님, 시간 복잡도와 공간 복잡도는 알고리즘의 성능을 분석하는 중요한 지표입니다.

시간 복잡도는 알고리즘이 실행되는데 걸리는 시간을 입력 크기에 따라 나타낸 것이고, 공간 복잡도는 알고리즘이 사용하는 메모리 공간을 입력 크기에 따라 나타낸 것입니다.

Big-O 표기법은 알고리즘의 효율성을 나타내는 방법 중 하나로, 입력 크기가 무한대로 커질 때 알고리즘의 실행 시간 또는 메모리 사용량이 어떻게 증가하는지를 점근적으로 분석합니다. 주로 최악의 경우를 기준으로 성능을 평가합니다. 예를 들어, O(n)은 입력 크기 n에 비례하여 실행 시간이 증가한다는 의미이고, O(log n)은 입력 크기가 증가해도 실행 시간이 크게 증가하지 않는다는 의미입니다. O(1)은 입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우입니다.

이진 탐색은 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘입니다. 작동 원리는 다음과 같습니다. 먼저 배열의 중간값을 확인하고, 찾고자 하는 값이 중간값보다 작으면 배열의 왼쪽 절반을, 크면 오른쪽 절반을 탐색 범위로 좁힙니다. 이 과정을 찾을 때까지 반복합니다.

핵심은 탐색 범위를 절반씩 줄여나간다는 점입니다. 따라서 시간 복잡도는 O(log N)입니다. 예를 들어 16개의 요소가 있는 배열에서 최악의 경우에도 4번 안에 값을 찾을 수 있습니다. 분할 정복 알고리즘의 대표적인 예시라고 할 수 있습니다.

면접관님, 재귀와 반복은 둘 다 코드를 반복적으로 실행하는 방법이지만, 작동 방식에 차이가 있습니다.

재귀는 함수가 자기 자신을 호출하는 방식입니다. 장점은 코드가 간결하고 가독성이 좋을 수 있다는 점입니다. 하지만 함수 호출 시 스택에 메모리를 계속 쌓기 때문에 스택 오버플로우가 발생할 위험이 있고, 반복에 비해 일반적으로 성능이 떨어집니다. 반드시 종료 조건을 명확하게 설정해야 무한 루프를 방지할 수 있습니다.

반복은 for나 while 같은 반복문을 사용하여 코드를 반복합니다. 재귀에 비해 메모리 사용량이 적고 성능이 좋은 경우가 많습니다.

재귀를 반복으로 변환하는 것은 가능합니다. 스택을 직접 사용하여 재귀 호출을 흉내 내거나, 꼬리 재귀 최적화가 가능한 경우에는 반복문으로 쉽게 변환할 수 있습니다. 반대로, 반복문을 재귀 함수로 바꾸는 것도 가능하지만, 가독성이 떨어질 수 있습니다.

이중 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 'next' 포인터뿐만 아니라 이전 노드를 가리키는 'prev' 포인터를 가지고 있다는 점이 특징입니다.

단일 연결 리스트는 'next' 포인터만 있어서 한 방향으로만 탐색이 가능한 반면, 이중 연결 리스트는 'prev' 포인터 덕분에 양방향으로 자유롭게 탐색할 수 있습니다.

단일 연결 리스트에서는 특정 노드를 삭제하려면 삭제할 노드의 이전 노드를 찾아야 하는 번거로움이 있지만, 이중 연결 리스트는 'prev' 포인터를 통해 이전 노드에 바로 접근할 수 있어 삭제 연산이 더 효율적입니다.

다만, 'prev' 포인터를 위한 추가적인 메모리 공간이 필요하다는 메모리 오버헤드가 발생한다는 단점도 있습니다.

동적 배열은 내부적으로 미리 정해진 용량(capacity)을 가지고 있습니다. 이 용량이 꽉 차서 새로운 요소를 추가해야 할 때, 동적 배열은 더 큰 새로운 배열을 생성하고 기존 배열의 모든 요소를 새 배열로 복사합니다. 이 과정을 '재할당'이라고 합니다.

재할당 과정은 기존 배열의 모든 요소를 복사해야 하므로 O(n)의 시간 복잡도를 가집니다. 하지만 동적 배열은 보통 용량을 기하급수적으로 늘립니다 (예: 현재 용량의 두 배). 이렇게 하면 재할당이 자주 발생하지 않게 됩니다.

이러한 재할당 비용은 '분할 상환 분석(Amortized Analysis)'을 통해 평균적으로 상수 시간 O(1)으로 평가됩니다. 즉, 개별 연산은 비쌀 수 있지만, 많은 연산을 수행했을 때 평균적으로 드는 비용은 매우 낮다는 의미입니다.

HashMap은 키-값 쌍을 저장하는 자료구조로, 빠른 검색 속도를 제공합니다. 동작 원리는 다음과 같습니다.

1. 해시 함수: 키를 해시 함수에 넣어 배열의 인덱스(버킷)를 얻습니다.
2. 저장: 해당 인덱스에 키-값 쌍을 저장합니다.

문제는 서로 다른 키가 같은 인덱스를 가리키는 해시 충돌이 발생할 수 있다는 점입니다. 이를 해결하는 방법은 크게 두 가지입니다.

• 체이닝(Chaining): 각 버킷을 연결 리스트로 만들어, 같은 인덱스에 여러 키-값 쌍을 저장합니다. 검색 시에는 해당 연결 리스트를 순회합니다.
• 개방 주소법(Open Addressing): 충돌이 발생하면, 다른 빈 버킷을 찾아 저장합니다. 선형 탐사, 이차 탐사, 이중 해싱 등의 방법이 있습니다.

HashMap의 성능은 해시 함수의 품질과 로드 팩터(데이터 개수 / 버킷 개수)에 따라 달라집니다. 로드 팩터가 높아지면 충돌 가능성이 커져 성능이 저하될 수 있습니다.

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 중요한 특징은 각 노드의 왼쪽 서브트리에 있는 모든 값은 해당 노드의 값보다 작고, 오른쪽 서브트리에 있는 모든 값은 해당 노드의 값보다 크다는 점입니다. 이 속성 덕분에 정렬된 데이터를 효율적으로 탐색, 삽입, 삭제할 수 있습니다.

일반적인 경우, 이진 탐색 트리의 탐색, 삽입, 삭제 연산의 평균 시간 복잡도는 O(log n)입니다. 하지만 트리가 한쪽으로 치우쳐진 최악의 경우에는 O(n)까지 늘어날 수 있습니다. 따라서 AVL 트리나 Red-Black 트리처럼 스스로 균형을 맞추는 균형 이진 탐색 트리를 사용하여 최악의 경우에도 O(log n)의 시간 복잡도를 보장하는 것이 중요합니다.

힙(Heap)은 완전 이진 트리의 일종으로, '힙 속성'을 만족하는 자료구조입니다. 힙 속성은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나(최대 힙), 항상 작거나(최소 힙) 같은 것을 의미합니다. 이러한 특징 덕분에 힙은 우선순위 큐를 구현하는 데 효과적입니다.

힙 정렬은 힙 자료구조를 이용한 정렬 알고리즘입니다. 먼저 주어진 데이터를 힙으로 만듭니다. 최대 힙의 경우, 루트 노드에는 항상 가장 큰 값이 위치하게 됩니다. 이 루트 노드와 힙의 마지막 노드를 교환하고, 힙의 크기를 줄인 후 다시 힙 속성을 만족하도록 조정하는 과정을 반복합니다. 이 과정을 통해 내림차순으로 정렬된 배열을 얻을 수 있습니다. 힙 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가집니다.

그래프를 표현하는 대표적인 방법으로는 인접 행렬과 인접 리스트가 있습니다.

인접 행렬은 2차원 배열을 사용하여 정점 간의 연결 관계를 표현합니다. 예를 들어, matrix[i][j] = 1은 정점 i에서 정점 j로 가는 간선이 존재한다는 의미입니다. 장점으로는 특정 정점 쌍의 연결 여부를 O(1) 시간 안에 확인할 수 있다는 점이 있습니다. 하지만 모든 정점 쌍에 대한 정보를 저장해야 하므로, 공간 복잡도가 O(V^2)입니다. 따라서 간선이 적은 희소 그래프의 경우 메모리 낭비가 심할 수 있습니다.

반면, 인접 리스트는 각 정점에 연결된 정점들을 리스트 형태로 저장합니다. 예를 들어, 정점 i의 리스트에는 정점 i에서 갈 수 있는 모든 정점들이 저장됩니다. 인접 리스트는 실제 간선 수에 비례하는 공간 복잡도 O(V+E)를 가지므로, 희소 그래프에 효과적입니다. 하지만 특정 정점 쌍의 연결 여부를 확인하려면 해당 리스트를 탐색해야 하므로, 시간 복잡도는 O(V)가 될 수 있습니다. 따라서 간선 탐색 빈도가 높은 경우에는 인접 행렬이 더 효율적일 수 있습니다.

BFS와 DFS는 그래프 탐색 알고리즘으로, 탐색 순서와 사용하는 자료구조에서 차이가 있습니다.

BFS는 큐를 사용하여 현재 노드와 연결된 모든 노드를 먼저 탐색합니다. 마치 물이 퍼져나가듯이 넓게 탐색하죠. 그래서 최단 경로를 찾는 문제에 유용합니다. 예를 들어, 지도에서 두 지점 사이의 최단 거리를 구할 때 사용할 수 있습니다.

반면 DFS는 스택을 사용하여 한 노드에서 최대한 깊숙이 탐색한 후, 더 이상 갈 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색합니다. 미로 찾기나, 그래프 내의 모든 경로를 탐색하는 문제에 적합합니다.

메모리 사용량 측면에서는, BFS는 큐에 많은 노드를 저장해야 할 수 있어 DFS보다 메모리를 더 많이 사용할 수 있습니다. DFS는 재귀 호출을 사용하므로 스택 오버플로우에 주의해야 합니다.

면접관님, 퀵 정렬, 병합 정렬, 힙 정렬은 모두 효율적인 정렬 알고리즘이지만, 시간 복잡도와 특징에서 차이가 있습니다.

퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가지며, 제자리 정렬(in-place sort)이라는 장점이 있습니다. 하지만 최악의 경우 O(n^2)까지 시간 복잡도가 증가할 수 있고, 안정 정렬(stable sort)은 아닙니다.

병합 정렬은 항상 O(n log n)의 시간 복잡도를 보장하며, 안정 정렬이라는 특징이 있습니다. 하지만 제자리 정렬이 아니기 때문에 추가적인 메모리 공간이 필요합니다.

힙 정렬 역시 O(n log n)의 시간 복잡도를 가지며, 제자리 정렬입니다. 하지만 일반적으로 퀵 정렬보다는 성능이 조금 떨어지는 경향이 있고, 안정 정렬은 아닙니다.

따라서 데이터의 특성과 메모리 사용량 등을 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다.

트라이(Trie)는 문자열을 저장하고 검색하는 데 특화된 트리 형태의 자료구조입니다. 각 노드는 문자 하나를 나타내며, 루트 노드부터 특정 노드까지 이어지는 경로가 하나의 문자열을 형성합니다.

트라이의 가장 큰 특징은 문자열 검색 시 시간 복잡도가 문자열의 길이에 비례한다는 점입니다. 따라서, 많은 문자열 중에서 특정 문자열을 빠르게 찾거나, 특정 접두사로 시작하는 문자열을 찾는 데 매우 효율적입니다.

주요 사용 사례로는 자동 완성 기능, 사전 검색, IP 라우팅 등이 있습니다. 예를 들어, 자동 완성 기능에서 사용자가 'apple'을 입력했을 때, 트라이를 사용하면 'apple', 'applet', 'application'과 같이 'apple'로 시작하는 단어들을 빠르게 찾아 추천해줄 수 있습니다.

다만, 트라이는 각 노드가 자식 노드를 가리키는 포인터를 많이 가지고 있기 때문에, 저장하는 문자열의 종류가 많아질수록 공간 복잡도가 높아질 수 있다는 단점이 있습니다.

레드-블랙 트리는 자가 균형 이진 탐색 트리입니다. 검색, 삽입, 삭제 연산 시 최악의 경우에도 O(log n)의 시간 복잡도를 보장하죠. 균형을 유지하기 위해 각 노드는 '레드' 또는 '블랙' 색상을 가집니다.

레드-블랙 트리는 다음과 같은 속성을 만족해야 합니다.

1. 루트 노드는 블랙입니다.
2. 모든 리프 노드(NIL 노드)는 블랙입니다.
3. 레드 노드의 자식은 모두 블랙입니다. (레드 노드가 연속으로 나올 수 없습니다.)
4. 어떤 노드로부터 시작해서 리프 노드까지 가는 경로에서 만나는 블랙 노드의 수는 모두 같습니다.

삽입이나 삭제 후에는 이러한 속성이 깨질 수 있습니다. 이때 '회전(Rotation)'과 '색상 반전(Color Flipping)' 연산을 통해 트리의 균형을 유지합니다. 회전은 트리의 구조를 재배치하고, 색상 반전은 노드의 색상을 변경하여 속성을 만족하도록 합니다. 이러한 연산들을 통해 트리의 균형을 유지하고 효율적인 탐색 성능을 보장합니다.

최소 스패닝 트리(MST)를 구하는 대표적인 알고리즘으로 Kruskal과 Prim 알고리즘이 있습니다. 둘 다 탐욕 알고리즘에 기반합니다.

Kruskal 알고리즘은 가장 가중치가 작은 간선부터 시작하여 트리를 확장해 나갑니다. 핵심은 사이클을 만들지 않도록 간선을 선택하는 것입니다. 이를 위해 Union-Find 자료구조를 사용하여 각 정점이 속한 집합을 관리하고, 두 정점이 같은 집합에 속해 있다면 해당 간선을 선택하지 않습니다.

Prim 알고리즘은 특정 정점에서 시작하여 트리를 확장해 나갑니다. 이미 트리에 속한 정점과 연결된 간선 중 가장 가중치가 작은 간선을 선택하여 트리를 확장합니다. Kruskal과는 달리 항상 연결된 트리를 유지한다는 특징이 있습니다.

두 알고리즘 모두 그래프의 모든 정점을 연결하면서 가중치의 합이 최소가 되는 트리를 찾는다는 공통점이 있습니다.

세그먼트 트리는 배열의 특정 구간에 대한 질의를 효율적으로 처리하기 위한 자료구조입니다. 기본적으로 이진 트리 형태를 가지며, 각 노드는 배열의 특정 구간에 대한 정보를 저장합니다. 예를 들어, 구간 합이나 구간 최솟값 등을 저장할 수 있습니다.

세그먼트 트리의 가장 큰 장점은 쿼리 연산의 시간 복잡도가 O(log N)으로 매우 빠르다는 점입니다. 배열의 크기가 N일 때, 트리의 높이가 log N에 비례하기 때문입니다. 또한, 특정 구간의 값을 업데이트하는 연산도 O(log N)에 수행할 수 있습니다.

주요 사용 사례로는 다음과 같은 것들이 있습니다.

• 구간 합 구하기: 배열의 특정 구간의 합을 빠르게 계산해야 할 때 유용합니다.
• 구간 최솟값/최댓값 구하기: 배열의 특정 구간에서 최솟값 또는 최댓값을 빠르게 찾아야 할 때 사용됩니다.
• Lazy Propagation: 구간 업데이트가 빈번하게 발생하는 경우, 업데이트 연산을 효율적으로 처리하기 위해 Lazy Propagation 기법을 함께 사용하기도 합니다. 이는 업데이트 정보를 노드에 저장해두었다가 필요할 때 자식 노드로 전파하는 방식입니다.

AVL 트리는 자가 균형 이진 탐색 트리로, 모든 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 최대 1 이하인 균형 조건을 유지합니다. 이 덕분에 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)으로 보장됩니다. 균형이 깨지면 LL, RR, LR, RL 회전을 통해 트리의 균형을 맞춥니다.

레드-블랙 트리 역시 자가 균형 트리이지만, AVL 트리보다 균형 조건이 덜 엄격합니다. 각 노드는 빨간색 또는 검은색으로 칠해져 있으며, 색상 속성을 통해 균형을 유지합니다. AVL 트리보다 삽입/삭제 시 회전 횟수가 적어, 삽입/삭제가 빈번한 경우 성능상 유리할 수 있습니다. 하지만 최악의 경우 탐색 성능은 AVL 트리보다 약간 떨어질 수 있습니다. 즉, AVL 트리는 엄격한 균형을 통해 탐색 성능을 극대화하고, 레드-블랙 트리는 균형 유지 비용을 줄여 삽입/삭제 성능을 향상시킨다고 볼 수 있습니다.

블룸 필터는 어떤 원소가 집합에 속하는지 여부를 검사하는 데 사용되는 확률적인 자료 구조입니다. 핵심 아이디어는 여러 개의 해시 함수를 사용하여 원소를 비트 배열의 여러 위치에 매핑하는 것입니다.

원소를 추가할 때는 각 해시 함수를 통해 얻은 인덱스에 해당하는 비트를 1로 설정합니다. 원소의 존재 여부를 확인할 때는 동일한 해시 함수들을 사용하여 비트 배열의 해당 위치를 확인합니다. 모든 위치의 비트가 1로 설정되어 있다면, 그 원소가 집합에 "아마도" 존재한다고 판단합니다.

블룸 필터는 공간 효율성이 매우 높지만, False Positive(오탐)가 발생할 수 있다는 단점이 있습니다. 즉, 실제로는 집합에 없는 원소를 있다고 판단할 수 있습니다. 하지만 False Negative(미탐)는 발생하지 않습니다.

주요 사용 사례로는 데이터베이스 시스템에서 존재하지 않는 키에 대한 접근을 빠르게 필터링하거나, 네트워크 캐시에서 이미 캐싱된 데이터를 확인하는 데 사용될 수 있습니다. 또한 스팸 필터링이나 악성 URL 검사 등에도 활용됩니다.

동적 배열의 capacity 확장 전략에서 1.5배와 2배 증가는 메모리 재사용과 성능 간의 트레이드오프를 가집니다.

2배 증가는 더 자주 새로운 메모리 블록을 할당하게 되어 메모리 단편화를 유발할 수 있습니다. 반면, 1.5배 증가는 더 작은 단위로 확장하여 메모리 낭비를 줄일 수 있지만, 더 빈번한 재할당으로 인한 오버헤드가 발생합니다.

Amortized O(1) append는 분할 상환 분석으로 설명됩니다. append 연산 시 capacity가 부족하면 새로운 배열을 할당하고 기존 요소를 복사하는데, 이 비용은 O(n)입니다. 하지만 이 비용은 발생하지 않는 append 연산들로 분산됩니다. 예를 들어, 2배 성장 시, n개의 요소를 추가하는 데 총 비용은 대략 2n번의 복사로 amortized O(1)이 됩니다. 1.5배 성장도 유사하게 분석되며, 성장 인자가 클수록 재할당 빈도는 줄지만 개별 재할당 비용은 커집니다.

대용량 데이터에서 배열 중간 삽입/삭제가 빈번하다면, 연속 메모리 배열의 비효율성을 피하기 위해 몇 가지 자료구조를 고려할 수 있습니다.

Gap Buffer는 텍스트 편집기 등에서 커서 주변의 삽입/삭제가 잦을 때 유리합니다. 배열 중간에 'gap'을 두어 삽입/삭제 시 gap만 이동시키므로, O(1)에 가까운 성능을 보입니다. 하지만 gap이 커지면 이동 비용이 증가하는 단점이 있습니다.

Rope는 매우 긴 문자열을 다룰 때 효과적입니다. 문자열을 트리 구조로 분할하여 관리하므로, 삽입/삭제 시 해당 부분만 재구성하여 O(log N)의 시간 복잡도를 가집니다. 메모리 오버헤드가 있지만, 큰 문자열의 부분적인 수정에 강점을 보입니다.

Unrolled Linked List는 링크드 리스트의 각 노드에 여러 개의 요소를 담는 방식입니다. 삽입/삭제 시 노드 내에서 처리하거나, 필요에 따라 노드를 분할/병합하여 O(sqrt N) 정도의 성능을 기대할 수 있습니다. 캐시 효율성을 높여 순차 접근 성능도 개선됩니다.

각 구조는 삽입/삭제 위치의 지역성, 데이터 크기, 접근 패턴에 따라 장단점이 명확하므로, 시스템의 특성을 고려하여 선택해야 합니다.