search

TeamCoook / iOSInterviewQuestions

✅ iOS 개발자 기술 면접 대비
18 stars 0 forks source link

[레벨 0] `4주차` 7. 자료구조의 종류와 iOS 개발에서 자주 사용되는 자료구조에 대해 설명해주세요. #7

Open longlivedrgn opened 5 months ago

longlivedrgn commented 5 months ago
soo941226 commented 5 months ago

이번주는 개조식으로 써보겠습니다~

배열, 연결 리스트, 스택, 큐의 특징과 iOS에서의 구현 방법을 설명해주세요.

해시 테이블의 개념, 충돌 해결 방법을 설명해주세요.

트리 자료구조의 종류(예: 이진 트리, 이진 탐색 트리, AVL 트리)을 설명해주세요.

longlivedrgn commented 5 months ago

배열, 연결 리스트, 스택, 큐의 특징과 iOS에서의 구현 방법을 설명해주세요.

배열

연결 리스트

노드는 아래와 같이 value와 next 값을 가지고 있다.

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

    init(value: T, next: Node<T>?) {
        self.value = value
        self.next = next
    }
}

링크드 리스트는 아래와 같은 구조를 가지고 있다. head/tail

class LinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?

    init (head: Node<T>?) {
        self.head = head
        self.tail = head
    }
}

스택

큐

하나의 Array로 구현

→ dequeue할 때 O(n)

struct QueueArray<T>: Queue {
  private var array: [T] = []
  var isEmpty: Bool {
    return array.isEmpty
  }
  var peek: T? {
    return array.first
  }

  mutating func enqueue(_ element: T) {
    array.append(element)
  }

  @discardableResult
  mutating func dequeue() -> T? {
    return isEmpty ? nil : array.removeFirst()
  }
}

두 개의 Array로 구현

→ dequeue할 때 O(1)

struct QueueStack<T>: Queue {
  private var dequeueStack: [T] = []
  private var enqueueStack: [T] = []

  var isEmpty: Bool {
    return dequeueStack.isEmpty && enqueueStack.isEmpty
  }
  var peek: T? {
    return !dequeueStack.isEmpty ? dequeueStack.last : enqueueStack.first
  }

  mutating func enqueue(_ element: T) {
    enqueueStack.append(element)
  }

  @discardableResult
  mutating func dequeue() -> T? {
    if dequeueStack.isEmpty {
      dequeueStack = enqueueStack.reversed()
      enqueueStack.removeAll()
    }
    return dequeueStack.popLast()
  }
}

해시 테이블의 개념, 충돌 해결 방법을 설명해주세요.

해시 테이블

해시 값 충돌하는 경우

분리 연결법(Separate Chaining)

개방 주소법(Open Addressing)

트리 자료구조의 종류(예: 이진 트리, 이진 탐색 트리, AVL 트리)을 설명해주세요.

ohdair commented 5 months ago

블로그 기재

qwerty3345 commented 5 months ago

배열, 연결 리스트, 스택, 큐의 특징과 iOS에서의 구현 방법을 설명해주세요.

배열 (Array)

연결 리스트 (LinkedList)

스택

큐

해시 테이블의 개념, 충돌 해결 방법을 설명해주세요.

트리 자료구조의 종류(예: 이진 트리, 이진 탐색 트리, AVL 트리)을 설명해주세요.

