자료구조의 종류와 iOS 개발에서 자주 사용되는 자료구조에 대해 설명해주세요.

[ujhong7]

자료구조란?

자료구조는 데이터를 정리하는 방법입니다.

• 데이터를 어떻게 저장할지
• 데이터를 어떻게 찾을지
• 데이터를 어떻게 수정하거나 삭제할지

이러한 작업들을 효율적으로 처리하도록 설계된 구조입니다.

---

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

  배열 (Array)

  • 특징:
    • 고정된 크기를 가지며 연속된 메모리 공간에 데이터가 저장됨.
    • 인덱스를 사용하여 데이터를 빠르게 접근 가능 (시간 복잡도: O(1)).
    • 삽입 및 삭제가 비효율적 (시간 복잡도: O(n)).
  • iOS에서의 구현:
    • Swift의 Array는 동적 배열로, 크기가 자동으로 조정되며 메모리를 효율적으로 관리함.

  연결 리스트 (Linked List)

  • 특징:
    • 노드(Node)가 데이터와 다음 노드를 가리키는 포인터를 포함.
    • 메모리 공간이 비연속적이며, 크기가 동적으로 변경 가능.
    • 삽입 및 삭제가 효율적 (시간 복잡도: O(1)~O(n)).
    • 탐색은 비효율적 (시간 복잡도: O(n)).
  • iOS에서의 구현:
    • Swift에는 기본 제공되지 않지만, class 또는 struct를 사용하여 직접 구현 가능.

  스택 (Stack)

  • 특징:

    • LIFO(Last In, First Out) 원칙에 따라 동작.
      

    • 삽입과 삭제는 한쪽 끝에서만 수행.

    • 삽입(push) 및 삭제(pop) 연산의 시간 복잡도: O(1).

  • iOS에서의 구현:
    • Swift의 Array를 사용하여 스택을 쉽게 구현할 수 있음:

      var stack = [Int]()
      stack.append(10) // push
      let top = stack.popLast() // pop

  큐 (Queue)

  • 특징:

    • FIFO(First In, First Out) 원칙에 따라 동작.
      

    • 삽입(enqueue)은 뒤쪽에서, 삭제(dequeue)는 앞쪽에서 수행.

    • 삽입 및 삭제 연산의 시간 복잡도: O(1).

  • iOS에서의 구현:
    • Swift의 Array 또는 Deque(Double-ended Queue) 구조를 활용:

      var queue = [Int]()
      queue.append(10) // enqueue
      let front = queue.removeFirst() // dequeue

---

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

  해시 테이블(Hash Table)

  • 개념:
    • 키(Key)를 해시 함수(Hash Function)에 전달하여 인덱스를 생성하고 데이터를 저장.
    • 키-값 쌍으로 데이터를 저장하며, 빠른 검색이 가능 (시간 복잡도: 평균 O(1)).
    • 충돌(Collision): 서로 다른 키가 동일한 해시 값을 갖는 현상.
    • Key를 해시 함수를 이용해 해시 주소값(해시 테이블의 index)으로 변환합니다.
    • 해시 주소값(해시 테이블의 index)를 통해 해시 테이블에 접근하여 데이터를 저장하거나 조회합니다.
    • Key에 대한 산술 연산을 이용하여 해시 주소값(해시 테이블의 index)으로 만들어주는 것
    • Babbab님의 해시 테이블 개념 포스팅

  충돌 해결 방법

  1. 체이닝(Chaining):
     • 동일한 해시 값을 갖는 데이터를 연결 리스트로 연결.
     • 메모리를 더 사용하지만 간단하고 구현이 용이.
  2. 개방 주소법(Open Addressing):
     • 충돌이 발생하면 빈 공간을 찾아 데이터를 저장.
     • 탐사 방법:
       • 선형 탐사(Linear Probing): 한 칸씩 순차적으로 탐색.
       • 제곱 탐사(Quadratic Probing): 점차 큰 간격으로 탐색.
       • 이중 해싱(Double Hashing): 두 번째 해시 함수를 사용.
  3. 이중 해시(Hash Map + Tree):
     • 충돌 시, 데이터가 많은 경우 트리 구조를 활용하여 시간 복잡도를 O(log n)으로 유지.

  iOS에서의 구현

  • Swift의 Dictionary는 내부적으로 해시 테이블을 기반으로 구현됨:

    var hashTable: [String: Int] = [:]
    hashTable["key"] = 100
    let value = hashTable["key"] // 100
    

---

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

  이진 트리 (Binary Tree)

  • 특징:
    • 각 노드는 최대 두 개의 자식을 가짐.
    • 계층적 데이터 표현에 적합.
  • iOS에서의 활용:
    • Swift로 재귀를 사용하여 구현 가능:

      class TreeNode {
          var value: Int
          var left: TreeNode?
          var right: TreeNode?
          
          init(_ value: Int) {
              self.value = value
          }
      }

  ---

  이진 탐색 트리 (Binary Search Tree)

  • 특징:
    • 왼쪽 서브트리의 모든 값은 부모 노드보다 작고, 오른쪽 서브트리의 값은 크다.
    • 검색, 삽입, 삭제의 시간 복잡도: O(log n) (균형이 잘 잡힌 경우).
  • iOS에서의 활용:
    • 데이터 검색 및 정렬 알고리즘 구현에 활용.

  ---

  AVL 트리 (AVL Tree)

  • 특징:
    • 이진 탐색 트리의 일종으로, 각 노드의 왼쪽과 오른쪽 서브트리 높이 차가 1 이하로 유지.
    • 삽입 및 삭제 시 자동으로 균형을 맞춤.
    • 시간 복잡도: O(log n).
  • 장점:
    • 균형을 유지하므로 최악의 경우에도 검색, 삽입, 삭제가 효율적.

  ---

  트리의 기타 종류

  1. 레드-블랙 트리:

     • 노드가 색(빨간색/검정색)을 가지며, 균형을 유지하는 이진 탐색 트리.

  2. B-트리 및 B+-트리:

     • 대용량 데이터베이스 및 파일 시스템에서 사용.
     • 다수의 자식을 가지는 트리로, 디스크 읽기/쓰기를 최소화.