선형 탐색
가장 기본적인 탐색 방법. 순차적으로 하나하나 검사하는 방법임 하나의 반복문으로 구현 가능
예시
예시 문제 : 배열 arr에서 특정 값 k의 위치 찾기
int index = -1;
for(int i = 0; i < arr.size(); i++){
if(arr[i] == k) {
index = k;
break;
}
}
return index;쌍 전체 탐색
선형 탐색을 여러 배열에서 실행함
예시
예시 문제 : 배열 a와 b가 있을 때, 각 배열에서 하나씩 숫자를 고른 쌍의 합이 K 이상인 값 중 최소인 값
int minValue = 1 << 30; // 충분히 큰 값
for(int i = 0; i < a.size(); i++){
for(int j = 0; j < b.size(); j++) {
int ab = a[i]+b[j];
if(ab > k && ab < minValue) minValue = ab;
}
}조합 전체 탐색
비트를 사용하면 할 수 있음.
사용 예시 : 크기가 4인 배열이 있을 때, 배열 안에 있는 요소들의 모든 조합 구하기
| a[3] | a[2] | a[1] | a[0] |
|---|---|---|---|
| 0 | 1 | 1 | 0 |
a[2]와 a[1]을 사용한 조합의 예시
예시
예시 문제 : 배열 a 안에 있는 수들을 더해서 정해진 수 w를 만들 수 있는지 판정 (부분합 문제)
bool exist = true;
for(int bit = 1; bit < (1 << a.size()); bit ++){
int sum_a = 0;
for(int i = 0; i < a.size(); i++){
if(bit & (1 << i)) sum_a += a[i];
}
if(sum == w) exist = true;
break;
}