[알고리즘] 원하는 조건 내에서 탐색 알고리즘

직접 원하는 조건을 만족하는 탐색을 작성할 수 있다.

 

https://hgu-can.tistory.com/entry/C-find-vs-findif-%EC%B0%A8%EC%9D%B4%EC%A0%90

[C++] find vs find_if 차이점

예를들면 pair로 저장된 vector에서 first와 second 모두 target보다 큰 값만 원할 때 직접 사용자 비교 함수를 정의하여 넣어줄 수 있다.

https://pangtrue.tistory.com/39

[C++ STL] '탐색 알고리즘(search algorithm)'

binarysearch 특정 조건 탐색 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>
#define F first
#define S second

using namespace std;
typedef pair<int, int> PII;

int N, M, H[2001][2002], T;
vector<PII> rec;
vector<PII> sta;

void solve() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M + 1; j++) {
            if (sta.empty() || H[i][j] > sta.back().F) sta.push_back({H[i][j], j});
            else if (H[i][j] == sta.back().F) continue;
            else {
                PII temp;
                int idx;
                while (!sta.empty() && H[i][j] <= sta.back().F) {
                    temp = sta.back();
                    idx = temp.S;
                    if (temp.F != 0) rec.push_back({temp.F, j - temp.S});
                    sta.pop_back();
                }
                sta.push_back({H[i][j], idx});
            }
        }
    }
    sort(rec.begin(), rec.end());
}

bool lessOrEqual(const PII p1, const PII p2) {
    return p1.F >= p2.F && p1.S >= p2.S;
}

bool go(const vector<PII>& r, const PII& t) {
    auto it = lower_bound(r.begin(), r.end(), t);
    return it == r.end() || !lessOrEqual(*it, t);
}

int main(void) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        string str;
        cin >> str;
        for (int j = 1; j <= M; j++) {
            if (str[j - 1] == '.')
                H[i][j] = H[i - 1][j] + 1;
            else
                H[i][j] = 0;
        }
    }
    solve();

    cin >> T;
    while (T--) {
        PII target;
        cin >> target.F >> target.S;
        if (go(rec, target))
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

find_if 탐색 알고리즘

#include<iostream>
#include<vector>
#include<algorithm>
#define F first
#define S second

using namespace std;
typedef pair<int, int> PII;

int N, M, H[2001][2002], T;
vector<PII> rec;
vector<PII> sta;

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M + 1; j++) {
			if (sta.empty() || H[i][j] > sta.back().F) sta.push_back({H[i][j], j});
			else if (H[i][j] == sta.back().F) continue;
			else {
				PII temp;
				int idx;
				while (!sta.empty() && H[i][j] <= sta.back().F) {
					temp = sta.back();
					idx = temp.S;
					if(temp.F != 0)rec.push_back({temp.F, j - temp.S});
					sta.pop_back();
				}
				sta.push_back({ H[i][j], idx });
			}
		}
	}
}

bool lessOrEqual(const PII p1, const PII p2) {
	return p1.F >= p2.F && p1.S >= p2.S;
}

bool go(vector<PII> r, PII t) {

	auto ret = find_if(r.begin(), r.end(), [&](const auto& pair) {
		return lessOrEqual(pair, t);
		});

	return ret == r.end();
}


int main(void) {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int j = 1; j <= M; j++) {
			if (str[j - 1] == '.') H[i][j] = H[i - 1][j] + 1;
			else H[i][j] = 0;
		}
	}
	solve();
	//sort(rec.begin(), rec.end());
	cin >> T;
	while (T--) {
		PII target;
		cin >> target.F >> target.S;
		if (go(rec, target)) cout << "NO\n";
		else cout << "YES\n";
	}

	//for (auto e : rec) cout << e.F << " " << e.S << "\n";


}