llimental commented 5 months ago
1. 배열, 연결 리스트, 스택, 큐의 특징과 iOS에서의 구현 방법을 설명해주세요. ### 1-1) 배열 - 연속된 메모리 공간에 동일한 타입의 요소를 저장하는 자료 구조 - 빠른 접근이 가능하며, 인덱스를 사용하여 요소에 직접 접근할 수 있습니다. - iOS에서 배열은 Array 클래스를 통해 구현되며, [] 내 인덱스를 기입하여 요소에 접근 가능합니다. ### 1-2) 연결 리스트 - 각 요소가 데이터와 다음 요소를 가리키는 포인터로 이루어진 자료 구조를 말합니다. - 삽입과 삭제가 상대적으로 용이하며 동적인 크기 조정이 가능합니다. - iOS에서 연결 리스트는 기능적으로 제공되지는 않지만 직접 구현할 수 있습니다. 각 노드를 클래스로 정의하고 다음 요소를 가리키는 프로퍼티에 각 요소를 대입하여 접근할 수 있습니다. ### 1-3) 스택 - 스택은 LIFO(Last In First Out, 후입선출) 방식의 자료 구조입니다. - 요소의 추가와 제거가 스택의 상단에서만 이뤄집니다(= 후입선출) - iOS에서 스택은 배열을 사용하여 구현할 수 있는데, append로 push의 역할을, popLast로 pop의 역할을 할 수 있습니다. ### 1-4) 큐 - FIFO(First In First Out, 선입선출) 방식의 자료 구조입니다. - 요소의 추가는 큐의 뒤쪽에서 이뤄지고, 제거는 앞쪽에서 이뤄집니다. - iOS에서 큐는 스택과 마찬가지로 배열을 사용하는데, append로 enqueue를, removeFirst로 dequeue를 수행할 수 있습니다.
2. 해시 테이블의 개념, 충돌 해결 방법을 설명해주세요. ### 2-1) 해시 테이블 - 해시 케이블은 키와 값으로 이루어진 데이터를 저장하는 자료 구조입니다. - 해시 함수를 사용하여 키를 배열의 인덱스로 변환하고, 해당 인덱스에 값을 저장합니다. 이를 통해 키를 사용하여 빠르게 값을 검색할 수 있습니다. - 올바른 해시 함수를 사용하면 검색 및 삽입에 걸리는 시간이 상수 시간(알고리즘이 실행되는 시간이 입력 크기와 관계없이 항상 일정한 시간이 걸리는 것)에 가깝고, 동적 크기 조정이 가능하여 삽입, 삭제, 검색 등의 연산을 유연하게 처리할 수 있습니다. ### 2-2) 충돌 해결 방법 - 우선, 해시 충돌이란 해시 함수가 서로 다른 입력값에 대해 동일한 출력값을 내는 상황을 의미합니다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리(요소가 n+1개, 환경이 n개라면 어느 한 곳에는 요소가 2개 이상이 있다는 원리)에 의해 해시 충돌은 항상 존재합니다. - 이러한 충돌 상황은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리고, 보안 측면에서는 안전성을 깨뜨리는 공격이 가능할 수 있기 때문에 이러한 충돌을 방지하는 것이 중요합니다. - 개별 체이닝(Separate Chaining)은 해시 테이블의 각 버킷에 연결 리스트나 다른 자료 구조를 사용하여 충돌된 요소들을 저장합니다. 충돌이 발생하면 해당 버킷에 연결 리스트를 사용하여 요소를 추가합니다. 다만 충돌이 많아질수록 연결 리스트의 길이가 길어지기 때문에 성능적 영향을 고려해야 합니다. - 개방 주소법(Open Addressing)은 충돌이 발생하면 다른 빈 버킷을 찾아 그곳에 요소를 저장하는 방식입니다. 선형 탐사, 이차 제곱 탐사, 랜덤 탐사 등의 방법을 사용하여 다음 빈 버킷을 찾습니다. 버킷이 모두 차면 해시 테이블의 크기를 확장할 수 있습니다.
3. 트리 자료구조의 종류(예: 이진 트리, 이진 탐색 트리, AVL 트리)을 설명해주세요. ### 3-1) 이진 트리 - 각 노드가 최대 두 개의 자식 노드를 가지는 트리이며 일반적으로 왼쪽 자식과 오른쪽 자식으로 구분됩니다. - 이진 탐색 트리, 완전 이진 트리, 균형 이진 트리 등의 종류가 있습니다. ### 3-2) 이진 탐색 트리 - 이진 트리의 한 종류로, 왼쪽 자식은 부모보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 가집니다. 효율적인 검색, 삽입 및 삭제 연산을 지원한다는 장점이 있습니다. ### 3-3) 균형 이진 트리 - 트리의 깊이가 최소한으로 유지되는 이진 트리입니다. ### 3-4) 이진 힙 - 완전 이진 트리의 일종으로, 특정한 순서를 유지하는 트리입니다. 최대 힙과 최소 힙이 있으며, 각각 부모 노드가 자식 노드보다 크거나 작은 값을 가집니다. 이진 힙은 우선순위 큐를 구현하는 데 자주 사용됩니다.
SunnnySong commented 5 months ago

1️⃣ 배열, 연결 리스트, 스택, 큐의 특징과 iOS에서의 구현 방법을 설명해주세요.

스택

큐

배열

연결 리스트

2️⃣ 해시 테이블의 개념, 충돌 해결 방법을 설명해주세요.

해시 테이블

해시 충돌

3️⃣ 트리 자료구조의 종류(예: 이진 트리, 이진 탐색 트리, AVL 트리)을 설명해주세요.

트리 자료구조

이진 트리, Binary Tree

이진 탐색 트리, Binary Search Tree