순차 탐색
리스트 안에 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법.
이처럼 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점이 특징이다.
시간 복잡도
따라서 데이터의 개수가 N개일 때 시간 복잡도는 이다.
python으로 구현한 순차탐색 :
# strs 처음부터 끝까지 target과 같은 것이 있는지 확인
def sequential_search(n, target, strs) :
for i in range(n) :
if strs[i] == target :
return i
print("생성할 원소의 개수와 찾을 문자열을 입력하세요 : ")
user_input = input().split()
n = int(user_input[0])
target = user_input[1]
print("앞서 적은 원소 개수만큼 문자열을 입력하세요 : ")
strs = input().split()
# 순차 탐색 수행 결과 출력
print(str(target) + "은 "+str(sequential_search(n, target, strs))+"번째 인덱스에 있습니다.")이진 탐색
이진 탐색(Binary Search)는 데이터가 정렬되어 있어야만 사용배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
이진 탐색은 위치를 나타내는 변숙 3개를 사용한다. (시작점, 끝점, 중간점)
탐색 과정
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
시간 복잡도
이진 탐색은 한 번 확인할 때마다 확인해야 하는 데이터 개수가 절반씩 줄어든다.
따라서 의 시간 복잡도를 갖는다.
c++로 구현한 이진 탐색 (재귀)
#include <iostream>
int binarySearch(int _arr[], int start, int end, int _target){
int mid = (start + end) / 2;
if(start > end){
return -999;
}
// 찾은 경우
if(_arr[mid] == _target){
return mid;
}
// mid보다 큰 경우
else if(_arr[mid] < _target) {
return binarySearch(_arr, mid+1, end, _target);
}
// mid보다 작은 경우
else {
return binarySearch(_arr, start, mid-1, _target);
}
}
using namespace std;
int main(void){
int n, target;
cin >> n >> target;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
int user_input;
cin >> user_input;
arr[i] = user_input;
}
int index = binarySearch(arr, 0, n-1, target);
if(index) {
cout << target << "은 " << index << "번 인덱스에 있습니다\n";
}
else {
cout << target << "은 존재하지 않습니다.\n";
}
return 0;
}이진 탐색 문제 TIP : sys 라이브러리의 readline(), rstrip()
이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 매우 넓은 편이다.
입력 데이터의 개수가 많은 문제에 python의 input() 함수를 이용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다.
이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하여 시간 초과를 피해야 한다.
sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다. 소스크드에 readline()으로 입력하면 입력 후 개행문자가 버퍼에 남는데, 버퍼를 비우기 위해 rstrip() 함수를 사용해야 한다.
sys library in python : readline(), rstrip()
import sys
user_input = sys.stdin.readline().rstrip()
print(user_input)이진 탐색 문제 TIP : bisect 라이브러리의 bisect_left(), bisect_right()
bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 6]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))#include <iostream>
#include <vector>
using namespace std;
int main(void){
vector <int> arr = {1, 2, 4, 4, 6};
int x = 4;
cout << lower_bound(arr.begin(), arr.end(), x) - arr.begin() << endl;
cout << upper_bound(arr.begin(), arr.end(), x) - arr.begin() << endl;
return 0;
}값이 특정 범위에 속하는 데이터 개수 구하기
from bisect import bisect_left, bisect_right
def countByRange(arr, left_value, right_value) :
right_index = bisect_right(arr, right_value)
left_index = bisect_left(arr, left_value)
return right_index - left_index
arr = [1, 2, 3, 3, 3, 3, 4, 4, 8 , 9]
# arr에서 값이 4~4인 개수 출력
print(countByRange(arr, 4, 4))
# arr에서 값이 -1~3인 개수 출력
print(countByRange(arr, -1, 3))Parametric Search
파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
ex. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
부품 찾기
문제 설명 :
문제 풀이 (이진 탐색) :
def binarySearch(nArr, start, end, target) :
if start > end :
return False
mid = (start + end) // 2
if nArr[mid] == target :
return True
elif nArr[mid] < target :
return binarySearch(nArr, mid + 1, end, target)
elif nArr[mid] > target :
return binarySearch(nArr, start, mid - 1, target)
n = int(input())
nArr = list(map(int, input().split()))
nArr.sort()
m = int(input())
mArr = list(map(int, input().split()))
for i in range(m) :
if binarySearch(nArr, 0, n-1, mArr[i]) == True:
print("yes", end=' ')
else :
print("no", end=' ')문제 풀이 (계수 정렬) :
n = int(input())
nArr = [0] * 1000001 # 입력 받는 정수는 1~1,000,000 라고 명시 되어 있기 때문
for i in input().split() :
nArr[int(i)] = 1
m = int(input())
mArr = list(map(int, input().split()))
for i in range(m) :
if nArr[mArr[i]] == 1 :
print('yes', end=' ')
else :
print('no', end=' ')떡볶이 떡 만들기
문제 설명 :
아이디어 :
이 문제는 전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제이다.
적절한 높이를 찾을 때까지 절단기의 높이를 반복하여 조절하면 된다.
그래서 '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부에 따라서 탐색 범위를 좁혀서 해결할 수 있다.
절단기 높이는 10억보다 작거나 같은 양의 정수 또는 0이라고 정의되어 있기 때문에 순차 탐색을 10억번 반복하면, 시간 초과를 받을 수 있다.
- 따라서 이진 탐색을 사용해야 한다.
(절단기의 길이를 줄이거나 늘리면서 범위를 좁혀나간다)
또한, 시간을 더 절약하기 위해 절단기 높이 H는 가장 긴 떡의 길이 안에 있어야 떡을 자를 수 있다. 따라서 이진 탐색의 탐색 범위를 start = 0 , end = 19로 설정해야 한다.
- 이진 탐색의 초기 탐색 범위를 start = 0, end = 떡 개별 높이의 최대값으로 하면 더욱 효율적이다.
문제 풀이 :
#include <iostream>
using namespace std;
// 임의로 설정한 절단기 길이 : mid = (start + end) / 2
// (mid만큼 자르고 남은 떡들의 합) < m 인 경우, mid+1 다시 탐색
// (mid만큼 자르고 남은 떡들의 함) > m 이 되는 경우, mid-1 다시 탐색 (단, 가장 최근의 mid값을 저장)
// 위 과정이 start>end 될 때까지
int binarySearch(int _arr[], int start, int end, int _n, int _m){
int ret = 0;
while(start <= end) {
int sum = 0;
int mid = (start + end) / 2;
for (int i = 0; i < _n; i++)
{
int cut_len = _arr[i] - mid;
// 자른 떡의 길이가 양수라면, sum에 더한다
if(cut_len > 0) {
sum += _arr[i] - mid;
}
// 자른 떡의 길이가 음수 == 절단기가 길어서 떡이 잘라지지 않음
else sum += 0;
}
// 떡이 사용자가 요구한 것보다 충분하면, 절단기 길이를 늘림 == 떡을 덜 자름(왼쪽 부분 탐색)
if(sum >= _m){
ret = mid; // 최적화된 절단기 길이 갱신
start = mid+1;
}
// 떡이 모자라면, 절단기 길이를 줄임==떡을 더 많이 자름(오른쪽 부분 탐색)
else {
end = mid-1;
}
}
return ret;
}
int main(void){
// 자를 떡의 개수(N)과 사용자가 필요한 떡의 양(M)을 입력받기
int n,m;
cin >> n >> m;
// 떡 개별 높이 입력 받기
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
int user_input;
cin >> user_input;
arr[i] = user_input;
}
// 이진 탐색의 초기 탐색 범위를 start = 0, end = 떡 개별 높이의 최대값
int start = 0;
int end = *max_element(arr, arr+n);
// 이진 탐색 시작
int max_h = binarySearch(arr, start, end, n, m);
cout << max_h << endl;
return 0;
}정렬된 배열에서 특정 수의 개수 구하기
문제 설명 :
이진 탐색을 직접 구현한 문제 풀이 :
#include <iostream>
using namespace std;
int last = -1;
int findFirstX(int _arr[], int start, int end, int _x){
int mid = (start + end) / 2;
if(start > end) {
return last;
}
// 찾는 값이 나오면, last값 갱신, return하지 않고 더 적은 index를 찾는다)
if(_arr[mid] == _x){
last = mid;
return findFirstX(_arr, start, mid-1, _x);
}
// 찾는 값이 더 크면
else if(_arr[mid] < _x) {
return findFirstX(_arr, mid+1, end, _x);
}
// 찾는 값이 더 작으면
else if(_arr[mid] > _x) {
return findFirstX(_arr, start, mid-1, _x);
}
}
int findSeondX(int _arr[], int start, int end, int _x){
int mid = (start + end) / 2;
if(start > end) {
return last;
}
// 찾는 값이 나오면, last값 갱신, return하지 않고 더 큰 index를 찾는다)
if(_arr[mid] == _x){
last = mid;
return findSeondX(_arr, mid+1, end, _x);
}
// 찾는 값이 더 크면
else if(_arr[mid] < _x) {
return findSeondX(_arr, mid+1, end, _x);
}
// 찾는 값이 더 작으면
else if(_arr[mid] > _x) {
return findSeondX(_arr, start, mid-1, _x);
}
}
int main(void){
int n, x;
cin >> n >> x;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
int user_input;
cin >> user_input;
arr[i] = user_input;
}
last = -1;
int firstX = findFirstX(arr, 0, n-1, x);
last = -1;
int secondX = findSeondX(arr, 0, n-1, x);
if(firstX == -1 || secondX == -1){
cout << -1 << endl;
}
else {
cout << secondX - firstX + 1 << endl;
}
return 0;
}
/*
7 2
1 1 2 2 2 2 3
*/bisect library를 이용한 문제 풀이 :
# bisect library 사용
from bisect import bisect_left, bisect_right
def countByRange(arr, x) :
right_index = bisect_right(arr, x)
left_index = bisect_left(arr, x)
return right_index - left_index
n, x = map(int, input().split())
arr = list(map(int, input().split()))
count = countByRange(arr, x)
if count == 0 :
print(-1)
else :
print(count)