1. 선형 검색
검색 문제에 대해 생각해보겠습니다.
우선 가장 간단한 검색 방법은 선형 검색(linear search)일 겁니다.
선형 검색이란 전체 원소를 방문하면서 해당 원소가 있는지를 찾는겁니다. 비유하자면 박철수라는 친구의 출석번호를 알고싶은데, 출석번호순으로 차례대로 읽어나가는 것입니다. 1번 강철수, 2번 김철수...3번...4번...5번.. 이런식으로요. 코드를 보면서 이해해봅시다.
#include <iostream>
#include <vector>
using namespace std;
bool linear_search(int N, vector <int> vec) {
for (int i : vec) {
if (i == N) return true;
}
return false;
}
int main(void) {
vector <int> vec = { 1,2,3,4,5 };
if (linear_search(3, vec))
cout << "found";
else cout << "not found";
}
linear_search라는 함수를 우선 구현했습니다. 단순히 벡터 내부를 순차적으로 돌아다니면서 찾고 찾았으면 종료하고 그렇지 않으면 더 돕니다. 여기서는 3이 있으니까 1번, 2번 이렇게 돌아다니고 3번을 찾고 끝났을 것이며 3이 존재하니까 found가 출력되겠네요. 시간복잡도는 O(N)이 됩니다.
2. 이진 검색
사실 우리는 또 다른 검색 방법을 쓸 수 있습니다. 이진 검색(binary search)입니다. 순차적으로 출석번호부를 읽어나갈 수도 있겠지만, 출석번호가 ㄱㄴㄷㄹㅁㅂㅅ...순임을 이용하면 좀 더 효율적으로 검색할 수 있을지 모릅니다.
만약에 100명이 있다고 가정해봐요. 그리고 여기서 박철수를 찾아봅시다. 일단 출석번호부를 반으로 갈라버립시다. 그리고 50번이랑 박철수의 이름을 비교합시다. 만약에 50번이 박철수보다 순번이 뒤에요. 뭐 신철수 이런 거라고 칩시다. 그러면 우리가 반으로 가른 출석번호부 중 뒷쪽 절반은 필요없겠어요. 박철수가 거기 없을 거라는 걸 미리 알아버렸네요. 그러면 또 절반을 갈라봅시다. 그런데 이번엔 25번이 류철수에요. 박철수는 그러면 출석번호가 25번보다 큰 게 확정이니 그러면 이번엔 앞쪽을 버리면 되겠네요. 이런식으로 범위를 좁혀나가면서 찾을 수 있겠습니다.
또 코드를 보죠!
#include <iostream>
#include <vector>
using namespace std;
bool binary_search(int N, const vector<int>& vec) {
auto first = vec.begin();
auto last = vec.end();
while (first < last) {
auto range_length = distance(first, last);
auto mid_distance = range_length / 2;
auto mid_element_iter = first + mid_distance;
auto mid_element = *mid_element_iter;
if (mid_element == N) return true;
else if (mid_element > N) last = mid_element_iter;
else if (mid_element < N) first = mid_element_iter + 1;
}
return false;
}
int main(void) {
vector <int> vec = { 1,2,3,4,5 };
if (binary_search(3, vec)) cout << "found";
else cout << "not found";
}
코드가 아까보다 약간 깁니다. 그래도 한 번 보죠. first는 벡터의 머리 last는 벡터의 꼬리입니다. 그리고 원소 개수를 표현하기 위해 distance(first, last) 이렇게 설정하였어요. 철수의 출석번호 이야기를 할 때 강조한 부분이 계속 있죠? 중간 세팅입니다. 그냥 반으로 갈라버린 부분이 N이랑 일치하면 true 반환하고 종료하면 끝이죠. 반갈죽 한 부분이 N보다 크다면 뒷부분은 찾아볼 필요 없겠어요. 앞부분으로 범위 좁혀주면서 찾아주면 됩니다. 반대 방향도 같아요.
시간복잡도는 O(logN)입니다.
사실 실행 결과는 당연히 같습니다. 그럼 이놈들 시간을 어떻게 비교하죠? 비교하는 프로그램을 작성해봅시다. 조금 길지만 할 수 있어요.
3. 실행시간 비교
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;
bool linear_search(int N, vector <int> vec) {
for (int i : vec) {
if (i == N) return true;
}
return false;
}
bool binary_search(int N, const vector<int>& vec) {
auto first = vec.begin();
auto last = vec.end();
while (first < last) {
auto range_length = distance(first, last);
auto mid_distance = range_length / 2;
auto mid_element_iter = first + mid_distance;
auto mid_element = *mid_element_iter;
if (mid_element == N) return true;
else if (mid_element > N) last = mid_element_iter;
else if (mid_element < N) first = mid_element_iter + 1;
}
return false;
}
void run_small_search_test() {
int N = 2;
vector<int> S = { 1, 3, 2, 4, 5, 7, 9, 8, 6 };
sort(S.begin(), S.end());
// 선형 탐색 시간 측정 시작
auto start = chrono::steady_clock::now();
if (linear_search(N, S)) cout << "found by linear searching" << '\n';
else cout << "not found by linear searching" << '\n';
auto end = chrono::steady_clock::now();
// 선형 탐색 시간 측정 끝
auto diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "linear search execution time: " << diff << " microseconds" << '\n';
// 이진 탐색 시간 측정 시작
start = chrono::steady_clock::now();
if (binary_search(N, S)) cout << "found by binary searching" << '\n';
else cout << "not found by binary searching" << '\n'; // 출력 오타 수정
end = chrono::steady_clock::now();
// 이진 탐색 시간 측정 끝
diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "binary search execution time: " << diff << " microseconds" << '\n';
}
void run_large_search_test(int size, int N) {
vector<int> S;
random_device rd;
mt19937 rand(rd());
uniform_int_distribution<mt19937::result_type> uniform_dist(1, size);
for (int i = 0; i < size; i++) S.push_back(uniform_dist(rand));
sort(S.begin(), S.end());
// 선형 탐색 시간 측정 시작
auto start = chrono::steady_clock::now();
bool linear_search_result = linear_search(N, S);
auto end = chrono::steady_clock::now();
// 선형 탐색 시간 측정 끝
auto linear_diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "linear search execution time: " << linear_diff << " microseconds" << '\n';
// 이진 탐색 시간 측정 시작
start = chrono::steady_clock::now();
bool binary_search_result = binary_search(N, S);
end = chrono::steady_clock::now();
// 이진 탐색 시간 측정 끝
auto binary_diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "binary search execution time: " << binary_diff << " microseconds" << '\n';
if (linear_search_result) cout << "element found in linear search" << '\n';
else cout << "element not found in linear search" << '\n';
if (binary_search_result) cout << "element found in binary search" << '\n';
else cout << "element not found in binary search" << '\n';
}
int main(void) {
run_small_search_test();
run_large_search_test(10000, 36543);
run_large_search_test(100000, 36543);
run_large_search_test(1000000, 36543);
}
좀 깁니다...그러나 시간 측정하는 부분만 보시면 되겠어요. 실행하면 결과는
//small
found by linear searching
linear search execution time: 135 microseconds
found by binary searching
binary search execution time: 52 microseconds
//large
linear search execution time: 41 microseconds
binary search execution time: 7 microseconds
element not found in linear search
element not found in binary search
linear search execution time: 105 microseconds
binary search execution time: 13 microseconds
element found in linear search
element found in binary search
linear search execution time: 4561 microseconds
binary search execution time: 59 microseconds
element not found in linear search
element not found in binary search가독성이 무척 구리다
대체로 이진 검색이 빠르죠. 그렇다면 이진 검색이 언제나 좋을까요? 꼭 그렇지는 않습니다. 일단 이진검색은 구현이 복잡하고, 정렬이 되어있어야 합니다. 만약에 출석번호부가 랜덤이고 이를 정렬하는 과정을 거치지 않는다면 이진검색을 쓸 수 없습니다. 김철수랑 박철수랑 비교했는데 누가 앞에 있는지 알 수 없다면 저런 방법을 쓸 수가 없습니다. 그러나 선형 검색을 한다면 그냥 박철수가 나올 때까지 읽어버리면 되니 상관이 없죠.
1. 선형 검색
검색 문제에 대해 생각해보겠습니다.
우선 가장 간단한 검색 방법은 선형 검색(linear search)일 겁니다.
선형 검색이란 전체 원소를 방문하면서 해당 원소가 있는지를 찾는겁니다. 비유하자면 박철수라는 친구의 출석번호를 알고싶은데, 출석번호순으로 차례대로 읽어나가는 것입니다. 1번 강철수, 2번 김철수...3번...4번...5번.. 이런식으로요. 코드를 보면서 이해해봅시다.
#include <iostream>
#include <vector>
using namespace std;
bool linear_search(int N, vector <int> vec) {
for (int i : vec) {
if (i == N) return true;
}
return false;
}
int main(void) {
vector <int> vec = { 1,2,3,4,5 };
if (linear_search(3, vec))
cout << "found";
else cout << "not found";
}
linear_search라는 함수를 우선 구현했습니다. 단순히 벡터 내부를 순차적으로 돌아다니면서 찾고 찾았으면 종료하고 그렇지 않으면 더 돕니다. 여기서는 3이 있으니까 1번, 2번 이렇게 돌아다니고 3번을 찾고 끝났을 것이며 3이 존재하니까 found가 출력되겠네요. 시간복잡도는 O(N)이 됩니다.
2. 이진 검색
사실 우리는 또 다른 검색 방법을 쓸 수 있습니다. 이진 검색(binary search)입니다. 순차적으로 출석번호부를 읽어나갈 수도 있겠지만, 출석번호가 ㄱㄴㄷㄹㅁㅂㅅ...순임을 이용하면 좀 더 효율적으로 검색할 수 있을지 모릅니다.
만약에 100명이 있다고 가정해봐요. 그리고 여기서 박철수를 찾아봅시다. 일단 출석번호부를 반으로 갈라버립시다. 그리고 50번이랑 박철수의 이름을 비교합시다. 만약에 50번이 박철수보다 순번이 뒤에요. 뭐 신철수 이런 거라고 칩시다. 그러면 우리가 반으로 가른 출석번호부 중 뒷쪽 절반은 필요없겠어요. 박철수가 거기 없을 거라는 걸 미리 알아버렸네요. 그러면 또 절반을 갈라봅시다. 그런데 이번엔 25번이 류철수에요. 박철수는 그러면 출석번호가 25번보다 큰 게 확정이니 그러면 이번엔 앞쪽을 버리면 되겠네요. 이런식으로 범위를 좁혀나가면서 찾을 수 있겠습니다.
또 코드를 보죠!
#include <iostream>
#include <vector>
using namespace std;
bool binary_search(int N, const vector<int>& vec) {
auto first = vec.begin();
auto last = vec.end();
while (first < last) {
auto range_length = distance(first, last);
auto mid_distance = range_length / 2;
auto mid_element_iter = first + mid_distance;
auto mid_element = *mid_element_iter;
if (mid_element == N) return true;
else if (mid_element > N) last = mid_element_iter;
else if (mid_element < N) first = mid_element_iter + 1;
}
return false;
}
int main(void) {
vector <int> vec = { 1,2,3,4,5 };
if (binary_search(3, vec)) cout << "found";
else cout << "not found";
}
코드가 아까보다 약간 깁니다. 그래도 한 번 보죠. first는 벡터의 머리 last는 벡터의 꼬리입니다. 그리고 원소 개수를 표현하기 위해 distance(first, last) 이렇게 설정하였어요. 철수의 출석번호 이야기를 할 때 강조한 부분이 계속 있죠? 중간 세팅입니다. 그냥 반으로 갈라버린 부분이 N이랑 일치하면 true 반환하고 종료하면 끝이죠. 반갈죽 한 부분이 N보다 크다면 뒷부분은 찾아볼 필요 없겠어요. 앞부분으로 범위 좁혀주면서 찾아주면 됩니다. 반대 방향도 같아요.
시간복잡도는 O(logN)입니다.
사실 실행 결과는 당연히 같습니다. 그럼 이놈들 시간을 어떻게 비교하죠? 비교하는 프로그램을 작성해봅시다. 조금 길지만 할 수 있어요.
3. 실행시간 비교
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
using namespace std;
bool linear_search(int N, vector <int> vec) {
for (int i : vec) {
if (i == N) return true;
}
return false;
}
bool binary_search(int N, const vector<int>& vec) {
auto first = vec.begin();
auto last = vec.end();
while (first < last) {
auto range_length = distance(first, last);
auto mid_distance = range_length / 2;
auto mid_element_iter = first + mid_distance;
auto mid_element = *mid_element_iter;
if (mid_element == N) return true;
else if (mid_element > N) last = mid_element_iter;
else if (mid_element < N) first = mid_element_iter + 1;
}
return false;
}
void run_small_search_test() {
int N = 2;
vector<int> S = { 1, 3, 2, 4, 5, 7, 9, 8, 6 };
sort(S.begin(), S.end());
// 선형 탐색 시간 측정 시작
auto start = chrono::steady_clock::now();
if (linear_search(N, S)) cout << "found by linear searching" << '\n';
else cout << "not found by linear searching" << '\n';
auto end = chrono::steady_clock::now();
// 선형 탐색 시간 측정 끝
auto diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "linear search execution time: " << diff << " microseconds" << '\n';
// 이진 탐색 시간 측정 시작
start = chrono::steady_clock::now();
if (binary_search(N, S)) cout << "found by binary searching" << '\n';
else cout << "not found by binary searching" << '\n'; // 출력 오타 수정
end = chrono::steady_clock::now();
// 이진 탐색 시간 측정 끝
diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "binary search execution time: " << diff << " microseconds" << '\n';
}
void run_large_search_test(int size, int N) {
vector<int> S;
random_device rd;
mt19937 rand(rd());
uniform_int_distribution<mt19937::result_type> uniform_dist(1, size);
for (int i = 0; i < size; i++) S.push_back(uniform_dist(rand));
sort(S.begin(), S.end());
// 선형 탐색 시간 측정 시작
auto start = chrono::steady_clock::now();
bool linear_search_result = linear_search(N, S);
auto end = chrono::steady_clock::now();
// 선형 탐색 시간 측정 끝
auto linear_diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "linear search execution time: " << linear_diff << " microseconds" << '\n';
// 이진 탐색 시간 측정 시작
start = chrono::steady_clock::now();
bool binary_search_result = binary_search(N, S);
end = chrono::steady_clock::now();
// 이진 탐색 시간 측정 끝
auto binary_diff = chrono::duration_cast<chrono::microseconds>(end - start).count();
cout << "binary search execution time: " << binary_diff << " microseconds" << '\n';
if (linear_search_result) cout << "element found in linear search" << '\n';
else cout << "element not found in linear search" << '\n';
if (binary_search_result) cout << "element found in binary search" << '\n';
else cout << "element not found in binary search" << '\n';
}
int main(void) {
run_small_search_test();
run_large_search_test(10000, 36543);
run_large_search_test(100000, 36543);
run_large_search_test(1000000, 36543);
}
좀 깁니다...그러나 시간 측정하는 부분만 보시면 되겠어요. 실행하면 결과는
//small
found by linear searching
linear search execution time: 135 microseconds
found by binary searching
binary search execution time: 52 microseconds
//large
linear search execution time: 41 microseconds
binary search execution time: 7 microseconds
element not found in linear search
element not found in binary search
linear search execution time: 105 microseconds
binary search execution time: 13 microseconds
element found in linear search
element found in binary search
linear search execution time: 4561 microseconds
binary search execution time: 59 microseconds
element not found in linear search
element not found in binary search가독성이 무척 구리다
대체로 이진 검색이 빠르죠. 그렇다면 이진 검색이 언제나 좋을까요? 꼭 그렇지는 않습니다. 일단 이진검색은 구현이 복잡하고, 정렬이 되어있어야 합니다. 만약에 출석번호부가 랜덤이고 이를 정렬하는 과정을 거치지 않는다면 이진검색을 쓸 수 없습니다. 김철수랑 박철수랑 비교했는데 누가 앞에 있는지 알 수 없다면 저런 방법을 쓸 수가 없습니다. 그러나 선형 검색을 한다면 그냥 박철수가 나올 때까지 읽어버리면 되니 상관이 없죠.
