Swift 면접준비 자료구조편

면접에서 중요한 것은 면접관의 질문이 구체적으로 들어오지 않기 때문에 횡설수설 하지 않고 핵심을 대답해야 한다는 것이다. 그러므로 항상 면접관의 의도를 파악하고 핵심을 말하는 연습이 되어 있어야 한다. 구체적인 내용은 추가로 면접관이 물어보는 경우가 많다. 따라서 쉐도우 복싱으로 어떠한 질문이 들어 왔을때 어떻게 간결하게 답변을 하고 만약 핵심키워드가 등장하지 않는다면 이어지는 질문으로 구체적으로 물어보기도 한다.

자료구조

• Array
• Linked List
• Stack
• Queue
• Hash Table
• Tree
• Heap

Hash Table

Q1. HashTable은 무엇인가요?

해시 테이블은 Key, Value쌍으로 데이터를 저장하는데 삽입 삭제 검색이 모두 평균적으로 선형시간 내에 이루어지는 자료구조입니다.

Q2. 삽입삭제검색이 선형시간내에 이루어질 수 있는 이유는 무엇인가요?

해시테이블은 내부적으로 버킷이라고 불리는 배열에 키와 값을 저장하는데요, 해시함수를 통해 key의 해시 값을 생성하고 그 해시값을 통해 index를 결정하기 때문에 key에 따라 저장될 위치가 결정 되기 때문에 배열 전체를 탐색하지 않아도 되기 떄문에 빠릅니다.

Q3. index가 같아진다면 어떻게 하나요?

이 상황을 해시 충돌이라고 표현하는데요, 이 해시충돌을 해결하는 방법으로 여러가지가 있습니다. 크게 두가지로 나눌 수 있습니다. Open Adderss 방법 separate chaining 즉 개방주소법 분리연결법 두가지로 나뉜다. 개방주소법은 저장해야할 버킷에 이미 다른 값이 저장되어 있다면 다른 버킷에 저장하는 방법이고 분리 연결법은 이 버킷을 각각 링크드리스트나 트리로 구성하는 것입니다.

Array

Q1. Array는 무엇인가요?

Array는 같은 타입의 데이터를 순차적으로 저장하는 선형 자료구조 입니다. 연속적으로 데이터들이 저장되어 index로 원소에 접근 할 수 있습니다.

Q2. Array의 시간복잡도는 어떻게 되나요?

접근 시간복잡도는 O(1), 삽입, 삭제에 대한 복잡도는 O(N)이다

Linked List

Q1. Linked List는 무엇인가요?

LinkedList는 데이터와 포인터로 구성된 Node가 연결된 선형 자료구조입니다. 배열과 달리 연속적인 메모리에 저장되지 않아 Index로 접근 할 수 없고 Node안에 포인터로 접근할 수 있습니다.

class Node<T> {
    var value: T
    var next: Node<T>?
}

Q2. Linked List의 시간복잡도는 어떻게 되나요?

접근 시간복잡도는 O(N)이고, 삽입 삭제에 대한 복잡도는 O(1)이지만 삭제나 삽입할 위치로 이동하는데 O(N)의 시간복잡도를 가져 엄밀히 말하자면 O(N)이지만 연속되는 위치에서 삽입과 삭제가 이루어진다면 O(1)의 시간복잡도를 갖습니다..
Swift에서는 직접적으로 LinkedList를 제공하고 있지 않습니다.

Stack, Queue

Q1. Stack은 무엇인가요?

스택은 원소의 삽입 삭제가 Top에서만 이루어지는 선형 자료구조 입니다. 한곳에서만 삽입 삭제가 가능하기 때문에 last in first out (LIFO)방식으로 가장 마지막에 삽입된 원소가 가장 먼저 삭제되는 특징이 있습니다.

Q2. Queue는 무엇인가요?

큐는 한쪽에서는 원소의 삽입만, 다른한쪽에서는 원소의 삭제만 가능한 선형 자료구조 입니다. First in First out으로 가장 먼저 삽입된 원소가 가장먼저 삭제되는 특징을 갖고 있습니다.

시간복잡도는 어떻게 되나요?

큐와 스택 모두 탐색은 불가능 하고 삽입 삭제 O(1) 상수시간을 갖습니다.

Tree

Tree는 무엇인가요?

Tree는 Node로 구성되어 있는 계층형 자료구조로서 한 Node는 여러개의 자식 Node를 가질수 있는 자료구조 입니다.