순차 탐색
최악의 시간 복잡도: O(N)
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용
#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int num;
vector<string> str;
string target;
int ans;
cin >> num >> target;
for (int i = 0; i < num; i++) {
string strTmp;
cin >> strTmp;
str.push_back(strTmp);
}
for (ans = 0; ans < num; ans++) {
if (str[ans] == target) {
break;
}
}
cout << ans+1;
}
이진탐색 : 반으로 쪼개면서 탐색하기
시간복잡도: O(logN)
배열 내부가 정렬되어있어야만 사용가능
#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int cnt;
vector<int> num;
int target;
int func(int left, int right) {
if (left > right) return -1;
int mid = (left + right) / 2;
if (num[mid] == target) {
return mid;
}
else if (num[mid] > target) {
return func(left, mid - 1);
}
else {
return func(mid + 1, right);
}
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> cnt >> target;
for (int i = 0; i < cnt; i++) {
int tmp;
cin >> tmp;
num.push_back(tmp);
}
sort(num.begin(), num.end());
int ans = func(0, cnt-1);
if (ans == -1) {
cout << "원소가 존재하지 않습니다.";
return 0;
}
cout << ans+1;
}
Parametric Search (파라메트릭 서치)
최적화 문제를 결정하는 문제로 바꿔서 해결하는 기법
⇒ 결정하는 문제 = '예' '아니오'로 대답
ex ) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으려는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁힐 수 있다
떡볶이 떡 자르기 문제
- '떡볶이 떡 자르기' 문제를 예로 하면 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복적으로 조정한다
- 현재 이 높이로 자르면 조건을 만족할 수 있는가 → 예 vs 아니오
- 범위로 좁힐 때는 이진 탐색 원리를 이용해 절반찍 좁혀나간다
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int cnt;
int etc;
vector<int> rice;
cin >> cnt >> etc;
for (int i = 0; i < cnt; i++) {
int tmp;
cin >> tmp;
rice.push_back(tmp);
}
int left, right;
sort(rice.begin(), rice.end());
left = 0;
right = rice.back();
int ans, mid;
while (left < right) {
ans = 0;
mid = (left + right) / 2;
for (int i = 0; i < cnt; i++) {
int tmp = rice[i] - mid < 0 ? 0 : rice[i] - mid;
ans += tmp;
}
if (ans == etc) break;
else if (ans < etc) {
right = mid - 1;
}
else {
// 적어도 M만큼의 떡을 얻기 위해
result = mid;
left = mid + 1;
}
}
cout << result;
}
'Algorithm > C++' 카테고리의 다른 글
[개념] 최단 경로 구하기 (0) | 2020.10.13 |
---|---|
[개념] 다이나믹 프로그래밍(동적계획법) (0) | 2020.10.11 |
[개념] DFS/BFS (0) | 2020.10.09 |
[개념] 정렬 알고리즘 (0) | 2020.10.01 |