면접 대비(자료구조 및 알고리즘)

1. ⭐⭐배열과 연결 리스트의 차이점을 설명해 보세요.

배열과 연결 리스트는 데이터를 저장하는 위한 자료구조로, 데이터 저장 방식에 큰 차이점이 있다. 배열은 연속된 메모리 공간에 데이터를 저장한다. 그래서 특정 인덱스의 데이터에 한 번에 접근할 수 있어서 읽는 속도가 빠르다. 하지만 데이터 삭제 또는 삽입 시 요소들의 인덱스를 수정해야 해서 비교적 시간이 오래걸린다. 

 

반면에, 연결 리스트는 노드를 이용해 메모리 공간에 데이터를 불연속적으로 저장한다. 각 노드는 데이터와 다음 노드의 주소 값을 저장하고 있어서 다른 노드에 접근할 수 있다. 배열과 달리 인덱스가 없으므로 한 번에 특정 데이터에 접근 할 수는 없지만, 데이터의 삽입과 삭제 시 노드가 가리키는 주소 값만 변경하면 되어서 속도가 빠르다는 장점이 있다. 

 

*핵심은 데이터 저장 방식과 연산의 수행 시간이다. 데이터의 저장 방식은 배열이 연속적 메모리 할당, 연결 리스트는 불연속적 메모리 할당 방식이다. 또한, 배열은 인덱스가 있어서 데이터에 빠르게 접근 가능하지만 데이터의 삽입과 삭제가 비교적 느리다. 반면에 연결 리스트는 노드에 저장된 주소 값만 변경하면 되므로 데이터의 삽입과 삭제가 빠르다. 하지만 특정 위치의 데이터에 접근 시 느리다는 특징이 있다. 

2. 자료 구조와 알고리즘을 배우는 이유는 무엇일까요?

가장 이유는 코드 최적화를 통해 프로그램의 속도를 높이고 싶기 때문이다. 

3. 시간 복잡도(Time Complexity)가 무엇인가?

시간복잡도란 알고리즘을 수행하는데 필요한 연산 횟수로, 실제 시간을 측정하는 것이 아니고 얼마나 많은 연산 횟수가 있는가로 측정한다. 따라서 효율적인 알고리즘을 구현하기 위해서는 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는 것이다. 시간표잡도를 표기하는 대표적인 방법으로 Big-O표기법이 있습니다. 

4. Big-O 표기법이란 무엇인지 설명해 주세요.

Big-O 표기법이란 시간 복잡도를 표기하는 방법으로, 일반적으로 최악의 경우에 대하여 나타내는 방법입니다. 예를들어, 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 업애서 복잡도를 나타낸다. 

대표적으로, O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^n) < O(N!)

5. 시간 복잡도를 직접 구할 때, 가장 먼저해야할 핵심적인 일은 무엇인가?

일반적으로, 가장 시간이 오래걸리는 반복문을 찾는 것이 핵심이다. 결국, 가장 오래 걸리는 반복문이 복잡도에 영향을 가장 크게 미치기 때문이다. 

6. 단순 연결 리스트를 '역순'으로 출력하는 방법을 설명해 보세요.

단순 연결 리스트를 역순으로 출력하는 방법은 '스택'에 연결 리스트의 요소를 순차적으로 넣고 빼는 방법이 있다. 이 방법은 스택을 사용하므로 추가적인 메모리가 필요하다. 메모리에 여유가 없다면 반복문을 활용해서 다음 노드가 가리키는 노드를 이전 노드로 바꿔서 역순으로 된 연결 리스트를 얻는 방법도 있다. 

7. DFS와 BFS의 차이점은 무엇인가?

모두 그래프를 탐색할 때, 사용하는 알고리즘이다. BFS는 너비 우선 탐색으로, 하나의 노드에서 시작해 가까운 노드들을 우선적으로 탐색을 한다. 큐로 구현이 가능하며, 비가중치 그래프에서 각 노드까지의 최단 거리를 알 수 있다. DFS는 깊이 우선 탐색으로, 하나의 노드에서 시작해 최대한 깊이까지 탐색하는 방법으로 스택 또는 재귀 함수로 구현할 수 있다.

8. ⭐스택은 어떤 경우에 주로 사용하는가?

스택은 데이터가 쌓이는 구조로 '후입선출'의 특징이 있습니다. 그래서 주로 마지막에 수행한 작업으로 돌아가야 할 때 자주 사용합니다. 예를들어, 웹 브라우저에서 뒤로가기 버튼을 눌러 앞에 열었던 페이지를 다시 열거나 작업 프로그램에서 실행 취소 기능을 수행해 마지막 상태로 돌아가야 하는 상황에 사용할 수 있습니다. 

9. 큐를 스택으로 구현하는 방법을 설명해 보세요.

큐는 선입선출, 스택은 후입선출 방식이므로 스택 2개를 사용해 큐를 구현할 수 있습니다. 우선 데이터 전체를 첫 번째 스택에 넣습니다. 이때 데이터는 역순으로 뒤집히게 됩니다. 이 데이터를 다시 두 번째 스택에 넣으면 마지막 데이터부터 첫 번째 데이터 순으로 쌓이게 됩니다. 따라서 두 번째 스택에서 pop 연산을 하면 선입선출을 구현할 수 있습니다. 

