▶️

기본 자료구조(Basic Data-Structure)

1. 기본 자료구조(Basic Data-Structure)

Basic Data-Structure

•

자료구조는 자료를 저장하는 구조를 말합니다.

Ex) Stack, Queue, Tree, Graph ...

•

특정 목적에 따라 자료를 저장하는 방법이 달라 목적(각 장단점에 의거)에 맞게 사용할 수 있어야 합니다.

•

저장되어 있는 자료구조를 바탕으로 의미있는 결과를 도출하는 과정을 알고리즘이라고 합니다.

•

가장 기본이 되는 자료구조 : 변수, 배열

2. 배열 VS 연결 리스트

	배열(Array / ArrayList)	연결 리스트(Linked List)
장점	탐색이 빠름	배열에 비해 삽입/삭제 연산이 빠름
단점	삽입/삭제 연산이 느림	배열에 비해 탐색이 느림
탐색 시간 복잡도	O(1)	O(N)
삽입 시간 복잡도	평균적으로 O(N)	평균적으로 O(1)
삭제 시간 복잡도	평균적으로 O(N)	평균적으로 O(1)

3. 캡슐화(Encapsulation)

Encapsulation

•

자료구조 구현의 핵심이라고 할 수 있습니다.

•

자료구조를 사용하는 사람은 자료구조가 어떻게 동작하는지 알 필요가 없도록 설계해야 합니다.

•

구현한 사람외에 사용하는 사람은 사용법만 알아야 합니다.

4. 구조체(Struct)

Struct

•

구조체는 캡슐화를 통해 구현하며, 캡슐화를 구현하기 위해 사용합니다.

•

하나의 자료형(Type)을 정의할 수 있습니다.

•

여러 프로퍼티와 메소드로 이루어져 있어, 관련된 데이터끼리 묶을 수 있습니다.

5. 스택(Stack)

Stack

•

Computer Science의 대표적인 자료구조 중 하나입니다.

•

Linear(선형) 자료구조이며, 자료를 쌓으면서 저장하는 자료구조입니다.

•

Last In First Out(LIFO) 특징을 가지고 있어, 순서를 뒤집거나 발자취를 기록할 때 사용할 수 있습니다.

•

Push/Pop 연산이 가능합니다.

•

Stack Overflow : Stack은 정해진 크기가 있어, 용량이 다 찼음에도 불구하고 데이터를 삽입할 경우를 말합니다.

•

Stack Underflow : Stack이 비었음에도 불구하고 데이터를 삭제하려고 하는 경우를 말합니다.

//MARK: - Type
struct Stack {
    //MARK: - Property
    var array: [Int]
    var len: Int
    var capacity: Int

    //MARK: - Initializer
    init(_ capacity: Int) {
        self.capacity = capacity
        self.array = Array(repeating: 0, count: capacity)
        self.len = 0
    }

    //MARK: - Method
    mutating func push(_ data: Int) -> Void {
        if len >= capacity {
            print("Overflow")
        } else {
            self.array[self.len] = data
            self.len += 1
        }
    }

    mutating func pop() -> Void {
        if self.len <= 0 {
            print("Underflow")
        } else {
            self.array[self.len - 1] = 0
            self.len -= 1
        }
    }

    func top() -> Int {
        return self.len <= 0 ? -1 : self.array[len - 1]
    }
}

Swift

복사

6. 큐(Queue)

Queue

•

Stack과 함께 Computer Science의 기초 자료구조 중 하나입니다.

•

First In First Out(FIFO) 구조이며, Linear(선형) 자료구조입니다.

•

Queue Overflow : Queue의 용량보다 데이터를 더 넣으려고 하는 경우를 말합니다.

•

Queue Underflow : Queue에 데이터가 없는데 데이터를 삭제하려고 하는 경우를 말합니다.

•

단순 투 포인터로 큐를 구현하게 되는 경우 push / pop 연산시 두 포인터가 모두 증가만 하게되므로. 앞의 공간에 대한 낭비가 발생할 수 있습니다.

7. 원형 큐의 개념과 구현방법(Circular Queue)

Circular Queue

•

선형큐의 공간 낭비의 단점을 해결하기 위한 큐입니다.

•

선형큐에 비해 공간 활용 능력이 우수합니다.

•

원소의 개수를 유지하는 별도의 변수가 필요합니다.

•

front, rear 투 포인터가 끝에 도달하게되면 push / pop 연산시 다시 처음으로 되돌리는 원형의 형태입니다.

//MARK: - Type
struct Queue {
    //MARK: - Property
    private var array: [Int]
    private var f: Int
    private var r: Int
    private var capacity: Int

