[학교 수업]/[학교 수업] 자료구조 및 알고리즘

Divide and Conquer Divide and Conquer (분할 정복)은 문제를 분할하고, 중앙에서 정복하고 하단에서 조합하는 형태로 아래와 같이 도식화 할 수 있습니다. 분할: 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 하위 문제로 나눈다.정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.문제는 주로 2개 이상의 하위 문제로 나누어지는데 Merge sort (병합 정렬)처럼 문제를 무조건적으로 2개로 나누지는 않습니다. 분할 정복 알고리즘의 수행 시간은 주로 점화식을 푸는 것과 연결됩니다. Quick Sort Merge sort와 달리 리스트를 비균등하게 분할하여 정복하는 방법을 사용합니다. 평균적으로 매우 빠..

Problem DefinitionThere are N jobs, J_1, J_2, ..., J_nEach J_i = (D_i, P_i), D_i = Deadline, P_i = ProfitThere are 1-Hour Time slots where you can schedule jobsEach job takes 1 hour to finishExample = {(2,2), (1,3), (1,1)} AssumptionsAll deadlines are Jobs are given in non-increasing order of profit (if aren't given that order, you could sort jobs that order) Intuition/AlgorithmSchedule higher p..

1. Dijkstra Algoritm 2024.06.02 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue 자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue0. 들어가기 전 2024.05.18 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 7 - Heap 자바[JAVA] 자료구조 구현 7 - Heap0. 들어가기 전 Heap은 '우선순위 큐'에 사용되기 위해 필수적으로hw-hk.tistory.com에서 구체적인 다익스트라의 구현에 대해서 작성했습니다. 다시 다익스트라를 의사코드로 나타내면 다음과 같습니다:Di..

0. 2024.09.12 - [학교 수업/자료구조 및 알고리즘] - [자료구조 및 알고리즘] #18 - Greedy Algorithms [자료구조 및 알고리즘] #18 - Greedy Algorithms0. 2024.06.09 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application1. an Application Union-Findhw-hk.tistory.com앞서 살펴봤던 Prim Algorithm과 같이 MST를 구하는 또 다른 알고리즘,Kruskal Algorithm을 살펴보려고합니다.202..

0. 2024.06.09 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최hw-hk.tistory.com위 글에서 Greedy Algorithms인 Kruskal algorithms을 통해 MST를 구하는 문제를 본 적이 있습니다. 1..

1. Path Path는 한 정점에서 다른 정점가지 연속되는 간선들을 통해서 도달할 수 있는 방법입니다. 예를 들어 아래와 같은 그래프가 있을 때:1번 정점에서 3번 정점까지 도달할 수 있는 Path 는 다음과 같이 나타낼 수 있습니다:1-e1 → 2-e1 →  1-e3 →  3-e4 →  2-e6 →  2-e5 →  2-e4 →  3 이때 간선의 이름과 같이 정점의 이름도 같이 적어주는데, 그냥 간선 이름들만 적어줘도 Path 를 설명할 수 있지 않을까?그렇지 않습니다. 만약 e1 → e1 → e3 → e4 → e6 → e5 → e4 라고만 적어놨다면,처음 시작하는 노드는 어디였고, 어느 정점에서 어느 정점으로 향하는 간선인지 명확하지 않습니다. 다시한번 Path 에 대해 정의하자면 다음과 같습니다: ..

3. Graph Patterns 3.1 Complete Graph - Kn 서로 다른 노드들의 모든 노드쌍에 대해서 간선을 공유하는 단순 그래프를 Complete Graph - Kn 이라고 합니다. 이때 n 은 정점의 개수입니다.(* A simple graph is complete if every pair of distinct vertices share an edge. The notation Kn denotes the complete graph on n vertices) 3.2 Cycles - Cn ... (* The cycle graph Cn is a circular graph with V = {0,1,2,...,n-1} where vertex i is connected to i+1 mod n and ..