10. 우선순위 큐는 무엇인가요?

우선순위 큐는 우선순위가 높은 데이터부터 꺼재는 자료구조로, 각 요소가 우선순위를 가집니다. 그리고 우선순위 큐를 활용해서 정렬하거나 다익스트라 알고리즘을 구현할 때 사용합니다. 또한, 우선순위 큐는 주로 힙을 이용해 구현합니다. 

11. 힙이란 무엇인가?

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

 

*연결 질문으로 힙에서 데이터 삽입 또는 삭제 과정을 묻는 내용이 나올 수 있다. 따라서 이 과정을 숙지하고 직접 그려보기를 추천. 힙 개념은 코딩 테스트에서도 빈번히 출제되므로 본인의 주 언어로 어떻게 구현하는지 반드시 익혀 두어야 한다. 

12. ⭐⭐⭐스택과 큐의 차이점을 설명해 주세요.

스택은 데이터가 쌓이는 구조로, 마지막에 들어온 데이터가 먼저 나가는 LIFO 형태의 자료구조이다. 스택에 데이터를 삽입하는 연산을 push라 하고, 스택의 가장 위에 데이터를 저장한다. 그리고 pop 연산은 스택에 있는 데이터를 삭제하는 연산으로 마지막에 저장한 데이터를 삭제합니다. 그리고 삽입과 삭제 각 연산의 시간복잡도는 O(1)입니다. 반면에, 큐는 데이터가 순차적으로 들어오는 형태로, 먼저 들어온 데이터가 먼저 나가는 FIFO 형태의 자료구조 입니다. 그리고 큐에 데이터를 추가하면 큐의 맨 뒤에 데이터가 삽입되며, 이를 인큐(enqueue)라 한다. 그리고 데이터를 삭제하면 큐의 맨 앞에서 삭제되며, 이를 디큐(dequeue)라고 한다. 인규와 티큐의 각각 연산도 O(1)의 시간 복잡도가 걸린다. 

13. ⭐⭐해시 테이블이란 무엇인가요?

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

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

해시 충돌을 해결하기 위한 방법으로 체이닝과 개방 주소법이 있습니다. 체이닝은 같은 해시가 나오는 키의 값을 연결 리스트로 저장하는 방식입니다. 해시 테이블의 저장 공간에 대한 제약을 적게 받지만, 하나의 해시에 노드가 너무 많아질 수 있다는 단점이 있습니다. 개방 주소법은 해시 충돌 발생 시 비어 있는 공간에 값을 저장하는 방식입니다. 세부적으로는 선형 조사법, 이차 조사법, 이중 해싱이 있습니다. 

 

*선형 조사법, 이차 조사법, 이중 행싱의 작동 방식도 알고 있어야 한다. Q. 좋은 해시 함수의 조건은 뭘까요?

15. 해시 충돌시 해결하는 방법인 개방 주소법 중에서 이중 행싱이 무엇인지 설명해 주세요.

이중 해싱(double hashing)은 해시 충돌이 발생하면 다른 해시 함수를 한 번 더 적용하는 방법이다. 

16. ⭐알고리즘 공부는 어떻게 했는지? 알고리즘 문제를 몇 개정도 풀어봤는지? 그 중 어려웠던 개념은? 그 개념 중에서 어떤 부분이 특히 어려웠는지?

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

3가지 모두 이진 트리지만, 서로 다른 특징이 있다. 먼저, 이진 탐색 트리는 모든 노드에 대해 왼쪽 서브 트리는 해당 노드보다 작은 값을 갖고, 오른쪽 서브 트리는 해당 노드보다 큰 값을 갖는다. 포화 이진 트리는 트리의 마지막 레벨까지 모든 노드가 채워져 있다. 마지막으로 완전 이진 트리는 트리의 마지막 레벨을 제외한 나머지 레벨에 모든 노드가 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 노드가 채워져 있다. 

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

이진 탐색 트리에서 불균형이 발생하면 시간 복잡도가 비효율적이라는 문제가 있다. 예를 들어, 트리가 한쪽으로 편향되어 있으면 O(n)의 시간복잡도가 소요될 수 있다. 이를 보완하기 위해 등장한 방법이 균형 이진 탐색 트리다. 대표적이로 레드-블랙 트리와 AVL 트리가 있다. 

 

*이진 탐색 트리에서 삽입, 삭제 연산을 수행하면서 불균형한 구조가 될 수 있다. 최악의 경우 편향적인 이진 탐색 트리가 되어 시간 복잡도가 O(n)이 된다.

* 레드-블랙 트리와 AVL 트리에 대해서 추가 질문 나올 수 있다.

 

*AVL 트리: 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리다. 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다. 

*레드-블랙-트리: 균형 이진 탐색 트리로, 탐색, 삽입, 삭제 모두 시간복잡도가 O(logn)입니다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용된다. 

19. ⭐트리와 그래프의 차이점은 무엇인가?

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