이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 이 글의 모든 출처는 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. 가장 왼쪽부터 차례대로 노드를 채워야 합니다. 이 배열 기반의 이진트리를 이용해서 힙을 구현하겠습니다. 힙의 이진트리는..

🖐🏻 SOLID 5원칙 1️⃣ SRP (단일책임의 원칙) 한 클래스는 하나의 책임만 가져야 한다. 정의 작성된 클래스는 하나의 기능만 가져야 한다. 클래스가 제공하는 모든 서비스는 하나의 책임을 수행하는 데 집중되어 있어야 한다. 어떤 변화에 의해 클래스를 변경해야 하는 이유는 오직 하나뿐이어야 한다. SRP 원리를 적용하면 무엇보다도 책임 영역이 확실해지기 때문에 한 책임의 변경에서 다른 책임의 변경으로의 연쇄 작용에서 자유로워질 수 있다. 적용방법 여러 원인들 속에 혼재된 각 책임을 개별 클래스로 분할하여 클래스 당 하나의 책임만을 맡도록 한다. 여기서 관건은 책임만 분리하는 것이 아니라 분리된 두 클래스간의 관계의 복잡도를 줄이도록 설계하는 것이다. 만약 각각의 클래스들이 유사하고 비슷한 책임을 중..

이 글은 비전공자 취준생이 개인적인 공부를 위해 작성한 글입니다. 자세한 내용을 원하실 경우 https://yurimac.tistory.com/30, https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/ 이곳을 방문해주시기 바랍니다. 이글의 출처는 위의 링크입니다. 그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 최적 해에 가까운 값을 구할 때 사용합니다. 매 순간마다 최적의 방법을 선택하여 값을 구하지만 결과적으로 최적 해라는 보장은 없습니다. 합이 가장 큰 값을 구해야하는 예제에서 다음 그림을 그..

이글은 비전공자 취준생이 개인적인 공부를 위해 작성한 글입니다. 자세한 내용은 https://babbab2.tistory.com/101 이곳에서 확인해주세요! 모든 이미지의 출처는 위의 티스토리임을 밝힙니다. 분할 정복 문제를 나눌 수 없을 때까지 나누어서 풀고, 나누어서 푼 문제를 다시 합병하여 답을 얻는 알고리즘 하양식 접근법으로 일반적으로 재귀함수로 구현합니다. 퀵 정렬 하나의 리스트를 pivot(기준점)을 기준으로 2개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 2개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게하는 방법입니다. 쉽게 생각하면 배열을 분할하고 정렬한 다음, 다시합치는 방법인 것 같습니다. 퀵정렬의 순서는 아래와 같습니다. 1. 기준점(pivot)을 ..

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/107 이곳을 확인해주세요! 깊이우선탐색(DFS) 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식 탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고, 다시 돌아가서 다른 인접노드의 자식들을 모두 탐색합니다. 탐색 노드의 가장 깊은 높드까지 다 탐색해야 다음 인접노드를 탐색할 수 있습니다. 구현 탐색할 그래프 미리 만들어두기 let graph: [String: [String]] = [ "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], "D" : ["B"], "E" : ["B"], "F" : ["C"], ] 깊이우선탐색을 하는 ..

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/106 이곳에서 확인해주세요! 너비우선탐색(BFS) Breadth-First Search 인접한 노드를 우선하여 탐색하는 방식입니다. 탐색 노드로부터 인접한 노드를 먼저 탐색하고, 다 탐색하면 인접한 노드의 인접한 노드들부터 탐색합니다. 따라서 같은 레벨에 있는 노드들부터 탐색하는 것처럼 보입니다. 참고로 왼쪽부터 탐색할지, 오른쪽부터 탐색할지 같은 순서는 중요하지 않습니다. 구현 1. 탐색할 그래프 미리 만들어두기 let graph: [String: [String]] = [ "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], "D"..

이 글은 개인적인 공부를 위해 작성하는 것임을 밝힙니다. 자세한 내용은 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..