12. 스파르타 코딩클럽 [사전캠프 - 자료구조/메모리 구조 및 ARC]

(스타터 과정이 아닌, 마스터 과정을 정리한 내용)

 

기본

⎮ 자료 구조

  1. 배열(Array) : 데이터를 순차적으로 저장하는 자료 구조

    - 인덱스를 사용해 특정 요소에 접근

    - 특징 : O(1)과 같은 빠른 조회가 가능. 단, 배열의 앞이나 중간에 삽입하거나 삭제할 시 성능 저하

var numbers = [1, 2, 3, 4, 5]
numbers.append(6)  // 배열 끝에 6을 추가
print(numbers)     

// [1, 2, 3, 4, 5, 6]

 

  2. *큐(Queue) : 선입 선출(FIFO, First In First Out) 구조.

     - 데이터를 한쪽에 삽입하고, 반대쪽에서 제거

     - 사용 사례 : 프린터 대기열 작업, *너비 우선 탐색

     - enqueue() : 큐에 데이터 삽입 / dequeue() : 큐에서 데이터 제거

struct Queue<T> {
    private var elements: [T] = []
    
    mutating func enqueue(_ element: T) {
        elements.append(element)
    }
    
    mutating func dequeue() -> T? {
        return elements.isEmpty ? nil : elements.removeFirst()
    }
}

큐는 '선입선출' 구조로, 가장 먼저 받은 데이터를 가장 먼저 소모하는 방식

  3. *스택(Stack) : 후입 선출(LIFO, Last In First Out) 구조.

      - 데이터를 한쪽에서 삽입하고 제거

      - 사용 사례 : 함수 호출 스택, 괄호 검사

      - push() : 스택에 데이터 삽입 / pop() : 스택에서 데이터 제거

        * 스택은 가장 최근에 삽입된 데이터를 먼저 제거하는 구조

struct Stack<T> {
    private var elements: [T] = []
    
    mutating func push(_ element: T) {
        elements.append(element)
    }
    
    mutating func pop() -> T? {
        return elements.popLast()
    }
}

스택은 '후입선출' 구조로, 마지막에 들어간 데이터를 가장 먼저 소모하는 방식

⎮ 메모리 구조 및 ARC

  1. 메모리 구조

     - Stack : 함수 호출과 지역 변수들이 저장되는 영역. 값 타입(struct, enum 등)의 인스턴스가 Stack에 저장

     - Heap : 동적으로 할당된 메모리 영역, 참조 타입(Class 등)의 인스턴스를 저장. 프로그램 실행 중에 동적으로 변하는 데이터 저장

     - Code : 실행 중인 코드가 저장되는 영역

     - Data : 코드 실행 시 유지되어야 하는 데이터(전역 변수나 정적 변수)가 저장

 

  2. ARC(Automatic Reference Counting) : Swift의 메모리 관리 방식(메모리 관리를 자동으로 처리하는 시스템)

      객체가 메모리에서 해제되어야 할 때를 결정하기 위해서 참조 회수를 추적, 참조가 없다면 메모리에서 해제

     - 강한 참조(Strong Reference) : 기본적으로 객체를 참조하는 방식, 참조 횟수가 0이 될때까지 메모리에 할당 

     - 순환 참조(Circular Reference) : 두 개 이상의 객체가 서로를 참조하면서 메모리에서 해제되지 않는 문제(메모리 누수)

         * 해결 방법 : weak(약한 참조) 또는 unowned(소유하지 않는 참조) 키워드 사용

 

⎮ 순환 참조(Circular Reference)

// 순환 참조 예제 : Person 객체가 Pet 객체를 참조하고, Pet 객체가 다시 Person 객체를 참조하는 상황

class Person {
    var name: String
    var pet: Pet?

    init(name: String) {
        self.name = name
    }
}

class Pet {
    var owner: Person?
}

let person = Person(name: "Alice")
let pet = Pet()

