🖥️ Computer Science25 [Swift] 우선순위 큐(Priority Queue) 구현하기 우선순위 큐는 요소가 삽입될 때마다 우선순위에 따라 정렬되며, 가장 높은 우선순위의 요소가 먼저 처리됩니다. 이전에 구현한 Heap을 사용하여 우선순위 큐를 쉽게 구현할 수 있습니다. 아래는 PriorityQueue 구조체를 제네릭으로 정의한 코드입니다.struct PriorityQueue { private var heap: Heap var isEmpty: Bool { return heap.isEmpty } var count: Int { return heap.count } var peek: T? { return heap.peek } init(sort: @escaping (T, T) -> Bool) { he.. 2024. 9. 27. [Swift] 힙(Heap) 구현하기 Heap은 트리 기반의 자료구조로, 특정 우선순위에 따라 요소들을 정렬하는 기능을 제공합니다. Heap은 크게 두 가지 유형이 있습니다. 최소 힙은 작은 값이 먼저 나오도록 정렬하고, 최대 힙은 큰 값이 먼저 나오도록 정렬합니다. 제네릭을 이용해 Heap 구조체를 정의하고 주요 기능을 구현해보겠습니다.struct Heap { private var elements: [T] = [] private let priorityFunction: (T, T) -> Bool var isEmpty: Bool { return elements.isEmpty } var count: Int { return elements.count } var p.. 2024. 9. 27. [Swift] Dequeue 구현하기 Dequeue는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조로, 이를 통해 큐와 스택의 기능을 모두 수행할 수 있습니다. Dequeue를 구조체와 배열을 이용해 구현할 수 있습니다.제네릭을 활용하여 Dequeue 구조체를 정의하고, 주요 기능들을 구현해보겠습니다. struct Deque { private var enqueue: [T] = [] // 뒤쪽에서 요소를 추가/제거하는 배열 private var dequeue: [T] = [] // 앞쪽에서 요소를 추가/제거하는 배열 var count: Int { return enqueue.count + dequeue.count } var isEmpty: Bool { return enque.. 2024. 9. 27. [Swfit] 큐(Queue) 구현하기 Queue를 구조체와 배열을 이용해 구현할 수 있습니다.먼저 제네릭을 활용해 Queue 구조체를 정의하고, 주요 기능을 구현해보겠습니다. struct Queue { private var queue: [T] = [] var isEmpty: Bool { return queue.isEmpty } var count: Int { return queue.count } var peek: T? { return queue.first } mutating func enqueue(_ element: T) { queue.append(element) } mutating func dequeue() .. 2024. 9. 27. [Swift] 스택(Stack) 구현하기 Stack을 구조체와 배열로 구현할 수 있습니다.먼저 제네릭을 이용해 Stack 구조체를 정의하고, 주요 기능을 구현해보겠습니다. struct Stack { private var stack: [T] = [] var isEmpty: Bool { return stack.isEmpty } var count: Int { return stack.count } var peek: T? { return stack.last } mutating func push(_ element: T) { stack.append(element) } mutating func pop() -> T? { .. 2024. 9. 27. [디자인 패턴] 팩토리 패턴 (Factory Pattern) 팩토리 메서드 패턴 (Factory Method Pattern) 객체를 생성하기 위한 인터페이스를 정의하는데, 어떤 클래스의 인스턴스를 만들지는 서브 클래스에서 결정하게 만드는 패턴 클래스의 인스턴스를 만드는 일을 서브클래스에게 맡기는 것 부모 추상 클래스는 인터페이스에만 의존하고 실제로 어떤 구현 클래스를 호출할지는 서브 클래스에서 구현 새로운 구현 클래스가 추가되어도 기존 Factory 코드의 수정 없이 새로운 Factory를 추가 가능 객체의 생성을 담당하는 클래스를 한 곳에서 관리하여 결합도를 줄이기 위하여 팩토리 패턴이 등장 결합도: 한 클래스에 변경점이 얼마나 다른 클래스에 영향을 주는가를 의미 팩토리 메서드 패턴의 장점 객체 간의 결합도를 낮출 수 있음 단일 책임 원칙을 따름 프로그램의 코드.. 2023. 3. 17. [디자인 패턴] 싱글톤 패턴 (Singleton Pattern) 싱글톤 패턴 (Singleton Pattern) 하나의 클래스에 오직 하나의 인스턴스 만 가지는 패턴 데이터베이스 연결 모듈에 많이 사용 하나의 인스턴스를 만들어 놓고 해당 인스턴스를 다른 모듈들이 공유하며 사용 인스턴스 생성 비용이 줄어듦 동시성(Concurrency) 문제를 고려해야 함 싱글톤 패턴을 사용하는 이유 최초 한 번만 인스턴스를 생성하여 고정된 메모리 영역을 사용하기 때문에, 메모리 낭비 방지 이미 생성된 인스턴스를 활용해 속도가 빠름 싱글통 인스턴스가 전역으로 사용되기 때문에, 다른 클래스 간에 데이터 공유가 쉬움 인스턴스가 절대적으로 한 개만 존재하는 것을 보증하고 싶은 경우에 사용 싱글톤 패턴의 단점 싱글톤 인스턴스가 혼자 너무 많은 일을 하거나, 많은 데이터를 공유시킬 경우에 다른 .. 2023. 3. 16. [자료구조] 해시 테이블(Hash Table) 해시 테이블(Hash Table) 해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 해시함수(Hash Function)를 사용하여 변환한 값을 index로 삼음 해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 함 대표적인 예로 파이썬의 dictionary, 루비의 Hash, 자바의 Map 등이 있음 해시 테이블의 특징 기본 연산으로는 search, insert, delete가 있음 순차적으로 데이터를 저장하지 않음 key를 통해서 value를 얻을 수 있음 => 이진탐색트리나 배열에 비해 속도가 빠름 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적 value는 중복 가능하.. 2023. 3. 15. [자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority) 순서에 상관없이 우선수위가 높은 데이터가 먼저 나가는 형태의 자료구조 우선순위 대기열이라고도 함 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조 일반적으로 힙(Heap)을 사용하여 구현 모든 항목에는 우선순위가 있음 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 큐에서 제외 두 요소의 우선순위가 같은 경우 큐의 순서에 따라 제공 우선순위 큐 구현 방법 배열, 연결리스트, 힙을 이용하여 구현 가능 구현 방법 삽입 (enqueue) 삭제 (denqueue) 배열 (unsorted array) O(1) O(N) 연결 리스트 (unsorted linked list) O(1) O(N) 정렬된 배열 (sorted array) O(N) O(1) .. 2023. 3. 13. [자료구조] 힙(Heap) 힙(Heap) 완전 이진트리 기반의 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐를 위해 만들어진 자료구조 반정렬상태(느슨한 정렬상태) 유지 큰 값이 상위에 있고 작은 값이 하위에 있는 정도 중복된 값 허용 힙의 종류 최대 힙(max heap) 부모 노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진트리 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 이진트리 힙의 활용 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 힙의 구현 힙을 저장하는 표준적인 자료구조는 배열 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않음 특정 위치의 노드 번호는 새로운.. 2023. 3. 13. 이전 1 2 3 다음 반응형