[알고리즘] 완전탐색(순차탐색)/이분탐색(이진탐색)

완전 탐색(=Brute Force) / 순차 탐색(=Sequential Search)

• 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 효율성 관점에서 최악의 방법
• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 시간 복잡도 : O(N) = 선형 복잡도 = 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것

[반복문]

def solution(trump):
	for i in range(len(trump)):
		if trump[i]==8:
			return i
	return -1

 

def sequential_search(n, target, array):
	for i in range(n):
		if array[i] == target:
			return i+1

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()   #5 Dongbin
n = int(input_data[0])
target = input_data[1]

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()   #Hanul Jonggu Dongbin Taeil Sangwook

print(sequential_search(n, target, array))

 

[재귀 함수]

def solution(trump,loc):
	if trump[loc]==8:
		return loc
	else:
		return solution(trump,loc+1)

 

---

 

이분 탐색(=이진 검색, Binary Search)

• 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘.
• 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법
• 시간 복잡도 : O(logN) 
• 이진 탐색 트리 : 부모 노드에서 왼쪽 노드는 부모 노드보다 작고, 오른쪽 노드는 부모 노드보다 크다

[분할 정복 알고리즘과 이진 탐색]
- 분할 정복 알고리즘 (Divide and Conquer)
  - Divide: 문제를 하나 또는 둘 이상으로 나눈다.
  - Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.
- 이진 탐색
  - Divide: 리스트를 두 개의 서브 리스트로 나눈다.
  - Comquer
    - 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
    - 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.  

 

 

[반복문]

#학원? #책?

def solution(array):
	left = 0
	right = len(array)-1

	while(left<=right):
		mid=(left+right)//2
		if array[mid]==target:
			return mid
		elif array[mid]<target:
			left = mid+1
		elif array[mid]>target:
			right = mid -1

	return mid

 

[재귀 함수]

#학원? #책? #패스트캠퍼스
def binary_search(array, target, start, end):
	if start>end:
		return None
	mid=(start+end)//2   #int함수 사용 가능
	if array[mid]==target:
		return mid
	elif array[mid]>target:
		return binary_search(array, target, start, mid-1)
	else:
		return binary_search(array, target, mid+1, end)

n, target = list(map(int, input().split()))   #10 7
array = list(map(int, input().split()))   #1 3 5 7 9 11 13 15 17 19

result = binary_search(array, target, 0, n-1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

#패스트캠퍼스
def binary_search(data, search):
    print (data)
    if len(data) == 1 and search == data[0]:
        return True
    if len(data) == 1 and search != data[0]:
        return False
    if len(data) == 0:
        return False
    
    medium = len(data) // 2
    if search == data[medium]:
        return True
    else:
        if search > data[medium]:
            return binary_search(data[medium+1:], search)
        else:
            return binary_search(data[:medium], search)