person.pet = pet
pet.owner = person // 순환 참조 발생

 

  여기서 순환 참조가 발생하는 이유는,

Person 클래스는 name을 저장하는 name 변수와, Pet? 타입의 pet 변수를 가지고 있고,

Pet 클래스는 owner라는 Person? 타입의 변수를 가지고 있음.

 

  Person 인스턴스와 Pet 인스턴스를 생성한 후, 인스턴스의 속성을 서로를 참조하는 구조가 생김.

person.pet = pet 일 때, Person 인스턴스가 Pet 인스턴스를 참조하고,

pet.owner = person 일 때, Pet 인스턴스가 Person 인스턴스를 참조함.

 

⎮ 순환 참조 해결하기

   순환 참조를 해제하려면 둘 중의 하나를 약한 참조로 만들면 됨.

// 순환 참조 해제
class Pet {
    weak var owner: Person?  // 약한 참조 사용
}

  weak를 사용하면 Pet 객체는 Person 객체에 대한 강한 참조를 하지 않게 되어 순환 참조가 방지됨

weak 참조는 객체가 메모리에서 해제되면 자동으로 nil로 설정됨

 

⎮ * 큐(Queue)

// Queue 문법
struct Queue<T> {
    private var elements: [T] = []
    
    mutating func enqueue(_ element: T) {
        elements.append(element)
    }
    
    mutating func dequeue() -> T? {
        return elements.isEmpty ? nil : elements.removeFirst()
    }
}

var queue = Queue<Int>()   // 빈 큐 생성

queue.enqueue(10)          // 10을 큐에 추가
queue.enqueue(20)          // 20을 큐에 추가
queue.enqueue(30)          // 30을 큐에 추가

print(queue.dequeue())     // 10을 제거하고 출력 (큐에서 첫 번째 요소 제거)
print(queue.dequeue())     // 20을 제거하고 출력
print(queue.dequeue())     // 30을 제거하고 출력
print(queue.dequeue())     // nil (큐가 비었으므로 nil 반환)

 

  코드를 뜯어보자

struct Queue<T> { ... }

/*
여기서 <T>는 제네릭 type으로 어떤 요소든 상관없이 다 받을 수 있게 해줌
*/

private var elements: [T] = []

/*
여기서 elements는 배열의 이름이고,
private는 접근 제어자로써, 이 배열이 Queue 외부에서는 접근할 수 없도록 숨기는 것.
Queue 내부에서만 배열에 접근하고 수정할 수 있도록 함.
Queue를 비우기 위해 []로 초기화
*/

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

/*
mutating 키워드는 이 함수가 Queue 구조체의 상태를 변경하는 것을 의미함.
구조체는 값 타입이기 때문에 메소드 내에서 구조체의 상태를 변경하려면 mutating을 명시해야 함.

enqueue(_ element: T)에서 parameter 이름을 _로 생략하였기 때문에
이 함수를 호출할 때는 enqueue(someValue)로 간단히 호출할 수 있음.
예를 들면 6이라는 숫자를 추가하고자 할 때, enqueue(6) 이렇게 간단히 호출이 가능함.

elements.append(element)를 통해 배열 마지막에 element를 추가함
*/

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

/*
mutating을 통해 값을 변환할 것임을 유추할 수 있음. 
위의 enqueue와는 다르게, dequeue에서는 값을 빼내는 것이기 때문에 parameter가 없음
큐가 비었을 경우에는 nil을 return해야 하므로, 메소드가 T?를 return하도록 설정

elements.isEmpty을 통해 큐가 비었는지 확인하고,
큐가 비었으면 nil을 반환하며, 그렇지 않을 때 첫번째 요소를 지우고 값을 반환

elements.isEmpty ? nil : elements.removeFirst()은 삼항 연산자로써
조건 ? True : False의 형태로 둘 중 하나를 선택할 수 있게 함.
*/

 

  * 큐(Queue)에서 배열(Array Type)을 사용하는 이유는 무엇일까?

  - 배열은 순차적인 데이터 저장이 가능함

  - .append와 .removeFirst()를 사용한 효율적인 연산이 가능함

  - 인덱스로 접근할 때, 처음과 마지막 요소에 쉽게 접근할 수 있음

 

 