    //MARK: - Initializer
    init(_ capacity: Int) {
        self.capacity = capacity
        self.array = Array(repeating: 0, count: capacity)
        self.f = 0
        self.r = 0
    }

    //MARK: - Method
    mutating func push(_ data: Int) -> Void {
        if self.r >= self.capacity {
            print("Overflow")
        } else {
            self.array[self.r] = data
            self.r += 1
        }
    }

    mutating func pop() -> Void {
        if self.r - self.f <= 0 {
            print("Underflow")
        } else {
            self.array[self.f] = 0
            self.f += 1
        }
    }

    func front() -> Int {
        return self.r - self.f <= 0 ? -1 : self.array[self.f]
    }

    func size() -> Int {
        return self.r - self.f
    }
}

Swift

복사

8. 스택 & 큐 정리(Stack & Queue Summary)

Summary

•

특정 자료구조가 무엇인지 아는 것은 중요하지 않고, 의도에 맞게 사용하는 능력이 중요합니다.

•

올바른 괄호 판단 문제는 대표적인 stack 자료구조를 활용하는 문제입니다.

•

Stack과 Queue에는 상태(status) 즉, 해야하는 작업이 저장된다고 볼 수 있습니다.

•

Stack의 경우 함수 호출에 대한 복귀 주소 즉, 발자취를 기록을 해두며, 이를 Call Stack이라고 합니다.(Stack의 Scheduling : 재귀호출)

•

Queue의 경우 Stack과 달리 상태의 의존관계가 없을 때 즉, 해야 하는 작업을 진행할 때 다른 작업에 영향을 받지 않고 순서대로 처리하며, 대표적으로 스케쥴링, 병렬화에 많이 사용됩니다.

9. 트리(Tree)

Tree

•

트리 역시 자료를 담는 Computer Science의 기초 자료구조 중 하나입니다.

•

계층형(Hierarchy) 자료구조입니다.

•

정점(Node), 간선(Edge)로 이루어져 있으며, 간선은 두 정점을 잇는 선을 말합니다.

•

부모와 자식관계를 가지며 레벨은 높이를 뜻합니다.

•

트리는 그 안에 또 트리가 존재하며(재귀적 성질), 이를 서브트리(Subtree)라고 합니다.

•

최상위 부모노드를 root라고 합니다.

10. 트리의 순회(Tree Traversal)

Tree Traversal

•

트리 내에 어떠한 자료가 담겨 있는지를 알기 위한 방법입니다.

•

순회하는 방법은 많지만, 재귀적 성질을 이용해서 순회하는 방법이 젤 중요합니다.

11. 이진 트리 재귀적 순회 방법

Tip

•

자식노드가 2개 이하인 트리를 Binary Tree(이진 트리)라고 함

•

전위 순회 : Root - L(Left Subtree) - R(Right Subtree)

•

중위 순회 : L(Left Subtree) - Root - R(Right Subtree)

•

후위 순회 : L(Left Subtree) - R(Right Subtree) - Root

•

세가지 순회방법이 목적은 트리 내의 자료를 탐색하는 것으로 같지만, 특성이 다릅니다.

//MARK: - Type
struct Node {
    //MARK: - Property
    var left: Int
    var right: Int

    //MARK: - Initializer
    init(_ left: Int, _ right: Int) {
        self.left = left
        self.right = right
    }
}

//MARK: - Function
func preOrder(_ tree: [Node], _ root: Int) -> Void {
    if root == -1 {
        return
    }

    print("\\(root) ", terminator: "")
    preOrder(tree, tree[root].left)
    preOrder(tree, tree[root].right)
}

func inOrder(_ tree: [Node], _ root: Int) -> Void {
    if root == -1 {
        return
    }

    inOrder(tree, tree[root].left)
    print("\\(root) ", terminator: "")
    inOrder(tree, tree[root].right)
}

func postOrder(_ tree: [Node], _ root: Int) -> Void {
    if root == -1 {
        return
    }

    postOrder(tree, tree[root].left)
    postOrder(tree, tree[root].right)
    print("\\(root) ", terminator: "")
}

Swift

복사

12. 우선순위 큐(Priority Queue)

Priority Queue

•

Tree를 활용하는 대표적인 예제입니다.

•

원소를 제거할 때, 우선순위가 가장 높은 원소를 제거합니다.

•

배열로 우선순위 큐를 구현하게 되면, 삽입 연산은 효율적이지만 삭제 연산의 경우 비효율적일 수 있습니다.

13. 힙(Heap)

Heap

•

Heap 자료구조는 부모의 우선순위가 항상 자식보다 높은 완전이진트리입니다.

