반응형
앞으로 예제와 함께 알고리즘 수업에서 배운 내용들을 요약하여 올릴 것이다.
총 올릴 알고리즘 분류는 아래 8가지이다.
1. Brute force
2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound
여기서는 Brute Force에 대해 다룬다.
Brute Force란
될 때까지 다 해본다는 알고리즘이다. 문제 해결을 위해 모든 경우의 수를 찾을 때까지 반복하는 방법이다. 실패하는 경우는 없으나 컴퓨팅 자원이 다른 알고리즘에 비해서 심각하게 낭비된다. 가장 단순하고 직관적이다.
Brute Force 예시
- Selection Sort
- Bubble Sort
- Sequential Search
- String Matching
- Exhausitve Search(완전탐색) :
- Traveling salesman Problem(Hamilton Circuits)
- Knapsack Problem
- Job Assignment Problem
정렬 알고리즘과 탐색 알고리즘 중 일부가 brute force에 해당한다. 또한 모든 경우의 수를 계산하는 완전탐색 알고리즘 들도 이에 해당한다.
Selection Sort
- 정렬 방법 중 하나인 선택정렬이다. 구현한 코드는 다음과 같다.
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <time.h>
int main(){
int arr[1001];
for(int i=0; i<1000; i++){
arr[i] = rand()%10000+1;
}
clock_t start_time = clock();
for(int i=0; i<1000; i++){
int min = i;
for(int j=i+1; j<1000; j++){
if(arr[j]<arr[min]){
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
clock_t end_time = clock();
for(int i=0; i<1000; i++){
printf("%d ",arr[i]);
}
double time_taken = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("\ntime: %f sec\n", time_taken);
return 0;
}
- 위의 코드에서는 작동시간까지 적어두었다. 확실히 C랑 파이썬 시간 차이가 많이 난다.
- 쉽게 말하면 카드 정렬하는 것과 비슷하다. 전체를 쓱 훑어서 가장 작은 걸 찾는다. 그래서 가장 작은걸 맨 앞으로 보내고, 맨앞으로 보내고 남은 다른 것 모두를 훑어 또 거기서 가장 작은 걸 찾아내어 2번째에 놓는다.
- 위의 과정을 모든 카드가 n-1번 반복한다.
- 그래서 반복문을 2번씩 돌리므로 시간복잡도는 O(n2)이다.
Bubble Sort
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
int main() {
int arr[1001];
// 난수 생성
srand(time(0));
for (int i = 0; i < 1000; i++) {
arr[i] = rand() % 10000 + 1;
}
// 정렬 시작 시간 기록
clock_t start_time = clock();
// Bubble sort
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000 - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
clock_t end_time = clock();
for (int i = 0; i < 1000; i++) {
std::cout << arr[i] << " ";
}
double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
std::cout << "\ntime: " << time_taken << " sec" << std::endl;
return 0;
}
- 인접한 두 원소끼리 비교하고, 크기가 순서대로 되어있지 않으면 위치를 교환한다.
- 위의 과정을 반복하면 한 번 끝날 때마다 가장 큰 게 뒤로 가게 된다, 즉 선택정렬과는 반대로 뒤부터 정렬이 된다.
- 선택정렬과 마찬가지로 O(N2)의 복잡도를 가진다.
Sequential Search
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
int main() {
int arr[]={288768, 169985, 133120, 483338, 491530, 307210, 393229, 26638, 10253, 110608, 368662, 419862, 458775, 30, 266271, 249887, 389151, 264226, 219169, 180262, 284713, 18478, 174127, 223279, 108592, 327732, 270389, 198710, 194612, 69689, 356410, 321597, 81983, 313408, 469056, 413761, 387139, 325701, 458822, 319559, 172103, 421961, 149578, 497738, 383051, 178253, 221263, 430162, 63573, 41050, 63579, 424026, 395360, 376930, 344165, 252008, 223340, 118893, 116845, 346220, 45170, 14454, 356471, 379000, 479354, 356475, 36988, 110717, 53374, 442494, 452736, 362626, 370820, 65669, 75910, 465033, 444554, 231568, 110737, 313494, 86168, 100508, 137374, 407710, 407711, 356514, 385189, 299173, 252408, 229546, 356525, 463022, 465074, 284851, 139445, 364727, 174264, 153787, 12475, 252091, 221372, 80064, 127171, 454853, 397510, 258257, 469208, 45272, 495833, 35041, 258274, 418019, 59620, 82150, 51431, 301294, 393455, 258289, 315634, 282865, 190708, 348407, 450808, 264442, 45306, 248058, 491773, 407804, 426241, 26883, 14596, 383236, 395526, 20748, 321810, 223509, 12565, 403734, 80152, 307482, 440602, 241953, 446753, 227623, 403752, 231719, 151851, 323884, 319789, 278828, 221487, 305456, 196912, 24886, 350519, 192824, 325946, 223548, 397630, 92480, 405824, 149824, 82245, 186697, 483658, 18763, 174412, 495947, 270669, 104783, 186704, 149841, 188753, 270676, 55637, 57686, 239959, 305494, 229722, 61790, 414047, 201058, 131427, 213348, 47458, 98660, 477540, 217449, 299370, 2413, 282990, 22895, 493936, 221549, 436595, 192883, 483704, 27001, 250235, 29053, 61821, 145791, 139649, 409988, 342405, 418182, 92550, 346501, 207241, 100746, 485771, 461195, 143758, 391567, 326035, 160155, 82336, 96678, 496045, 434608, 201140, 471477, 33209, 27067, 29117, 266685, 303553, 254402, 231875, 12741, 303558, 405959, 424391, 16841, 215502, 29135, 20945, 461266, 45523, 307667, 137685, 190933, 352729, 328154, 231905, 475617, 301538, 436718, 168430, 111088, 387569, 487924, 428533, 322038, 84470, 260598, 119289, 340471, 342523, 217595, 107005, 381438, 416246, 139770, 186881, 207369, 498187, 156176, 227861, 119318, 250391, 193047, 94746, 348700, 193057, 174626, 365093, 90662, 420395, 74285, 125489, 475698, 483894, 346680, 248376, 369209, 277051, 367161, 293432, 401988, 440902, 299590, 408136, 88646, 289356, 211535, 100945, 307795, 297556, 475731, 129620, 266835, 31322, 41563, 420443, 483937, 45666, 96866, 279138, 53857, 402022, 293473, 92770, 82533, 485998, 66161, 455284, 174714, 256635, 238204, 182909, 303743, 307846, 162438, 400011, 8843, 250514, 309908, 43671, 49817, 410266, 170651, 127644, 55965, 385699, 152232, 469674, 297643, 453292, 117418, 451242, 74417, 383669, 176825, 53947, 451260, 252604, 438972, 205503, 109252, 344773, 371406, 332494, 328401, 53972, 21204, 322262, 248534, 25302, 58073, 408282, 455388, 152288, 101096, 19178, 412395, 90860, 318194, 148212, 357109, 447222, 379639, 105208, 252662, 338684, 408317, 156414, 232198, 453383, 408328, 498443, 23310, 66319, 107280, 492308, 381717, 340758, 330520, 135961, 394010, 113435, 252699, 236313, 486170, 432922, 258851, 148259, 359205, 322346, 267053, 486189, 178996, 232244, 138037, 404282, 379707, 287553, 383815, 207689, 496458, 19274, 246606, 308048, 291667, 293715, 115544, 400217, 201560, 52059, 195422, 95072, 236386, 469860, 457573, 426854, 349030, 418664, 459626, 271216, 424819, 445301, 271223, 416632, 11130, 58238, 359295, 441217, 86914, 144259, 269189, 328583, 160653, 197517, 27533, 74641, 347029, 318358, 168855, 19352, 13215, 119714, 414629, 322471, 64424, 318375, 43946, 43948, 353198, 304048, 271281, 314292, 244662, 482231, 256952, 426939, 3005, 484285, 447424, 54210, 486342, 238535, 132040, 80843, 93134, 318415, 353231, 467924, 107477, 156630, 291800, 336858, 351195, 21468, 250846, 306143, 201696, 386016, 111586, 148453, 222182, 209894, 115686, 197609, 363497, 218091, 216041, 177134, 429039, 207860, 312310, 472056, 285691, 224251, 248832, 277505, 17409, 136195, 64516, 252933, 279557, 37895, 238601, 347147, 398348, 447501, 463892, 105492, 465942, 89110, 300058, 496668, 312355, 222245, 388136, 187433, 363563, 189484, 418860, 298031, 257073, 109621, 76855, 171066, 201788, 50237, 164926, 287808, 336961, 459845, 201799, 396360, 37959, 490572, 332877, 27727, 42065, 445527, 148569, 68702, 314462, 390239, 435300, 470116, 392300, 50285, 169070, 455788, 214128, 54385, 148594, 439411, 406642, 463989, 62581, 287856, 310392, 406650, 416892, 126078, 343167, 337025, 488578, 423045, 35977, 406666, 224395, 255117, 478350, 349327, 418961, 169105, 31892, 5269, 302231, 148636, 64668, 187551, 255138, 322726, 421034, 289963, 453806, 320687, 122031, 76977, 484530, 494771, 193715, 79032, 355513, 335037, 453821, 144575, 421054, 236739, 66757, 117961, 238798, 154831, 9423, 177365, 214229, 13527, 70872, 435417, 324825, 103642, 117981, 191709, 296163, 7400, 148715, 496877, 81135, 290033, 70898, 355570, 140533, 335094, 326903, 255224, 468215, 204021, 447739, 105724, 216310, 437504, 15618, 9480, 347401, 87306, 265485, 15630, 294159, 355600, 312592, 134418, 339218, 345362, 167189, 23830, 199960, 359705, 193818, 451867, 441628, 468249, 138521, 171291, 341281, 118051, 251172, 25893, 374054, 36135, 163108, 21801, 46377, 58671, 271664, 15665, 218415, 64818, 468274, 70965, 142646, 228662, 154934, 310584, 19769, 372022, 435516, 349501, 83260, 120127, 173370, 499009, 142662, 496967, 261446, 7500, 468307, 30044, 304482, 40290, 91492, 30053, 181607, 294247, 50535, 300392, 7531, 93548, 335214, 367983, 255345, 361841, 85362, 79217, 413045, 79218, 449908, 480634, 494972, 394622, 28030, 466302, 218495, 130433, 294275, 339332, 269700, 1411, 368007, 322953, 458122, 157067, 216462, 345488, 105872, 56726, 277911, 48536, 386463, 282016, 181671, 32168, 243113, 409007, 91567, 220596, 140726, 322999, 36280, 40376, 495033, 259517, 443842, 42435, 19906, 58821, 406982, 167365, 263626, 359885, 370127, 83409, 374228, 40405, 13781, 171480, 175578, 437724, 124382, 275935, 417246, 15842, 165347, 308715, 24043, 331245, 22000, 181745, 415218, 310771, 146930, 65012, 134641, 341495, 253427, 71161, 130555, 278015, 200194, 105987, 97797, 413190, 15879, 97803, 407054, 413199, 130576, 134670, 386582, 484887, 40473, 423455, 437793, 153124, 265767, 439850, 251436, 136753, 431666, 300594, 495156, 337461, 106036, 423479, 58936, 138810, 384573, 386624, 7747, 480836, 398919, 431690, 460364, 325197, 425550, 388685, 165458, 153177, 138842, 61019, 130652, 388702, 319072, 3682, 224867, 398949, 58990, 218736, 46704, 419442, 499321, 493181, 278142, 448129, 93833, 405130, 415373, 355984, 292497, 460432, 378516, 233109, 358039, 89753, 315035, 161436, 181917, 269986, 403107, 59044, 269989, 126632, 374444, 138931, 249527, 464567, 159417, 388792, 95931, 91835, 356027, 493242, 153276, 48834, 126658, 333508, 458437, 376516, 216775, 173774, 370383, 116433, 429777, 227027, 52948, 216789, 390873, 315104, 319204, 36583, 63208, 259817, 34539, 136941, 437998, 22256, 204528, 55028, 263924, 370428, 134910, 124672, 366341, 280327, 325388, 34580, 401173, 237333, 202519, 196379, 376607, 36640, 386848, 79648, 208673, 487204, 485159, 132904, 294698, 50991, 386866, 470837, 51007, 423746, 89923, 83781, 89925, 374600, 196430, 53075, 380755, 151387, 91996, 339805, 57181, 149344, 337770, 307050, 489326, 249712, 264049, 200564, 167798, 362360, 69497, 188282, 434046, 57214, 300928, 262017, 10115, 458627, 343941, 483208, 401288, 161680, 173970, 65427, 302995, 264085, 165784, 241560, 483226, 311194, 352158, 79775, 391076, 159653, 380839, 94120, 309161, 440238, 436144, 475059, 321460, 130999, 417722, 341950, 292802, 108485, 151494, 327623, 18376, 88009, 452557, 477134, 110545, 208854, 366553, 165850, 327643, 436190, 194527, 311264, 268258, 118755, 456674, 227304, 339949, 165870, 393197, 337908, 403448, 47098, 317436};
// 정렬 시작 시간 기록
clock_t start_time = clock();
//순차 탐색으로 237333, 357001, 317436 찾기
int n = sizeof(arr) / sizeof(arr[0]);
int key = 237333;
int key2 = 357001;
int key3 = 317436;
int index = -1;
int index2 = -1;
int index3 = -1;
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
index = i;
}
if (arr[i] == key2) {
index2 = i;
}
if (arr[i] == key3) {
index3 = i;
}
}
if(index == -1) {
printf("key: %d, not found\n", key);
}else{
printf("key: %d, index: %d\n", key, index);
}
if(index2 == -1) {
printf("key: %d, not found\n", key2);
}else{
printf("key: %d, index: %d\n", key2, index2);
}
if(index3 == -1) {
printf("key: %d, not found\n", key3);
}else{
printf("key: %d, index: %d\n", key3, index3);
}
clock_t end_time = clock();
double time_taken = double(end_time - start_time) / CLOCKS_PER_SEC- 이번엔 탐색 알고리즘에서 순차탐색이다.
- 사실 순차탐색이라고는 하지만 그냥 앞에서부터 쭉 비교하는 방식이다. 알고리즘이라고 하기에 민망하다.
- 처음부터 쭉 한 방향으로 탐색을 수행하기에 선형탐색이라고 불리고, 정렬되지 않은 데이터에서 쓰인다.
- 시간복잡도는 O(n)이다.
String Matching
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cstdio>
int main() {
clock_t start_time = clock();
FILE *fp = fopen("TheLittlePrince.txt", "r");
char str[1000000];
size_t read_size = fread(str, 1, sizeof(str) - 1, fp);
str[read_size] = '\0';
int count = 0;
const char *target = "어린 왕자";
size_t target_len = strlen(target);
for (size_t i = 0; i <= read_size - target_len; i++) {
if (strncmp(&str[i], target, target_len) == 0) {
std::cout << "'어린 왕자'가 나타난 위치: " << i << std::endl;
count++;
}
}
fclose(fp);
clock_t end_time = clock();
double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
std::cout << "\n총 '어린 왕자'가 쓰인 횟수: " << count << std::endl;
std::cout << "소요된 시간: " << time_taken << " 초" << std::endl;
return 0;
}- brute force를 이용해 글자를 찾는 방식이다.
- 가장 맨 앞글자를 기준으로 탐색하며, 일치하면 다음글자끼리 비교하여 있는지 확인하는 방식이다.
- 유사한 글자가 많은 경우에 시간이 오래 걸릴 수 있다. 앞부분글자만 겹친다면 그만큼 시간을 많이 잡아먹기 때문이다.
- 그래서 일반적으로 kmp나 라빈카프 등의 나중에 배울 알고리즘이 널리 쓰인다.
- 시간 복잡도는 찾는 pattern의 길이 m, 전체 text의 길이 n이라고 했을 때 O(m·n)이다.
Traveling Salesman Problem
#include <iostream>
#include <algorithm>
#include <ctime>
int main() {
int matrix[5][5] = {
{0, 2, 3, 2, 3},
{2, 0, 3, 4, 1},
{3, 3, 0, 2, 4},
{2, 4, 2, 0, 5},
{3, 1, 4, 5, 0}
};
clock_t start_time = clock();
int arr[5] = {1, 2, 3, 4, 5};
char ch[7];
int min = 1000000;
for (int i = 1; i < 5; i++) {
for (int j = 1; j < 5; j++) {
if (j == i) continue;
for (int k = 1; k < 5; k++) {
if (k == i || k == j) continue;
for (int l = 1; l < 5; l++) {
if (l == i || l == j || l == k) continue;
printf("1 %d %d %d %d ", i + 1, j + 1, k + 1, l + 1);
int sum = matrix[0][i] + matrix[i][j] + matrix[j][k] + matrix[k][l] + matrix[l][0];
printf("sum: %d\n", sum);
if (sum < min) {
min = sum;
ch[0] = '1';
ch[1] = char(arr[i] + '0');
ch[2] = char(arr[j] + '0');
ch[3] = char(arr[k] + '0');
ch[4] = char(arr[l] + '0');
ch[5] = '1';
ch[6] = '\0';
}
}
}
}
}
printf("minimum: %d\n", min);
printf("path: %s\n", ch);
clock_t end_time = clock();
double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
printf("Time taken: %.6fs\n", time_taken);
return 0;
}- 소위 외판원 문제라고 불리는 문제다. 모든 vertex를 돌아 최초의 vertex로 돌아와야 할 때, 가장 빠른 경로를 구하는 문제이다.
- 각 vertex 간 사이의 가중치가 주어지고, 여기서 가장 빠른 경로를 찾는 것이다. 이렇게 그래프에서 모든 정점을 오직 한 번씩만 지나는 순회를 해밀턴 순회라고 부른다. 모든 점을 한번씩만 지나서 출발지로 되돌아올 수 없는 경우 해밀턴 순환을 만족하지 못한다고 한다.
- 해밀턴 순회 시작한 곳으로 되돌아 올 필요가 없는 경우는 해밀턴 경로라고 한다.
- vertex가 하나 늘어날 때마다 처리량이 제곱해서 증가하므로 brute force로 풀기에는 매우 비효율적이다.
Knapsack Problem
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
using namespace std;
int main() {
int itemCounts, limitedWeight;
int solution = 0;
printf("Enter item count\n");
scanf("%d", &itemCounts);
printf("Enter weight limit\n");
scanf("%d", &limitedWeight);
vector<pair<int, int>> item;
for (int i = 0; i < itemCounts; i++) {
int weight, value;
printf("Enter weight and value\n");
scanf("%d %d", &weight, &value);
item.push_back({weight, value});
}
clock_t start_time = clock();
int used = 1 << itemCounts;
for (int i = 0; i < used; i++) {
int tempWeight = 0;
int tempValue = 0;
for (int j = 0; j < itemCounts; j++) {
// i가 j번째 아이템을 선택했는지 확인 (비트 연산)
if (i & (1 << j)) {
tempWeight += item[j].first;
tempValue += item[j].second;
}
}
// 무게 제한 내에서 최대 가치를 찾기
if (tempWeight <= limitedWeight) {
solution = max(solution, tempValue);
}
}
printf("Solution: %d\n", solution);
clock_t end_time = clock();
double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
printf("Time taken: %.6fs\n", time_taken);
return 0;
}- 가방 안에 짐들을 넣는데, 각 짐들의 무게와 가치가 주어진다.
- 이때 가방이 감당할 수 있는 무게로 담되, 최대의 가치를 추구해야 하는 문제이다.
- 이 역시 모든 경우를 다 해보는 비효율적인 O(2^n)의 시간복잡도를 가져 DP로 해결하는 것이 낫다.
- 만약 물건을 쪼갤 수 있다면(fractional) 무게대비 가치가 가장 높은 걸 고르는 greedy algorithm을 사용한다.
Job Assignment Problem
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int main() {
int cost[10][10] = {
{13, 6, 7, 12, 14, 15, 10, 11, 15, 4},
{ 8, 14, 11, 9, 6, 14, 7, 9, 16, 12},
{10, 8, 10, 10, 8, 15, 11, 5, 7, 9},
{13, 13, 16, 9, 13, 16, 15, 9, 14, 16},
{11, 4, 9, 14, 12, 11, 5, 16, 8, 14},
{ 7, 10, 12, 13, 4, 11, 16, 12, 15, 9},
{ 6, 11, 10, 11, 13, 15, 7, 16, 11, 12},
{ 7, 15, 5, 10, 4, 16, 12, 4, 10, 16},
{ 5, 14, 10, 15, 8, 8, 8, 14, 14, 4},
{ 8, 11, 4, 16, 8, 12, 4, 14, 9, 6}
};
vector<int> perm = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int min_cost = 999999999;
vector<int> solution;
clock_t start_time = clock();
do {
int temp = 0;
for (int i = 0; i < 10; ++i) {
temp += cost[i][perm[i]];
}
if (temp < min_cost) {
min_cost = temp;
solution = perm;
}
} while (next_permutation(perm.begin(), perm.end()));
clock_t end_time = clock();
cout << "Minimum Cost: " << min_cost << endl;
cout << "Solution: ";
for (int i = 0; i < 10; ++i) {
std::cout << solution[i] << " ";
}
cout << endl;
double time_taken = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
cout << "Time taken: " << time_taken << " seconds" << endl;
return 0;
}- 각 직업당 사람하나를 할당해 임금 합의 최솟값을 뽑아내는 과정을 담는다.
- 2차원 배열을 보통 입력받고 모든 경우를 다 팩토리얼로 계산한다.
- 그래서 시간복잡도는 O(n!)가 되어서 branch and bound로 처리하는 것이 더 낫다.
결론
지금까지 Brute Force에 대한 예시들이었다.
반응형
'algorithm' 카테고리의 다른 글
| [알고리즘] 3. Decrease and Conquer 내용 정리 (0) | 2024.11.11 |
|---|---|
| [알고리즘] 2. Divide and conquer 내용 정리 (0) | 2024.11.11 |
