지나공 : 지식을 나누는 공간
[4] C++ 이진탐색 이것이 코딩테스트다 chapter7 정리 본문
오늘 알아볼 내용은,
- 순차 탐색
- 이진 탐색
- 트리 자료구조
- 이진 탐색 트리
- 실전문제 - 부품 찾기
- 실전문제 - 떡볶이 떡 만들기
순차 탐색
[개념]
가장 기본 탐색 방법으로, 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 탐색 알고리즘이다. 이름처럼, 순차로 데이터를 탐색한다.
[사용예]
- 배열에 특정 값의 원소가 있는지 체크할 때
- 배열 자료형에서 특정한 값을 가지는 원소의 개수를 셀 때
[코드]
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int sequantialSearch(int n, string target, vector<string> arr) {
//모든 원소 하나씩 확인
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i + 1; //현 위치 반환(인덱스보다 하나 크게)
}
}
return -1; //찾지 못하면 -1 반환
}
int n; //원소개수
string target;
vector<string> arr;
int main(void) {
cout << "생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요. " << '\n';
cin >> n >> target;
cout << "앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다." << "\n";
for (int i = 0; i < n; i++) {
string x;
cin >> x;
arr.push_back(x);
}
//순차 탐색 결과 출력
cout << sequantialSearch(n, target, arr) << "\n";
}이진 탐색
[소개]
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘으로, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. 탐색 번위를 절반씩 좁혀가며 탐색하고, 반씩 좁혀가는 점은 퀵 정렬과 비슷하다.
[방법]
변수 3개를 사용하고, 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 사용한다.
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
7개 원소를 가진 배열에서 50을 찾는다고 하자.
7의 1/2는 3.5인데 중간점 위치는 소수점 이하는 버리고 정한다. 즉 인덱스 3번째 값이 중간점이다.
arr[3]인 35와, 찾으려는 값 50을 비교한다.
50이 더 크므로, 중간점을 포함해서 그보다 작은 값들은 볼 필요가 없다. arr[4]부터 마지막 인덱스까지 재탐색하면 된다.
arr[4]부터 arr[6]까지 탐색하므로 중간값의 인덱스는 (4+6)/2 = 5 이다. 중간값 arr[5]인 65와 찾으려는 데이터 50과 비교하면 중간값을 포함해서 그 이후의 값은 더 볼 필요가 없다. 즉, 4번째 인덱스가 50임을 알 수 있다.
[시간복잡도]
한번 확인할 때마다 확인할 원소 개수가 절반씩 줄어드므로 log2N, 밑이 2인 -> 즉 시간복잡도가 O(logN)이다.
[코드]
1. 재귀함수로 구현
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
//찾았다면 중간점 인덱스 반환
if (arr[mid] == target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
else return binarySearch(arr, target, mid + 1, end);
}
int n, target;
vector<int> arr;
int main() {
//n(원소개수)와 target(찾으려는 값) 입력받기
cin >> n >> target;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
//이진탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
cout << "원소가 존재하지 않습니다.";
}
else {
cout << result + 1 << '\n';
}
}
2. 단순 반복문으로 구현
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) end = mid + 1;
else start = mid + 1;
}
return -1;
}
int n, target;
vector<int> arr;
int main() {
//n(원소개수)와 target(찾으려는 값) 입력받기
cin >> n >> target;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
//이진탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
cout << "원소가 존재하지 않습니다.";
}
else {
cout << result + 1 << '\n';
}
}
부품 찾기 코드
이진탐색을 재귀함수로 구현하여 해결했다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int>arr;
vector<int>cus;
string binarySearch(vector<int>& arr, int target, int start, int end) {
if (start > end) return "no";
int mid = (start + end) / 2;
if (arr[mid] == target)
return "yes";
else if (arr[mid] > target)
return binarySearch(arr, target, start, mid - 1);
else
return binarySearch(arr, target, mid + 1, end);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
cin >> m;
for (int i = 0; i < m; i++) {
int x;
cin >> x;
cus.push_back(x);
}
for (int num : cus) {
string exist = binarySearch(arr, num, 0, n - 1); //타겟이 있는지 탐색할 대상은 arr이니까 n개
cout << exist << " ";
}
}
책을 보니 계수 정렬이나 set으로도 풀 수 있다고 한다.
계수정렬로 풀기
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int arr[1000001]; // 100만개의 데이터인데 100만번째 인덱스가 존재해야 하므로 1 더 크게
vector<int> cus; //손님거
int main() {
cin >> n;
for (int i = 0; i < n; i++) { //매장부품 입력
int x;
cin >> x;
arr[x] = 1;
}
cin >> m;
for (int i = 0; i < m; i++) {//손님 부품 입력
int x;
cin >> x;
cus.push_back(x);
}
for (int i = 0; i < m; i++) {
if (arr[cus[i]] == 1) {
cout << "yes" << " ";
}
else {
cout << "no" << " ";
}
}
}
set으로 풀기
set은 단순히 특정 데이터가 존재하는 지 검사할 때 코드 간결성에 있어 매우 효과적이다.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, m;
set<int> s;
vector<int> cus; //손님거
int main() {
cin >> n;
for (int i = 0; i < n; i++) { //매장부품 입력
int x;
cin >> x;
s.insert(x);
}
cin >> m;
for (int i = 0; i < m; i++) {//손님 부품 입력
int x;
cin >> x;
cus.push_back(x);
}
for (int i = 0; i < m; i++) {
if (s.find(cus[i]) != s.end()) {
cout << "yes" << " ";
}
else {
cout << "no" << " ";
}
}
}
떡볶이 떡 만들기 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int binarySearch(vector<int>& nums, int n, int m, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2; //현 절단기 설정 높이
cout << "mid : " << mid << " ";
int rice = 0; //손님이 가져갈 떡
for (int i = 0; i < n; i++) {
if(nums[i] > mid)
rice = rice + (nums[i] - mid);
}
cout << "rice : " << rice << endl;
if (m == rice) {
return mid; //현 높이 반환
}
else if (m < rice) { //정답의떡에 비해 더 많은 게 잘렸으니까 높이를 높여서 잘릴 떡을 줄이자.
start = mid + 1;
}
else {
end = mid - 1;
}
}
return -1;
}
int m, n;
vector<int> nums;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
nums.push_back(x);
}
sort(nums.begin(), nums.end());
int top = nums[n - 1];
//중간점의 위치 받기
int mid = binarySearch(nums, n, m, 0, top);
cout << mid << endl;
}위 문제에서 마지막에 좀 헤맨 부분은...떡 높이보다 큰 떡에 대해서만 차이값을 구해야 하는데 그거에 대한 조건문을 빠뜨린 바람에 ,,, binarySerach 함수 안에서 nums에 대해 for문을 돌릴 때 mid보다 큰 값에 대해서만 nums[i] - mid를 해야 한다.
이것이 코딩테스트다 라는 책을 보며 정리한 내용입니다.
