본문 바로가기

알고리즘

[알고리즘] 회의실 배정 문제의 여러가지 풀이법 (Brute-Force, 분할정복, DP, 그리디) 회의실 배정 문제 회의실 배정 문제를 여러 가지 알고리즘으로 해석해보고자 한다. 문제의 상황은 아래와 같다. 실생활에서 자주 마주할만한 상황이라 재미있다. 회의실은 1개인데, n개의 회의가 있다. 이때 하나의 회의실에서 최대한 많이 회의를 할 수 있도록 스케줄을 잘 짜 보는 것이다. (문제에서 S는 회의 시작시간, F는 회의 종료시간으로 주어진다.) 예를 들면 아래와 같은 상황이 있을 수 있다. 시간표를 어떻게 짜야 가장 많은 회의를 배정할 수 있겠는가? 한번 생각해보자. 백준 1931번에 비슷한 문제가 있으니 참고해도 좋다. https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acm.. 더보기
[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)와 Kruskal, Prim 알고리즘 Spanning Tree (신장 트리) 란? Spanning Tree (신장 트리)란 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리이다. 무방향 그래프란 방향성이 없는 그래프로 그림상에서 화살표가 아닌 실선으로 이루어진 그래프를 뜻한다. 즉, Spanning Tree는 최소의 간선을 이용하여 모든 정점을 연결한 그래프이다. 너비 우선 탐색을 이용하여 생성된 신장 트리를 BFS (Breath First Spanning tree, 너비 우선 신장 트리)라고 하고, 깊이 우선 탐색을 이용해 생성된 신장 트리를 DFS (Depth First Spanning tree, 깊이 우선 신장 트리)라고 한다. Spanning tree는 최소의 도로를 이용한 도로망 건설이나 최소의 네트워크선을 이.. 더보기
[알고리즘] Stable sorting algorithm, In-Place algorithm Stable Sorting Algorithm (안정 정렬 알고리) - 크기가 같은 데이터가 정렬된 이후에도 입력된 순서를 그대로 유지하게 하는 정렬 알고리즘이다. Stable Sorting Algorithm Bubble Sort Insertion Sort Cocktail Shaker Merge Sort Unstable Sorting Algorithm Selection sort Heap Sort Shell Sort Quick Sort Exchange Comb In-place Algorithm - 입력 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요한 알고리즘이다. - 정렬을 하는 과정에서 추가적인 메모리 공간이 "거의" 안든다고 생각하면 쉽다. - Quick Sort의 경우는 정의에 따라서 No.. 더보기
정렬 알고리즘 총정리 1. Bubble Sort (버블 정렬) 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도는 O(n^{2})로 매우 느리다. (효율성은 나쁘지만 코드가 단순하기 때문에 교육용으로(?) 자주 사용되는 것 같다.) Stable 하고 In-place 하다. (https://blog.wookingwoo.com/27 참고) 이미지 출처: https://www.cs.mtsu.edu/~xyang/2170/bubbleSort.html Bubble Sort Complexity Average (평균 시간복잡도) O(n^2) Best Case (최선 시간복잡도) O(n) Worst Case (최악 시간복잡도) O(n^2) Space Complexity (공간복잡도) O(1) C++ 코드 예시 void swap(in.. 더보기

티스토리툴바