⎮ * 너비 우선 탐색

  너비 우선 탐색 : 인접한 노드들을 우선으로 탐색하는 방식

   위의 그림에서 볼 수 있듯, BFS는 인접한 노드부터 우선적으로 탐색함

 같은 레벨의 노드를 탐색하고 다음 레벨로 넘어가는 방식(A, B, C, D냐 A, C, D, B냐는 상관 없이 같은 레벨의 노드를 탐색)

 

 

⎮ * 깊이 우선 탐색

깊이 우선 탐색 :  한 방향으로 가능한 깊게 탐색. 더 이상 갈 곳이 없으면 뒤로 돌아와 다른 경로를 탐색하는 방식 

위의 그림에서 볼 수 있듯, DFS는 모든 노드를 깊게 탐색함

경로를 추적하거나 특정 경로를 찾는 데 유용

스택(Stack)을 사용하여 구현하거나 재귀(Recursive)를 사용하여 구현

 

⎮ * 스택(Stack)

// 스택 문법
struct Stack<T> {
    private var elements: [T] = []
    
    mutating func push(_ element: T) {
        elements.append(element)
    }
    
    mutating func pop() -> T? {
        return elements.popLast()
    }
}

var stack = Stack<Int>()   // 빈 스택 생성

stack.push(10)             // 10을 스택에 추가
stack.push(20)             // 20을 스택에 추가
stack.push(30)             // 30을 스택에 추가

print(stack.pop())         // 30을 제거하고 출력 (스택에서 마지막 요소 제거)
print(stack.pop())         // 20을 제거하고 출력
print(stack.pop())         // 10을 제거하고 출력
print(stack.pop())         // nil (스택이 비었으므로 nil 반환)

 

  코드를 뜯어보자

struct Stack<T> { ... }

/*
Stack을 제네릭 Type으로 선언. 어떤 값이든 다 받을 수 있음
*/

private var elements: [T] = []

/*
큐 안에서만 요소를 참조할 수 있도록 private 접근 제어자 사용
elements를 배열 Type으로 설정. 값을 빈 배열[]으로 초기화
*/

mutating func push(_ element: T) {
    elements.append(element)
}

/*
mutating 키워드는 이 함수가 Queue 구조체의 상태를 변경하는 것을 의미함.
구조체는 값 타입이기 때문에 메소드 내에서 구조체의 상태를 변경하려면 mutating을 명시해야 함.
elements.append(element)를 통해 배열 마지막에 element를 추가함
*/

mutating func pop() -> T? {
    return elements.popLast()
}

/*
mutating을 통해 값을 변환할 것임을 유추할 수 있음
T?를 통해 nil이 리턴 될 수 있음을 유추할 수 있음
popLast() - 마지막에 넣은 데이터를 제거하고 반환하는 함수
*/

 

⎮ * 제네릭 파라미터(Generic Parameter)

  1. 제네릭 파라미터 : 타입을 변수처럼 다룰 수 있게 해주는 기능

     - 코드 재사용성 증가, 타입 안전성 증가

     - 타입을 나중에 지정할 수 있음(타입에 구애를 받지 않음)

     - 타입 안전성 증가(컴파일러가 타입 오류를 미리 확인해줌으로써, 런타임에서 발생하는 오류를 줄일 수 있음)

// 제네릭 사용 전 코드
func addIntegers(a: Int, b: Int) -> Int {
    return a + b
}

let sum = addIntegers(a: 3, b: 5)  // Int 타입의 값들만 더할 수 있음
// Double Type이나 다른 Type의 값을 더하려면 같은 함수가 각각 필요함

// 제네릭 사용 후 (타입을 파라미터로 받는다면?)
func add<T: Numeric>(a: T, b: T) -> T {
    return a + b
}

