이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 이 글의 모든 출처는 https://jeonyeohun.tistory.com/327 이곳에 있습니다. 우선순위 큐(Priority Queue) 힙을 이용해서 가장 높은 우선순위에 있는 요소를 항상 제일 처음에 위치시키는 특별한 큐 가장 우선순위가 높은 요소가 큐에서 제거되면 그 다음 우선순위에 있는 요소가 큐의 첫 요소로 이동합니다. 힙에 대한 설명은 https://jerry311.tistory.com/55 에 있습니다. 우선순위 설정 우선순위 큐를 사용하려면 어떤 기준으로 우선순위를 정할지 지정해주어야 합니다. 지정 init(_ elements: [T] = [], _ sort: @escaping (T, T) -> Bool) { heap = Heap..

이글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 이글의 모든 내용에 대한 출처는 https://jeonyeohun.tistory.com/325 이곳입니다. 힙 이진트리를 사용해서 반정렬 상태로 유지하는 자료구조 힙은 트리의 루트 노드에 데이터들의 최솟값 혹은 최대값을 저장합니다. 최솟값을 루트에 둘 때는 최소힙, 최대값을 루트에 두면 최대힙이라고 합니다. 완전 이진트리 트리를 구성하는 모든 노드가 최대 2개의 자식노드를 가지는 자료구조 완전 이진트리는 아래와 같은 특징을 가집니다. 1. 각 높이에 있는 모든 노드가 자식노드를 가져야 다음 높이에 새 노드를 추가할 수 있습니다. 2. 가장 왼쪽부터 차례대로 노드를 채워야 합니다. 이 배열 기반의 이진트리를 이용해서 힙을 구현하겠습니다. 힙의 이진트리는..

이 글은 개인적인 공부를 위해 작성하는 것임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/105 을 방문해주세요! 그래프 노드(정점)과 간선(브랜치)로 이루어진 자료구조 연결되어있는 원소간의 관계를 표현한 자료구조 실생활의 현상이나 사물을 그래프로 활용할 수 있음 알고 있어야 할 그래프 관련 용어 노드(정점) 컴퓨터 과학에 쓰이는 기초적인 단위 즉, 위의 그림에서는 동그라미 하나가 노드다. 그래프에서 노드는 대응하는 개체를 나타내는 정점이다. 간선(브랜치) 객체 사이를 잇는 연결 경우에 따라 노드 사이를 잇는 각 연결의 강도를 나타내는 가중치를 갖는다. 인접 정점 간선에 의해 직접 연결된 노드 위의 그래프 그림에서 1의 인접 정점은 5와 2, 6의 인접 정점은 4 참고로 ..

덱 스택과 큐의 특성을 모두 갖는, 둘을 조합한 형태의 자료구조 덱의 ADT(Abstract Data Type)를 구성하는 핵심 함수 네가지의 기능은 다음과 같다. - 앞으로 넣기 - 뒤로 넣기 - 앞에서 빼기 - 뒤에서 빼기 덱은 머리에서 추가와 삭제가 이뤄지는 것은 물론 꼬리에 위치한 노드에서 추가와 삭제가 이뤄진다는 점에서 양방향 연결리스트를 기반으로 덱을 구현하는 경우가 많고, 이는 덱 구현에 있어서 매우 좋은 선택이라 할 수 있다. 여기서 간단하게만 덱을 구현해보았다. class Deque{ var enQueue: [T] var deQueue: [T] = [] var count: Int { return enQueue.count + deQueue.count } var isEmpty: Bool { ..

Stack LIFO : 마지막으로 들어온 놈이 첫번째로 나가는 자료구조 struct Stack { private var stack: [T] = [] public var count: Int { return stack.count } public var isEmpty: Bool { return stack.isEmpty } public mutating func push(_ element: T) { stack.append(element) } public mutating func pop() -> T? { return isEmpty ? nil : stack.popLast() } } 사용 var myStack = Stack() myStack.push(10) myStack.pop() 시간복잡도는 O(1)이다. 그런데 S..

큐 선입선출(FIFO) : 먼저들어온 놈이 먼저 나가는 자료구조 Swift 에서의 구현 struct Queue { private var queue: [T] = [] public var count: Int { return queue.count } public var isEmpty: Bool { return queue.isEmpty } public mutating func enqueue(_ element: T) { queue.append(element) } public mutating func dequeue() -> T? { return isEmpty ? nil : queue.removeFirst() } } 그러나 이 방법은 dequeue시에 element들이 자리를 당기는 과정에서 O(n)의 시간복잡도가 ..

메모리 모델 stack 영역 프로그램이 자동으로 사용하는 메모리 영역이다. 함수호출과 관계되는 지역변수와 매개변수가 저장된다. 함수 호출 시 생성되며, 함수가 끝나면 반환된다. stack 사이즈는 각 프로세스마다 할당되지만 프로세스가 메모리에 로드될 때 stack 사이즈가 고정되어 있어 런타임 시 stack 사이즈를 바꿀 수 없다. 명령 실행 시 자동으로 증가 or 감소하기 때문에 보통 메모리의 마지막 번지를 지정한다. heap 영역 필요에 의해 동적으로 할당할 때 사용하는 메모리 영역이다. C에서 malloc(), calloc() 등의 함수를 사용하여 메모리 크기를 할당할 수 있다. 메모리 주소 값에 의해서만 참조되는 영역이다. stack영역과 heap영역은 사실 같은 공간을 공유한다. heap이 메모..