병합 정렬(merge sort)는 배열을 절반씩 쪼개서 재귀적인 방법으로 Sorting하는 알고리즘이다. void merge(vi& arr, int low, int mid, int high) { vi ans; int i = low; int j = mid + 1; while (i

한 Task를 처리하는데 각각 처리 시간이 다른 기계들이 있다. 완료되어야 하는 작업의 수는 compNum개이고, 각 기계들은 상이한 작업 처리 시간을 가지고 있다. compNum개의 작업이 모두 완료되기 위한 최소 시간은 얼마인가? 이진 탐색(binary search)를 통해서 구해보자. int minTaskTime(int taskNum, vi prcTime) { //taskNum: 해결해야하는 작업의 개수 //prcTime: 작업하는 기계들의 처리시간을 갖는 벡터 int low = 0; int high = 10000; int mid = 0; while (1) { int compNum = 0; mid = (low + high) / 2; for (int i = 0; i < prcTime.size(); i..

배열에서 연속된 부분의 합 중 최대값을 구하는 문제이다. -1, 2, 4, -3, 5, 2, -5, 2 이 중에서 최대 값은 -1, 2, 4, -3, 5, 2, -5, 2 연속된 수의 합이 10으로 가장 크다. 아래의 코드는 O(n^2)의 시간 복잡도로 최적해를 찾는 코드이다. #include using namespace std; int find_max_sum(int arr[], int n) { int best = 0; for (int a = 0; a < n; a++) { int sum = 0; for (int b = a; b < n; b++) { sum += arr[b]; best = max(sum, best); } } return best; } int main() { int arr1[8] = { -1..

서로를 공격할 수 없도록 퀸을 배치하는 경우의 수를 구하는 문제이다. 백트랙킹 기법을 이용하여 불가능한 경우가 나오면 깊이 탐색을 포기하고 다른 가지를 탐색한다. int n = 4; int cnt = 0; bool col[7] = { false }; bool diag1[7] = { false }; bool diag2[7] = { false }; n은 체스판의 크기, cnt는 경우의 수, col은 체스판의 열, diag1, diag2는 각각 왼쪽, 오른쪽 대각선을 의미한다. 퀸은 같은 행과, 열을 모두 이동할 수 있으므로 체스판의 행과 열에는 하나의 퀸만 올 수 있다. void search(int y) { if (y == n) { cnt++; return; } for (int x = 0; x < n; x+..

재귀함수를 이용하여 순열을 구하는 알고리즘이다. #include #include using namespace std; vector permutation; void search(int n, bool chosen[]) { vector::iterator it; if (permutation.size() == n) { for (it = permutation.begin(); it != permutation.end(); it++) { cout

재귀함수를 이용하여 부분집합을 구하는 방법이다. #include #include using namespace std; vector subset; void search(int k, int n) { vector::iterator it; if (k == n + 1) { for (it = subset.begin(); it != subset.end(); it++) { cout