let intSum = add(a: 3, b: 5)        // T가 Int로 결정됨
let doubleSum = add(a: 3.5, b: 2.1)

// 구조체에서의 제네릭 파라미터
struct Box<T> {
    var value: T

    init(value: T) {
        self.value = value
    }
}

let intBox = Box(value: 10)    // Box<Int> 타입
let stringBox = Box(value: "Hello")  // Box<String> 타입

 

실습

⎮ 큐(Queue) 구현하기

큐(Queue) 구현하기: 정수를 저장하는 Queue 구조체를 구현하세요.
enqueue()로 데이터를 삽입하고, dequeue()로 데이터를 제거합니다.
큐의 현재 상태를 출력하는 메서드를 추가하세요.

struct Queue {
    private var nums: [Int] = []

    mutating func enqueue(_ num: Int) {
        nums.append(num)
    }

    mutating func dequeue() -> Int? {
        return nums.isEmpty ? nil : nums.removeFirst()
    }

	// 큐의 현재상태를 출력하는 함수
    func printQueue() {
        print("Queue contents: \(nums)")
    }

	// 큐가 비어있는지 확인하는 함수 (큐가 비어있으면 True로 리턴)
    func isEmpty() -> Bool {
        return nums.isEmpty
    }
}

var queue = Queue()

// 데이터 삽입
queue.enqueue(10)
queue.enqueue(20)

// 큐 상태 출력
queue.printQueue()  // 출력: Queue contents: [10, 20]

// 데이터 제거
queue.dequeue()  // 10이 제거됨

// 큐 상태 출력
queue.printQueue()  // 출력: Queue contents: [20]

// 큐가 비었는지 확인
print(queue.isEmpty())  // 출력: True

 

⎮ 스택 구현하기

문자열을 저장하는 Stack 구조체를 구현하세요.
push()로 데이터를 삽입하고, pop()으로 데이터를 제거합니다.
스택의 최상단 값을 반환하는 메서드를 추가하세요.

struct Stack {
    private var words : [String] = []

    mutating func push(_ word: String) {
        words.append(word)
    }

    mutating func pop() -> String? {
        return words.popLast()
    }

    func popData() -> String? {
        return words.last
    }
}

var stack = Stack()
stack.push("Hi")
stack.push("Hello")
stack.printStack()
// ["Hi", "Hello"]

stack.pop()
stack.printStack()
// ["Hi"]

 

⎮ 순환 참조 문제 구현하기

두 클래스를 생성하세요:
Person 클래스: 이름을 저장하는 속성(name)과 애완동물(pet) 속성을 가짐.
Pet 클래스: 주인(owner) 속성을 가짐.
서로를 참조하는 인스턴스를 생성하고 순환 참조 문제를 확인하세요.

class Person {
    var name: String
    var pet: Pet?

    init(name: String) {
        self.name = name
    }
}

class Pet {
    var owner: Person?

    init(owner: Person?) {
        self.owner = owner
    }
}

// 순환 참조 발생
var person1 = Person(name: "Steve")
var pet = Pet(owner: person1)

person.pet = pet  // Person이 Pet을 참조
pet.owner = person  // Pet이 Person을 참조

 

⎮ 순환 참조 해결 방법

weak 키워드를 사용해 순환 참조 문제를 해결하세요.
해결 후, 두 인스턴스가 정상적으로 메모리에서 해제되는지 확인하세요.

class Person {
    var name: String
    var pet: Pet?

    init(name: String) {
        self.name = name
    }

    deinit {
        print("\(name) 해제 되었습니다.")
    }
}

class Pet {
    weak var owner: Person?

    init(owner: Person?) {
        self.owner = owner
    }

    deinit {
        print("Pet이 해제 되었습니다.")
    }
}

// 테스트 코드
var person: Person? = Person(name: "John")
var pet: Pet?  = Pet(owner: person)

person?.pet = pet

person = nil
pet = nil