검색(Searching)
- 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야 한다.
- 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다.
- 검색하는 컬렉션이 무작위이고 정렬되지 않은 경우, 선형검색이 기본적인 검색방법이다.
linear search (선형 검색, (순차탐색))
- 한 번에 하나씩 모두 검색
- 반복문을 활용해 배열의 변수(코드에서는 반복자 i)만큼 검색을 진행
# 선형 검색 알고리즘
# 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다.
def linear_search(arr, target):
# 입력 배열 길이의 범위에서 각 idx를 반복
for idx in range(len(arr)):
# 현재 idx의 항목이 비교 대상과 같은지 확인
if arr[idx] == target:
# 현재 인덱스를 일치 항목으로 반환
return idx
# 전체 배열을 반복할 수 있다면, 비교 대상은 존재하지 않는다.(의미없는 -1 값 반환)
return -1
print(linear_search([0,1,2], 2)) # case 1 - true
print(linear_search([0,1,2], 3)) # case 2 - falseBinary search(이진 검색)
- 반복을 통해 숫자를 반으로 줄이면서 검색을 진행하기 때문에 선형(순차탐색)보다 속도가 더 빠르다.
- 데이터가 이미 정렬된 경우에만 작동
- 시간복잡도: O(logN)
- 프로그래밍에서 로그에 대해 이야기 할 때 항상 log2()를 의미하는데, 그 이유는 컴퓨터가 2진수 시스템에서 작동하기 때문
- 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산횟수는 log₂N에 비례한다
- 이진 탐색은 인덱스의 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
- step 1: 시작점(low) 0, 끝점(high) 7 (idx는 0부터 시작), 중간점(middle) 4 (소수점 이하 제거)
- step 2: 찾고자하는 value(Search_item)가 middle하고 같을 경우 [middle]값 return
- step 3: 찾고자하는 value(Search_item)가 middle보다 작을경우 중간점에서 -1한 지점을 끝점으로 잡고 재탐색
- 시작점(low) 0, 끝점(high) 3 (idx는 0부터 시작), 중간점(middle) 1 (소수점 이하 제거)
- 시작점(low) 0, 끝점(high) 3 (idx는 0부터 시작), 중간점(middle) 1 (소수점 이하 제거)
- step 4: 찾고자하는 value(Search_item)가 middle보다 클경우 중간점에서 +1한 지점을 시작점으로 잡고 재탐색
- 시작점(low) 2, 끝점(high) 3 (idx는 0부터 시작), 중간점(middle) 2 (소수점 이하 제거)
'''반복문 이진 탐색'''
def binary_search(test_list, search_item):
#리스트를 처음 얻을 때 두 개의 다른 리스트(참조요소)를 설정
low = 0 # 인덱스가 0(리스트의 첫번째 항목)으로 주어진다.
high = len(test_list) - 1 # 인덱스의 마지막 항목(리스트길이-1)
while low <= high:
middle = (low + high) // 2 # middle을 지정해서 검색속도를 빠르게 한다.
guess = test_list[middle]
if guess == search_item:
return middle
if guess > search_item:
high = middle - 1
else:
low = middle + 1
return None
test_list = [6,12,17,23,38,45,77,84] # 이미 정렬된 리스트에서 검색 진행
print('binary_search',binary_search(test_list, 17))
'''
binary_search 2
''''''이진탐색의 재귀적 구현'''
def binary_search(arr, target, low, high):
if low > high:
return None
middle = (low+high) // 2
# 중간인덱스의 값과 찾을 값이 같으면 중간인덱스 반환
if arr[middle] == target:
return middle
# 중간인덱스의 값이 찾을 값보다 크면 마지막 점을 왼쪽으로 이동
elif arr[middle] > target:
return binary_search(arr, target, low, middle -1)
# 중간인덱스의 값이 찾을 값보다 작으면 시작점을을 오른쪽으로 이동동
else :
return binary_search(arr, target, middle + 1, high)
# n(원소의 개수)과 target(찾고자 하는값)을 입력 받기
n, target = list(map(int, input().split()))
#전체 원소 입력받기
arr = list(map(int, input().split()))
#이진 탐색 수행 결과 출력 하기
result = binary_search(arr, target, 0, n-1)
if result == None:
print ("원소가 존재하지 않습니다")
else:
print('찾고자하는 값의 인덱스:' , result+1)
'''
input
10 7
1 3 5 7 9 11 13 15 17 19
output
찾고자하는 값의 인덱스: 4
input
10 7
1 3 5 6 9 11 13 15 17 19
output
원소가 존재하지 않습니다
'''이진탐색을 이용한 문제 해결
파라메트릭 서치(Parametric Search)
- 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
- 이 문제는 이진탐색을 이용하여 해결 가능
'''
문제 떡볶이 떡 만들기:
떡볶이 떡의 길이가 일정하지 않다.
대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰 준다.
절단기에 높이 (H)를 지정하면 줄지어진 떡을 한 번에 절단 한다.
높이가 H보다 긴떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면
자른 뒤 떡의 높이는 15, 14, 10, 15cm가 된다.
잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다.
손님은 6cm만큼의 길이를 가져간다.
손님이 왔을때 요청한 총 길이가 M일때
적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하라.
'''
'''
입력조건:
첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1,000,000 / 1<= M <= 2,000,000,000)
둘째 줄에 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M이상 이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억 보다 작거나 같은 양의 정수 또는 0.
출력조건: 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력
'''
# n(떡의 개수)과 m(원하느 떡의 길이)을 입력 받기
n, m = list(map(int, input().split(' ')))
# 떡들의 개별 높이 정보 입력받기
arr = list(map(int, input().split()))
# 이진 탐색을 위한 가장낮은 인덱스와 끝점 설정
low = 0
high = max(arr)
def find_dduck(arr, M, low, high):
result = 0
while low<=high:
total = 0
mid = (low+high)//2
for x in arr: # 현재 떡의 길이를 비교
if x > mid: # 만약 arr에 담긴 떡의 총길이가 mid 보다 크다면 total에 저장
total += x - mid
#떡의 양이 부족한 경우 더 많이 자르기 (왼쪽으로 이동)
if total < m :
high = mid - 1
# 떡의 양이 충분한 경우 덜 자르기 (오른쪽으로 이동)
else:
result = mid #최대한 덜 잘랐을때가 정답이므로, 여기에서 result에 기록
low = mid+1
print(result)
find_dduck(arr, 6, low, high)
'''
4 6
19 15 10 17
15
'''
재귀 함수 Recursive Function
자기자신을 다시 호출하는 함수로 스택의 개념이 적용되어있다.
하위 문제를 쉽게 해결할 수있을 때까지 문제를 더 작은 하위 문제로 나누는 것 을 의미
- 함수의 내부는 스택처럼 관리. (LIFO, 후입선출)
- 재귀는 해결을 위한 특정 기능을 재호출한다는 측면이고, 분할정복은 문제를 분할하고 해결하는 구체적인 방법론
- 단점:
함수를 반복적으로 호출 하여 메모리를 더 많이 사용한다. - 단점에도 불구하고 수학적으로 개념이 복잡한 경우에는 시간과 공간(메모리)복잡도 측면에서 효율이 안 좋더라도 재귀를 사용하여 문제를 해결하는 것이 좋다.
- 분할정복법을 활용하기 위해서는 재귀개념(기능 재호출)이 필요
# 단순 무한 재귀 함수
'''
무한 재귀 호출을 하기때문에 RecursionError가 발생
RecursionError: maximum recursion depth exceeded while calling a Python object
--> 최대 재귀 깊이 초과 메시지
'''
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
# 종료 조건을 포함한 재귀 함수
'''
재귀함수를의도적으로 무한루프를 사용할 것이 아니라면
재귀함수의 종료 조건을 반드시 명시 해야 한다.
'''
def recursive_func(i):
if i == 5:
return
print (i, '번째 재귀 함수에서', i+1,'번째 재귀함수를 호출합니다')
recursive_func(i+1)
print (i, '번째 재귀함수를 종료 합니다.')
recursive_func(1)
'''
1 번째 재귀 함수에서 2 번째 재귀함수를 호출합니다
2 번째 재귀 함수에서 3 번째 재귀함수를 호출합니다
3 번째 재귀 함수에서 4 번째 재귀함수를 호출합니다
4 번째 재귀 함수에서 5 번째 재귀함수를 호출합니다
4 번째 재귀함수를 종료 합니다.
3 번째 재귀함수를 종료 합니다.
2 번째 재귀함수를 종료 합니다.
1 번째 재귀함수를 종료 합니다.
'''재귀의 개념은 수학적 사고에 기반하고, 코드를 작성하기 전에 문제를 해결하는 재호출 로직 발견해야 한다.
'''팩토리얼 구현 예제'''
# n! <-- !는 팩토리얼 표시로 1x2x3x--------(n-1)xn 을 구현한것
# 수학적으로 0! 과 1!의 값은 1
'''반복문을 통한 팩토리얼(n!) 구현 예제'''
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n+1):
result *= i
return result
'''재귀함수를 통한 n! 구현 예제'''
def factorial_recursive(n):
# n이 1 이하인 경우 무조건 1
if n <= 1:
return 1
# else문은 안써줘도 된다
# n! = n*(n-1)!
return n*factorial_recursive(n-1)
print('반복문 사용 코드: ', factorial_iterative(5))
print('재귀함수 사용 코드: ', factorial_recursive(5))
'''
반복문 사용 코드: 120
재귀함수 사용 코드: 120
'''재귀 함수의 대표적인 활용 예제
유클리드 호제법 - 최대 공약수(GCD) 계산, 두 자연수 A, B에 대하여 (A>B)A를 B로 나눈 나머지는 R, 이때 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.
- 두개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘
- 유클리드 호제법의 아이디어를 재귀 함수로 작성이 가능하다.
- 재귀 문제를 풀기 위해서는 하위 문제를 쉽게 해결할 수 있을 때까지 문제를 더 작은 하위 문제로 나누는 것이라고 이해 해야한다. 이것이 유클리드 호제법의 아이디어와 닮아 있다.
# 유클리드 호제법법
def gcd(a,b):
if a % b == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192,162))
'''
6
'''주의!
- 재귀함수를 사용하면 알고리즘을 간결하게 작성 할 수 있다, 다만 타인이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 새용해야하고 주석을 생활화 해라.
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현 할 수 있다. ( 재귀와 반복문중 유리한 함수를 사용해라 그때그때)
- 컴퓨터가 함수를 연속적으로 호출하면 메모리 내부의 스택 프레임에 쌓인다, 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이요하는 경우가 많다.
재귀의 조건
- base-case 기본 케이스 혹은 조건이 있어야 한다.
- 반복 중지 조건이 있어야 함. 알고리즘은 특성상 반복을 중지할 수 있어야 한다.
- 추가조건과 기본 케이스의 차이를 확인한다.
- 반드시 자기자신을 호출해야한다.
- 함수 마지막 줄에서 자기 자신을 부르는 재귀 작업을 한다.
def sum_list(items):
if len(items) == 1: # 1. Base Case(항목이 1개인 경우가 기본 케이스)
return items[0]
elif len(items)>1: # 2-1. 추가 조건
print("items:",items[0:])
return items[0] + sum_list(items[1:]) # 2-2. items[:]는 한 항목씩 감소한다. # 3. 재귀 작업
print("sum_list:",sum_list([2,3,4,5]))
'''
items: [2, 3, 4, 5]
items: [3, 4, 5]
items: [4, 5]
sum_list: 14
'''
ref. https://freedeveloper.tistory.com/371
[이것이 코딩 테스트다 with Python] 17강 재귀 함수
https://www.youtube.com/watch?v=gFpKGWdEE5g&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=17 재귀 함수 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다 단순한 형태의 재귀 함..
freedeveloper.tistory.com
