순차 탐색
: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.
- 순차 탐색 소스코드
def sequential_search(n, target, array) :
for i in range(n) :
if array[i] == target :
return i+1
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0])
target = input_data[1]
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()
print(sequential_search(n, target, array))- 순차 탐색의 최악의 경우 시간 복잡도
: O(N)
이진 탐색 : 반으로 쪼개면서 탐색하기
: 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
- 재귀 함수로 구현한 이진 탐색 소스코드
n, target = map(int, input().split())
array = list(map(int, input().split()))
def binary_search(target, array, start, end) :
if start > end :
return None
mid = (start + end) // 2
if target == array[mid] :
return mid
elif target > array[mid] :
return binary_search(target, array, mid+1, end)
else :
return binary_search(target, array, start, mid-1)
result = binary_search(target, array, 0, n-1)
if result == None :
print("fail")
else :
print(result + 1)먼저 이진 탐색이 어떻게 진행되는지 생각해놓고 작성하면 된다.
재귀 함수가 아닌 반복문을 사용할 경우는 아래와 같다.
n, target = map(int, input().split())
array = list(map(int, input().split()))
def binary_search(target, array, start, end) :
while start <= end :
mid = (start + end) // 2
if target == array[mid] :
return mid
elif target > array[mid] :
start = mid+1
else :
end = mid-1
result = binary_search(target, array, 0, n-1)
if result == None :
print("fail")
else :
print(result + 1)이진 탐색 코드는 그냥 암기하기!
- 트리 자료구조
: 노드와 노드의 연결로 표현
여기서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다.
이러한 트리 구조를 이용하여 이진 탐색이 가능한 방식이 바로 이진 탐색 트리이다.
이진 탐색 트리
: 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
트리 자료구조 중에서 가장 간단한 형태
- 이진 탐색 트리의 특징
-> 부모 노드보다 왼쪽 자식 노드가 작다.
-> 부모 노드보다 오른쪽 자식 노드가 크다.
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야 이진 탐색 트리라 할 수 있다.
빠르게 입력받기
: 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다.
이때 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다.
이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간초과를 피할 수 있다.
import sys
input = sys.stdin.readline().rstrip()sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다.
소스코드에 readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데,
이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다.
실전 문제
- 부품 찾기
: 이진 탐색으로 찾은 경우
import sys
input = sys.stdin.readline
n = int(input())
store = list(map(int, input().split()))
m = int(input())
need = list(map(int, input().split()))
store = sorted(store)
def binary_search(target, array, start, end) :
if start > end :
return "No"
mid = (start + end) // 2
if array[mid] == target :
return "yes"
elif array[mid] > target :
return binary_search(target, array, start, mid-1)
else :
return binary_search(target, array, mid+1, end)
for i in need :
result = binary_search(i, store, 0, n-1)
print(result, end=" "): 집합 자료형 이용
n = int(input())
array = set(map(int, input().split()))
m = int(input())
x = list(map(int, input().split()))
for i in x :
if i in array :
print("yes", end=" ")
else :
print("no", end=" ")집합 자료형으로 단순히 특정 데이터가 존재하는지 검사할 수 있다. set() 함수 사용
- 떡볶이 떡 만들기
: 처음 작성한 코드
n, m = map(int, input().split())
array = list(map(int, input().split()))
result = 0
def binary_search(target, start, end) :
total = 0
if start > end :
return None
mid = (start + end) // 2
for i in array :
if i >= mid :
total += i-mid
if total == target :
return mid
elif total > target :
return binary_search(target, mid+1, end)
else :
return binary_search(target, start, mid-1)
an = binary_search(m, 0, max(array))
if an != None :
print(an)주어진 입력 예시는 잘 돌아가지만 틀렸다.
: 답안 예시
n, m = map(int, input().split())
array = list(map(int, input().split()))
result = 0
start = 0
end = max(array)
while start >= end :
total = 0
mid = (start + end) // 2
for x in array :
if x > mid :
total += x-mid
if total < m :
end = mid-1
else :
result = mid
start = mid + 1
print(result)재귀적으로 구현하지 않고 반복문을 사용하여 더 간결하게 만들었다.
시작은 0, 끝점은 주어진 떡의 길이 중 가장 긴 길이
total 에 잘랐을 때의 떡의 양을 더하고
다 더한 total 값이 요청한 떡의 길이 m보다 부족한 경우 더 많이 잘라야 하므로
end = mid-1로 하고, 아닌경우 떡의 양이 충분하기 때문에 덜 자른다.
최대한 덜 잘랐을 때가 정답이므로 result에 mid값을 저장하고 start = mid + 1로 한다.