◦

자식노드가 2개 이하인 이진트리 이면서, 값이 왼쪽부터 채워지는 트리를 완전이진트리라고 합니다.

•

Heap에 값을 삽입하게 되면, 완전이진트리 특성에 따라 왼쪽부터 채워지고, 부모와 자식 사이의 우선순위를 비교하여 트리를 재구성해야 합니다.

•

노드가 n개일 때, 높이가 대략 log n이므로 높이가 1개 증가할 때 마다 노드는 약 2배 증가하게 됨을 알 수 있습니다.

•

즉, 삽입 연산 시 최악의 경우 트리의 높이 만큼 비교 연산을 수행 하므로, O(log n)의 시간복잡도를 가집니다.

•

Heap에서 삭제 연산을 하게 되면, 우선순위가 가장 높은 root를 삭제하고, 가장 끝에 있는 자식 노드를 root로 옮기고 우선순위를 비교하여 트리를 재구성해야 합니다.

•

삽입 연산과 마찬가지로 root에서 최대로 트리의 높이 만큼 내려올 수 있으므로, O(log n)의 시간복잡도를 가집니다.

14. 우선순위 큐 구현(배열)

//MARK: - Type
struct PriorityQueue {
    //MARK: - Property
    private var data: [Int]
    private var len, capacity: Int

    //MARK: - Initiailzer
    init(_ capacity: Int) {
        self.capacity = capacity
        self.data = Array(repeating: 0, count: capacity + 10)
        self.len = 0
    }

    //MARK: - Method
    mutating func push(_ x: Int) -> Void {
        self.data[self.len] = x
        self.len += 1
    }

    mutating func pop() -> Void {
        var min: Int = self.data[0], minIndex: Int = 0
        for i in 0..<self.len {
            if min > self.data[i] {
                min = self.data[i]
                minIndex = i
            }
        }

        for i in minIndex..<self.len {
            self.data[i] = self.data[i + 1]
        }

        self.len -= 1
    }

    func top() -> Int {
        var min: Int = self.data[0]
        for i in 0..<self.len {
            min = min > self.data[i] ? self.data[i] : min
        }

        return min
    }
}

Swift

복사

15. 우선순위 큐 구현(힙)

//MARK: - Type
struct PriorityQueue {
    //MARK: - Property
    var data: [Int]
    var len, capacity: Int

    //MARK: - Initializer
    init(_ capacity: Int) {
        self.capacity = capacity
        self.data = Array(repeating: 0, count: self.capacity + 10)
        self.len = 1
    }

    //MARK: - Method
    mutating func push(_ x: Int) -> Void {
        self.data[self.len] = x
        self.len += 1

        var currentIndex: Int = self.len - 1
        while currentIndex > 1 {
            if self.data[currentIndex] < self.data[currentIndex >> 1] {
                let temp: Int = self.data[currentIndex]
                self.data[currentIndex] = self.data[currentIndex >> 1]
                self.data[currentIndex >> 1] = temp

                currentIndex >>= 1
            } else {
                break
            }
        }
    }

    mutating func pop() -> Void {
        self.data[1] = self.data[self.len - 1]
        self.data[self.len - 1] = 0
        self.len -= 1

        var currentIndex: Int = 1
        while true {
            var childIndex: Int = -1

            if self.len - 1 < (currentIndex << 1) {
                break
            } else if (0 < (currentIndex << 1) && (currentIndex << 1) <= self.len - 1) && (currentIndex << 1 + 1) > self.len - 1 {
                childIndex = currentIndex << 1
            } else {
                childIndex = (currentIndex << 1) < (currentIndex << 1 + 1) ? (currentIndex << 1) : (currentIndex << 1 + 1)
            }

            if self.data[currentIndex] > self.data[childIndex] {
                let temp: Int = self.data[currentIndex]
                self.data[currentIndex] = self.data[childIndex]
                self.data[childIndex] = temp

                currentIndex = childIndex
            } else {
                break
            }
        }
    }

    func top() -> Int {
        return self.data[1]
    }
}

Swift

복사

16. 우선순위 큐의 구현 요약

	배열	힙
삽입	O(1)	O(log n)
삭제	O(n)	O(log n)
탐색	O(n)	O(1)

Tip

•

삽입 연산이 배열이 빠르긴 하지만, 삭제 연산에서 차이가 많이 발생하므로 우선순위 큐를 구현해야 한다면 힙으로 구현하는 것이 바람직하다고 할 수 있습니다.

•

힙의 경우 완전이진트리이기 때문에, 배열을 이용하여 구현할 수 있습니다.